海量数据选取重复次数最多的n个

不念不忘少年蓝@ 2023-10-17 15:33 16阅读 0赞

最近刚换工作，面试的时候有一道题觉得很有意思，大致是通过web日志分析出网站最多的10条http请求的ip地址、页面等，我想这个可以归纳为海量数据选取重复次数最多的n个，跟网上看过的一题很类似：有10亿个整数，要求选取重复次数最多的100个整数。  
  
现在把几种方法总结一下，以“有10亿个整数，要求选取重复次数最多的100个整数”为例  
1.位图排序  
阶段1：初始化一个空集合  
 for i=\[0,n)  
 bit\[i\]=0;  
阶段2：读入数据i，并设置bit\[i\]=1  
 for each i in the input file  
 bit\[i\]=1;  
阶段3：输出排序的结果  
 for i=\[0,n)  
 if bit\[i\]==1  
 write i on the output file  
这个算法的时间复杂度在O(n)  
  
2.Hash+堆排序  
采用Hash+小顶堆  
Hash就是为了统计每个数出现的次数，然后发生冲突的地方用个链表把它链接起来，在每个节点中存储一个含有data和count成员的结构体，data记录相应的数字，而count记录对应的数字出现的次数，这一步的时间复杂度是o(n).（注意这里虽然数字很多，但是因为会存在大量的重复数据，不用担心最后的空间会有10亿）,然后创建一个大小为100的小顶堆，然后将Hash表中前面100个非空的成员放入小顶堆中，然后将hash表中的其他数据和堆顶出现的次数比较，如果比堆顶出现的次数少，则丢弃当前数，如果大于堆顶元素的出现次数，则替换堆顶，然后进行堆调整，这一步时间复杂度是o(nlog100).  
总的时间复杂度是o(n)+o(nlog100)  
  
3.Hash+桶排序  
1、首先预设1024个文件作为“桶”，依次读取原始数据的记录，每读到一条记录就进行哈希计算  
2、由于相同的记录哈希值一定相同，所以重复数据一定落入同一个桶内，对于落入同一个桶内的数据，直接为该数据的数量加一，即桶内的条目都是唯一的，各自记录自己的总重复数量。  
3、当一个桶的体积达到64M的时候（应该非常罕见），为该桶增加一个子桶，新的数据进来的时候先在父桶内找相同记录，没有的话在放入子桶，重复数设置为1。  
4、当全部数据读取完之后，依次对1024个桶（及其子桶）进行内部排序，可以一次性把64M的数据读入内存快速排序即可，然后再归并父桶及其子桶，最终得到1024个已经内部排序的桶。  
5、最后，构造一个容量为100的大堆，遍历1024个桶，每次从桶内取出一个数放进堆中，如果堆中没有数字被替换出来，则换到下一个桶继续取数字放进堆中，如果堆中的数字被换出来一个，则继续从该桶取数据。直到连续1024次替换没有新的数子桶堆中被换出来位置。  
6、最后得到的100容量的大堆即为所求。  
  
参考文章：  
[http://www.cnblogs.com/dolphin0520/archive/2011/10/19/2217369.html][http_www.cnblogs.com_dolphin0520_archive_2011_10_19_2217369.html]  
[http://blog.csdn.net/lianbch/article/details/6518787  
][http_blog.csdn.net_lianbch_article_details_6518787] [http://www.dewen.org/q/988][http_www.dewen.org_q_988]

来源:http://blog.chinaunix.net/uid-26722078-id-3652446.html

[http_www.cnblogs.com_dolphin0520_archive_2011_10_19_2217369.html]: http://www.cnblogs.com/dolphin0520/archive/2011/10/19/2217369.html
[http_blog.csdn.net_lianbch_article_details_6518787]: http://blog.csdn.net/lianbch/article/details/6518787
[http_www.dewen.org_q_988]: http://www.dewen.org/q/988