首页 > 海量数据处理, 笔试面试题 > 海量数据处理之归并、堆排、前K方法的应用:一道面试题

海量数据处理之归并、堆排、前K方法的应用:一道面试题

2011年9月8日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

 

最初关注海量处理方面是因为好久以前在西安交大BBS算法版上看到一个牛人总结的帖子,收集了起来,后来发现网上铺天盖地地转载过,那个帖子提供了一些解决问题很好的思路,所以就零碎地整理过海量数据处理方面的一些方法,但终归没有深入并做一个稍微细致的思考,从这篇博文开始,希望能坚持整理出来。

下面一道面试题是以前大雄考过我的,据说是那时一些公司常问的类型题目,这里回顾并总结一下,欢迎大家讨论并提出问题。

题目:一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

分析:

本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词

  1. 词频统计

词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时对每个词hashhash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种,至于具体的hash函数,就不讨论了,哈哈

  1. 寻找前K个词

对于海量数据“寻找前K大”,目前总结起来我想一般也就两种方案:堆排序、K选择。

这里需要说明两点:

(1)如果数据量比较大,一般我们认为K>2,如果K<2,遍历一遍即可求,无需过多讨论

(2)如果数据量不是太大,完全可以做K次冒泡来求得

这里我们考虑的是数据量比较大,K>2的情况

当然,还有其他方法,欢迎留言补充。

  • 堆排序

网上对于解决海量前K大问题比较常用的方法就是堆排。我们知道,使用堆排序是要求堆可以放入内存啊,这么大的数据,怎么放?这里有一个技巧,内存中并不是放入所有数据的堆,而是放入K大小的堆,我们知道堆调整的复杂度为lgK,使用K大小的堆,文件遍历一遍我们就可以求出前K大,所以复杂度是NlgK,N是词的个数,只不过这个“遍历”是文件操作,系数要比在内存中“遍历”的系数要大一些。

方案:将统计好的词频取K个放入内存,调整为最小堆,注意这里是最小堆,求前K大,比较当前的元素与最小堆当中的最小元素,如果它大于最小元素则替换那个最小元素,这样最后得到的K个元素就是最大的K个。反之,求前K小,用的自然就是最大堆啦。

  • K选择

K选择是用于求第K大的元素,其实“求前K大”等价于“求第K大”,对数据运行一次K选择算法,那么前K大的元素不就都有了么。但是问题是K选择也需要放入内存啊,这么大的数据又放不下了,肿么办?是的,又是归并的思想。不过这里为大家提供两种可行的方案,方案1使用归并的思想,方案2是直接用K选择的外排序,几乎不需要内存,此为大雄原创,O(∩_∩)O~。

此外,如果大家有更好的方法,欢迎留言补充,谢谢!

方案1:我当时的想法是,将统计好的词频分段,先在内存中求出每段的前K大,然后各段的前K大有了,再将这几段的前K大放入内存求得最终的前K大

方案2:直接使用文件运行前K大算法。思路是开两个文件,选取轴数后一个文件放入大数,一个文件放小数,同时记录各文件放入的数目,从而直接用文件得到最终的前K大。这样做只是时间上耗费可能要多一些

  • 堆排 & K选择的对比分析

这里对两种方法做一个简单的分析:复杂度。

前K堆方法的复杂度为NlgK,N为词总数。

K选择方法复杂度:N + 1/2 + 1/4 + … = 2N. (类似快排:快排是N + N + N + … 共lgN个),这样看起来貌似前K快一点,呵呵,实际上还要考虑系数的问题,例如操作文件比操作内存的系数必然要大,一般来讲:只能说K很小的时候,堆比较快;K很大的时候,前K比较快吧。

放假的时候准备把相关的代码简单写一下吧,不要停止思考。。。加油!

  • Yx.Ac

    @memon
    1. 这个的确如你所说,这里列出来就是提供一种思路,哈哈
    2. 方案1不是用前K堆的,这个思路就是考虑到内存只能放入一段,所以针对每段求出前K,那么总的前K必然是在这5段的前K中的。
    3. 我觉得trie树很有意思,能详细说下不?@memon

  • memon

    1. k选择那个 应该就是quick sort取前k大的方法 但是吧磁盘当内存用了。我觉得实际应用效果有限,因为io和内存的性能相比太低了,而且内存的随即读写很好,但是机械硬盘最好顺序读写。
    2. “方案1:我当时的想法是,将统计好的词频分段,先在内存中求出每段的前K大,然后各段的前K大有了,再将这几段的前K大放入内存求得最终的前K大” 这个的具体目的是啥?我觉得内存维护一个k大堆,之后扫一遍所有的段就可以得到结果了。不过,如果这个前k大大到2G的内存是放不下的,我觉得这个方案1应该可行。
    3. 这个用trie树搞搞不知道行不。 如果是自然语言的单词,应该2G能放下吧。。。不太确定。

  • Yx.Ac

    的确是他们很爱出的题目,海量相关的@超超

  • Yx.Ac

    哈哈,是这样。。。@超超

  • http://www.blabla.com 超超

    看了就要顶!
    话说大雄原创的k选择外排序是使用快排的思路,是把大于轴数的数据放到一个文件中,把小于轴数的数据放到另一个文件中,然后递归得到最终的前K大(小)。

    • http://www.blabla.com 超超

      这个题真是大公司的常考题型呀!
      你的博客真是用心良苦呀~ 赞一个!