【算法】海量数据处理算法（top K问题）

本文主要是介绍【算法】海量数据处理算法（top K问题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

举例

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

　　1.分治：

　　顺序读文件中，对于每个词c，取hash(c)%2000，然后按照该值存到2000个小文件中（同一个词hash值相同，放在同一个文件中）。这样每个文件大概是500k（1G/2000 = 500k）左右

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

　　2.hash遍历：

　　对每个小文件，用hash的方式统计每个文件中出现的词以及相应的频率（相当于hash去重）

　　3.堆遍历：

　　用最小堆取出出现频率最大的100个词（最坏的情况同一个hash文件中，前100就是整个文件的前100），

　　并把100个词及相应的频率存入文件，这样又得到了5000（每个词一个频率，100 * 2000 / 50，估计有50倍的重复率）个文件。

　　4.归并整合

　　下一步就是把这5000个文件进行归并（类似与归并排序）的过程了，可以将文件两辆合并，去前100 即可。

这篇关于【算法】海量数据处理算法（top K问题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！