云计算大赛总结

作者: shad0w_walker(admin) 分类: 杂心情 发布时间: 2017-04-25 17:14 ė 6 3条评论

上次去面ms,面试官看见我简历就说,参加过这么多竞赛啊。想来我至今的大学生涯就是不断地参加竞赛,我始终认为现在只有不断地coding才是绝对正确。我从来没有认为大多数的本科生有很强科研能力,特别是在我所处这样的弱校里。我看着周围那些拼了命写出paper的同学,不过是这个时代急功近利的缩影。

参加了这么多竞赛,也应该写点总结了。

准备

第一次听说云计算大赛这个名字是在学院的官网,当时公告的内容是四个学长组成的一支队伍在第二届云计算大赛中获了二等奖,并不知道这个比赛是什么,只知道这四个都是我听说过能力特别强的学长。

第三届云计算大赛开始后两个多月,指导老师才跟我们说了这么一个比赛,问我们有没有兴趣,当时我在分布式方面唯一会的就是配置hadoop集群,对hadoop、MapReduce完全不懂,更别说spark、scala、函数式编程这些名词。所以当时的想法是先答应下来试试,试了不行再选择放弃,说实话,一窍不通的我根本没有对这个比赛抱有希望。

当时比赛已经开始两个多月,初赛作品的提交还有一个月时间,而我又面临着china-final和期末考试这两座大山,所以基本上没时间搞,但老师说这个比赛会延期,果然本来16年底截止的初赛延期到了下学期的开学。

初赛

云计算大赛分四个类型,分别是命题赛、技能赛、创意赛和创业赛。命题赛是完成企业生产实践中遇到的问题;创意赛就是提出想法,设计系统原型;创业赛则是让创业团队带着创业项目来找投资。而我参加的技能赛则是在spark上设计算法,解决两道偏理论型的题目。

技能赛有两道题:第一题是对大数据的聚类,第二题是对大型文本串构建通用后缀树。

带着怀疑能不能完成赛题的心情我们开始讨论用哪种语言编程,spark一般可以使用scala、java、python、R。不会scala语法的我看了scala的代码示例,妈呀邪教,赶快丢了。于是和队友讨论怎么用java,但是要使用java编写spark还是要学函数式编程那一套,而且java编出的代码看上去太过冗长。所以最终还是入了scala邪教的巨坑,开始了我和下划线的搏斗。

两道题目主要是我和另一位大佬在做,他负责第一题,我负责第二题。第一题是常听说的聚类,但是要针对给定的数据集进行优化,大佬的思路是在spark mllib的kmeans库基础上优化,分为了预处理和kmeans上的优化两部分,不会ML的我就不细说了。

第二题的后缀树是比赛里会用到的数据结构,遇到这种题目,通常做法是从裤裆中掏出模板,或者用后缀数组、AC自动机之类更简洁或更强大的数据结构代替,但说到并行化我就完全没有头绪了。于是我的第一想法和很多人都一样,找paper。在网上找了好多paper,但是paper里的做法怎么说呢……太过理论化,有的甚至看都看不懂,寒假在家研究了好多论文,又重新把单机构建的UKK和MCC算法学了一遍,发现UKK和MCC都要利用后缀链接这个分布式很难实现的东西,所以基本上毫无进展。接下来就说说我从这种状态慢慢写出程序的一个个过程吧。

版本1

到了开学前夕,实在是写不出什么东西来,本着ACM赛场上没有思路就敲暴力的想法,我写了一个暴力构建后缀树的版本,它的基本思路是把每个后缀串都从树根往下插入这棵树,其中唯一有难度的就是把一根链插入一棵树,balabala之后反正就解决了,本地debug了一下,结果还挺对的。但是放到集群环境下,结果就错误了。

版本2

我傻眼了,集群环境和单机完全不一样,并不会维护一棵大的树,让你把链一根根插入,而是在每个worker上都有树,最终reduce成一棵大树。然后我fix了一下程序,把链插入树的机制改成了树插入树,也就是两棵树合并。令人愉悦的是,集群环境下结果也正确了,但是运行稍微大一点的输入数据,就GG了

版本3

正当我认为我完全GG之时我突然想到,为什么我要把整棵树都构建出来,我可以切断根节点往下的所有路径,然后生成这些子树就行了,于是我写出了一个真正分布式的版本,思路是:根据每个后缀的第一个字符区分它在哪个子树中,然后对每个子树进行合并,最终有多少种字符,就会生成多少棵子树。然后我用广播变量记录了文本串的信息,起初是(String, String, Int)表示每个字符的值,所在文件以及位置。虽然知道这个程序充满了问题,但能跑出部分数据集,我还是开开心心地提交了初赛程序。

版本4

初赛提交没多久,评测人员联系我说我报错了,报错不要紧,这件事被老师和队友知道了,于是我只能硬着头皮改。报错的原因是OOM,我将文件的id记录下来,表示成Int,然后将每个字符的值用Int表示,于是广播变量就变成了(Int, Int, Int),稍稍缓解了内存压力。

初赛结果是第二题跑的比较慢,但还好在规定时间内运行结束了,最大的数据集依然报错,但还好进了复赛。

复赛

进入技能赛复赛有11支队伍,比赛内容还是初赛的题目,但是数据集更换。第一题为一个大型稀疏文本数据集,第二题是初赛的两个大数据集以及两个基因数据集。

版本X

复赛的代码优化了很久,最终的版本思路和初赛还是差不多,但我切割子树时,按其前5个字符,广播变量最终优化成了一个Long类型,至少保证了每个数据集都能跑出来。具体的代码见github

4月21日去南京江北新区科创园进行复赛的最终答辩,有意思的是,答辩的PPT是前一天做好的,演讲稿是当天凌晨准备好的,虽然那时候队友都已经呼呼大睡了。

答辩前我本来完全不慌,但因为是最后一个答辩队伍,看了前面队伍的答辩,突然就慌了,第一题大家都用了kmeans,把我们的优化都讲了,我似乎没什么新意,第二题别人的做法如此华丽,各种我没听说过的名词满天飞,相比之下,我的算法全部都是我自己设计,显得十分简陋。

演讲时如果紧张了又没准备好,那就会讲的吞吞吐吐,如果紧张了又准备的很充分,那就会讲的很快。没错,我当时语速非常地快。本来预计5分钟讲完第一题,但讲完第一题时候我看了一下时间才过去3分钟。于是开始放缓语速讲第二题,最终12分钟讲完了本来准备15分钟讲完的内容。(虽然觉得讲的很怂,不过最终答辩25分拿了24分,那我能不能夸夸自己哦?

结果

最终我们排在了第三名,没错前两名都有一等奖。

总的来说我们的两道题得分都没有特别高也没有特别低,于是累加之后超过了第一题分高但第二题异常、以及第一题分低第二题满分的队伍,上升到了第三名。值得一提的是,第一题考察准确度和时间两个方面,但计算时间得分的时候会将准确度加权乘上,也就是说准确度的占比更高,而我们就属于准确度高,程序特慢的队伍……

总结

我们讨论了一下这次比赛,其实还是有很多可以提高的地方。第一题的数据并没有真正分布到每个worker节点,所以导致耗时较长。第二题别的队伍使用的都是paper中的算法,例如ERA什么,而我没有努力查已有算法,自己想的做法又不够好,导致最终耗时较长。第二题我使用比赛规定的最多48核运行时出错了一直都解决不了,最后只能用21核跑,这也导致了效率的下降,后来学长跟我说shuffle时可能内存不够把数据写到磁盘上了我才恍然大悟,而且第二题出题方的主旨是算法的通用性和可扩展性,换句话说,就是要能对任意大小的文本串进行构建,这就十分的先进了,反正我的算法做不到。如果有些问题能够解决,最后的成绩说不定还能有所提升,说到底,还是经验不足。

总的来说,对于赛前对云计算毫无所知的我来说这样的成绩已经不错了,我和大佬这两个业余云计算玩家超过了不少云计算方向实验室的学生,甚至很多都是研究生。话说回来,看完答辩,对南大PASA实验室的冠军队伍还是非常服气的。

 

最后附一张答辩照片

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/723.html

3条评论

  1. ramay7 2017年4月28日 23:06 回复

    admire!Orz

    1. shad0w_walker(admin)
      shad0w_walker(admin) 2017年4月29日 17:30 回复

      Orz tuilaoshi

  2. sb_walker 2017年5月15日 18:51 回复

    Or2Or2Or2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部