美国访学记录(待续)

我的导师张岩峰教授,在我上研二期间去了美国访学。在11月时,他突然问我“想不想去美国?这边的张晓东教授想让你来做研究”我突然一愣,内心想去,但又怕水平不够过去丢人。经过了一周的思考,我决定过去见识见识。 作出决定之后,我回了老家办理了人生第一本护照。然后回到沈阳,准备签证的事项,而美国那边在办理DS2019。当我拿到了DS2019后,向美国驻沈阳领事馆申请列签证。办理签证真的很麻烦,为了顺利通过签证,我准备了所需要的全部材料。当时面签我的是个黑人小哥哥,穿着西服打着领带面容和善。面签时,我首先用英文做了自我介绍,然后小哥哥在敲键盘、看材料。然后问我了是哪一方提供资助,我回答是OSU,就这样我的签证就顺利的通过了。 就这样,我在2017年12月来到了俄亥俄州立大学(OSU) – The Ohio State University。在OSU的Xiaodong Zhang教授、Hao Wang博士与Rubao Lee博士的指导下,开展了GPU相关的研究。 以下内容和照片均为本人编写与拍摄,部分照片由旧手机拍摄画质较差。 第一章 出发 我从沈阳桃仙国际机场出发,乘坐达美航空的DL188途径北京-底特律,最后到达哥伦布。 从底特律到哥伦布降落的时候,我在飞机上拍下了第一张美国的夜景。 图4中,那个巨大的运动场是Ohio Stadium。在那里时常有巨星的演唱会、橄榄球比赛举行。很可惜,Taylor Swift在那里举办过演唱会但是我没有去。 第二章 开始 在刚来美国的前5天,我是住在张岩峰教授租的公寓里,因为尚未到期我可以先住着,然后再租新的地方。 在临时住所带了一周,在24号平安夜去了下美国的超市 – Walmart买了些食材做了几顿饭。 有意思的是,那天下午我在等车站遇到了对金发的母女,他们遇到我对我说“你帮助别人有什么感受”,大概就是这个意思吧。我一时没有反应过来如何回答,愣了一会。然后她们没有说什么,只是说“Merry Christmas”,我也回了一句。再几个月后,我从Target超市出来等车,又遇到了这对母女。她们应该早已经不记得我,但是我印象很深。这一次,她们直接问我有没有$15,她们无家可归了,今晚需要住旅店。在美国呆了几个月后,我已熟知这些人对套路,我没有回答。而我也反应过来,第一次遇到她们是向我要钱。这对母女看我没什么反应,说了句“It’s okay”就离开了。 经过了几天的搜寻与联系,我找到了离OSU较近对公寓 – University Village。几个上海交大的本科生到OSU交流,因为要离开需要将房子sublease出去。我接了他们的房子,住到了2018年的7月末。 接下来的几天,我去了未来要进行研究的实验室 – DreeseLab,它位于2015 Neil Avenue。 我在校园附近散步,校园很大、很干净。图2.11是The Oval,一个椭圆形的草地上交织着十几条小路。从DreeseLab出来后,是一个停车场。图2.12是路过停车场,在雪地上遇到的野兔。 在入驻实验室的几天后,有客人来到实验室做一个talk。在晚上,我们去了一家中餐馆 – Hong Kong House吃了顿晚饭。 我每天从公寓到实验室,就靠着UV与OSU提供的班车。 第三章 吃 我是个吃货,起初我会尝试去超市买各种个样的食材,自己做饭。图中的厨具使用的是电炉丝来加热,而不是中国常见的煤气/天然气。在炉子的上面又4个电炉丝,可以条件不同的火力。炉子下面是一个巨大的烤箱,分为2层。 后来,随着研究工作的繁忙,我不再自己做菜,而是去实验室旁边的High Street上去吃快餐。在那条街上有许多餐馆,包括熟悉的McDonald,也有起家与Columbus的Wendy’s,还有著名的美式中餐 – Panda Express。我也吃过那里的墨西哥餐馆 – QDOBA,还有服务态度特差的中餐馆Joy’s…

Read more

6. Z 字形变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下: L C I R E T O E S I I G E D H N 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。 请你实现这个将字符串进行指定行数变换的函数: string convert(string s, int numRows); 示例 1: 输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2: 输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释: L D R E O E I I…

Read more

3. 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。   请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 解法1 思路:使用双层循环,外层循环取字符串s的每个位置,内层循环取外层循环的值至字符串末尾。在内层循环中创建一个范围为0-255的boolean数组用来判断字符是否重复出现,这比HashMap更加轻量。最后,使用一个名为maxLen的变量存放最终结果,我们在内层循环更新这个变量。 解法2 解法一采用了双重循环,时间复杂度是O(n^2)的,我们可以使用滑动窗口方法,维护一个[i, j),0<=i<j<=|s|的窗口,确保窗口内的字串不含重复字符。窗口的前沿是j,后沿是i。前沿滑动,直到加入到窗口内的字符出现重复。此时,我们滑动窗口后沿,直到窗口内不含重复字符。我们在窗口前沿滑动时,计算maxLen = max(maxLen, i – j). 因为是左闭右开区间,直接用i-j就是窗口的大小。 参考:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/

Read more

2. 两数相加

题目描述 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807 https://leetcode-cn.com/problems/add-two-numbers/ 思路1 首先链表是倒叙的,这就启发了我们可以用按位相加的方法逐步地求得结果。链表l1与l2相加,对应位相加后大于10,我们需要向前进位。下面的实现思路较为清晰,且易理解,但是有点笨拙。因为这涉及了三次的链表扫描。 直接将l1与l2对应位相加 扫描相加后的结果,如果大于等于10,向前进位 重新扫描,将添加的多余节点剔除 对于这种解法涉及到3次扫描,运行时间为29ms,“我的提交执行用时已经战胜 93.99 % 的 java 提交记录”。我们还有优化的空间,争取一次扫描就能够完成计算。 思路2 我们能不能只用一个while循环就实现整个算法所需要的流程呢?我们使用while循环,条件为链表l1与l2任意之一遍历到尽头。在while内部有三种可能 l1与l2均未遍历到尽头 只有l1未遍历到尽头 只有l2未遍历到尽头 对于情况1,我们只需要将相应位置到数相加,保存的新建的链表节点中即可。需要注意的是,我们不能直接使用“=”覆盖新建链表节点到val字段,而是应该使用“+=”操作符。这样做是为了利用上,上次循环产生到进位符。对于情况2与3,我们用上次进位符与l1或l2到节点值相加即可。 为了处理相加后可能产生的进位情况,我们在后面判断新建节点的值是否大于等于10.若大于等于10,下一个新建的节点赋予初值1,否则赋初值0.

Read more

Hive源码阅读-2-Hive设计

图1显示了Hive的主要部件以及与Hadoop交互的流程. Hive主要包括以下部件 UI – 用户用于提交查询以及操作Hive的的界面. Hive同时提供命令行与GUI Driver – 用于接受查询的组建. 这个组建实现了会话处理, 它基于JDBC/ODBC接口提供了执行与抽取的APIs. Compiler – 解析SQL, 对查询块和查询表达式做语义分析, 最终会产生执行计划. 查询计划附带了来自于metastore中表和分区信息的元数据. Metastore – 该组建存储了各个表与分区的结构信息, 如列名、列类型. Execution Engine – 该组建负责执行由编译器生成的执行计划. 该计划是由stage组成的DAG. 执行引擎负责管理不同阶段plan的依赖以及在相应的系统组件上执行这些计划. 图1显示了系统的执行流. 首先UI向Driver调用执行接口(1:executeQuery). Driver会为查询创建Session, 并且向Compiler发送查询来产生执行计划(2:getPlan). Compiler从Metastore获取必要的元数据(3:getMetaData, 4:sendMetaData). 元数据被用来校验查询树中表达式的类型, 也可能被用来根据查询谓词对分区进行剪枝. 查询计划由Compiler所生成(5:sendPlan), 它是一个包含stages的DAG, 每个stage是map或reduce操作, 也可以是对元数据的操作, 还可以是对HDFS对操作. 对于map/reduce类型的stages来说, 这类plan包含了map操作符树(在mapper端被执行的操作符树)以及reduce操作符树. 执行引擎将这些stages提交到系统相应的组件. 在每个任务(mapper/reducer)中, 与表关联的或与中间结果关联的反序列化器被用来从HDFS上读取行. 一旦产生出输出, 他们就会被序列化然后被当作临时文件写入HDFS(该操作在mapper端完成, 这是防止任务中不包含reduce操作). 之后的map/reduce操作会读取上一步产生的临时文件. 对于DML操作, 最终的临时文件被移动到保存表的路径. 产生临时文件并移动,而不是直接保存到最终路径. 这么做可以避免脏读的发生, 因为在HDFS中文件重命名是原子操作. 对于查询来说,…

Read more

Hive源码阅读-1-环境搭建

Hive版本与下载地址 项目编译 配置Hive 在Intellij IDEA中导入与调试项目 1. Hive版本与下载地址 http://archive.apache.org/dist/hive/hive-1.2.1/ 2. 项目编译 依赖:Apache Maven 3.6.0、JDK 1.8.0_144、Hadoop 2.X 打包命令:mvn clean package -Phadoop-2 -DskipTests -Pdist clean表示删除$HIVE_HOME/packaging/target目录 -Pdist表示使用pom.xml中名为dist的profile;-Phadoop-2表示支持hadoop 2;-DskipTests表示跳过测试。当命令执行完毕后,我们可以在“apache-hive-1.2.1-src/packaging/target/apache-hive-1.2.1-bin/apache-hive-1.2.1-bin”找到编译完成的完整的项目。为了能够正常使用编译好的Hive,我们对它进行相应的配置。 3. 配置Hive 为了能够中终端中使用hive命令,我们在.bashrc(Mac OS为.bash_profile文件)中追加 我们在conf/hive-site.xml中添加以下内容来配置metadata存贮的位置,下面的配置文件使用derby数据库存储metadata。mapreduce.framework.name变量表示,我们尽可能的使用local模式来执行SQL。 我们接下来修改hive-env.sh,中其中指定HADOOP_HOME与HIVE_CONF_DIR的位置 当上述配置修改完毕后,我们使用source ~/.bashrc命令使终端中的环境变量生效。接下来执行hive,创建新表来测试环境是否配置成功。 4. 在Intellij IDEA中导入与调试项目 点击File->Close关闭当前项目,接下来点击Import Project导入“apache-hive-1.2.1-src”。当导入完毕后,我们点击Idea右边的Maven,展开Profiles,勾选hadoop-2。 我们点击Run-Edit Configurations,中Templates中选择Remote。新建一个远程调试的Configuration。然后我们使用以下命令启动一个启用了远程调试的hive进程 接下来,点击刚刚中Idea中创建的远程Configuration,来连接到正在等待的hive。下面,我们就可以中Idea中下断点,对Hive进行单步调试与分析了。 参考: Hive源码编译及阅读修改调试 Hive Developer FAQ

Read more