首页 > 编程语言 > 详细

大数据类算法问题

时间:2018-01-15 23:34:35      阅读:205      评论:0      收藏:0      [点我收藏+]

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

1G有2^26个单词,1M可以存2^16个词。

step1:利用hash散列方法,hash(x)/5000将文件单词存到5000个不同的空间。(平均下来,每个空间大概有200k大小,有的可能超过1M,则对于该集合继续划分,知道都小于1M)

step2:将每个集合放入内存进行hashmap处理,key设为单词,value为频率。

step3:对于每个集合,通过最小堆排序的算法求其平率最高的100个。然后将这5000个进行归并排序。(5000*100=500000<2^16)

大数据类算法问题

原文:https://www.cnblogs.com/wuleh/p/8290019.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!