当前位置:首页 > 资讯 > info5 > 正文

海量数据处理算法(top K问题)

发表于: 2016-09-22   作者:u010321471   来源:转载   浏览:
摘要: 举例有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。思路首先把文件分开针对每个文件hash遍历,统计每个词语的频率使用堆进行遍历把堆归并起来具体的方案1.分治:顺序读文件中,对于每个词c,取hash(c)%2000,然后按照该值存到2000个小文件中。这样每个文件大概是500k左右。注意:如果其中的有的文件超过了1M大小,还可以按

举例

有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

思路

  • 首先把文件分开
  • 针对每个文件hash遍历,统计每个词语的频率
  • 使用堆进行遍历
  • 把堆归并起来

具体的方案

1.分治:
顺序读文件中,对于每个词c,取hash(c)%2000,然后按照该值存到2000个小文件中。这样每个文件大概是500k左右。

注意:

如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。

2.hash遍历:
对每个小文件,用hash的方式统计每个文件中出现的词以及相应的频率

3.堆遍历:
用 最小堆取出出现频率最大的100个词,并把100个词及相应的频率存入文件,这样又得到了5000个文件。

4.归并整合

下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

海量数据处理算法(top K问题)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号