最近剛換工作，面試的時候有一道題覺得很有意思，大致是通過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://blog.csdn.net/lianbch/article/details/6518787
? ?http://www.dewen.org/q/988

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

總結

以上是生活随笔為你收集整理的海量数据选取重复次数最多的n个的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。