我們得到這些〜50GB的數據文件，包含16個字節的代碼，並且我想找到任何出現時間的1/2或更多的代碼。有沒有什麼辦法可以通過數據一次性完成？日誌梳理算法
編輯：有很多代碼 - 可能每個代碼都不同。
專欄：我選擇達柳斯培根作爲最佳答案，因爲我認爲最好的算法是他所鏈接的多數元素的修改。大多數算法應該是可修改的，只能使用少量的內存 - 就像我認爲的201代碼獲得1/2的內存一樣。基本上你只是走在流數達201個不同的代碼。只要您找到201個不同的代碼，就會丟棄每個代碼（從計數器中扣除1，忘記任何變爲0的代碼）。最後，你最多下降了N/201倍，所以任何比這個更多次的代碼仍然必須在周圍。
但是這是一個兩遍算法，而不是一個。你需要第二次通過才能統計候選人的人數。實際上，很容易發現解決此問題的任何解決方案必須至少使用2次（您加載的第一批元素可能全部不同，其中一個代碼最終可能只有1/2％）。
感謝幫助！
Metwally et al., Efficient Computation of Frequent and Top-k Elements in Data Streams (2005)。我在雅虎工作時閱讀過一些其他相關論文，我現在找不到;但這看起來是一個好的開始。
編輯：啊，看到這個Brian Hayes article。由於Demaine等人和參考文獻，它描繪了一個確切的算法。它通過一次傳遞完成，只有很少的記憶，產生一系列項目，包括您正在尋找的頻繁項目，如果它們存在的話。獲得確切的數字需要一個（現在易處理的）第二遍。
這取決於代碼的分佈。如果有足夠多的不同代碼，您可以在地圖上構建一個帶核心的http://en.wikipedia.org/wiki/Frequency_distribution。否則，您可能必須構建一個http://en.wikipedia.org/wiki/Histogram，然後對檢查每個存儲桶中的代碼頻率的數據進行多次傳遞。
這取決於存在多少個不同的代碼以及您有多少內存可用。
我的第一個想法是建立一個計數器的哈希表，代碼作爲鍵。遍歷整個文件，增加相應代碼的計數器，並計算總數。最後，用超過（*總計數器1/200）的計數器過濾所有密鑰。
我沒有足夠的內存 - 每一個代碼理論上可能不同。 – Gwildore 2008-12-09 04:02:08
如果這些文件僅由16字節代碼組成，並且您知道每個文件有多大，則可以計算每個文件中的代碼數量。然後，您可以找到0.5％的閾值，並按照其他任何建議來計算每個代碼的出現次數，記錄頻率跨越閾值的每個代碼。
每個文件的內容是代表單個數據集還是文件之間有任意的中斷？在後一種情況下，假設隨着時間的推移代碼分佈相當不變，您可以通過將每個文件拆分爲更小，更易於管理的塊來簡化您的工作。作爲獎勵，您可以更快地獲得初步結果，並且可以提前進入下一個流程。
我可以在收集數據時做到這一點，但我確實希望爲整個50 gig文件提供正確的答案。 – Gwildore 2008-12-09 04:02:58
將內存中的文件塊分類，就好像您正在執行和外部排序一樣。但是，不是將每個塊中的所有已排序代碼寫出來，只需編寫每個不同代碼以及該塊中出現的次數即可。最後，合併這些摘要記錄以查找每個代碼的出現次數。
此過程可擴展爲任意大小的數據，並且只會傳遞一次輸入數據。取決於您想要一次打開多少個摘要文件，可能需要多次合併傳遞。
對文件進行排序可讓您使用固定的內存量計算每個代碼的出現次數，而不管輸入大小如何。
您也知道代碼的總數（通過將輸入大小除以固定代碼大小，或通過在更常見的問題中在排序過程中計算可變長度代碼的數量）。
因此，您知道與每個代碼關聯的輸入的比例。
這基本上是管道sort * | uniq -c
如果每個代碼只出現過一次，那是沒有問題的;你只需要能夠數它們。
嗯，沒有。流/速寫算法的全部重點在於無法保留直方圖，因爲數據非常龐大。 – ShreevatsaR 2008-12-09 03:42:22
他/她正在談論使用多次通行證來追捕高計數的時間間隔 - 我的問題只是需要的通過次數。 – Gwildore 2008-12-09 03:57:38
感覺你應該能夠建立一個直方圖，如果你的桶（bin）的大小足夠大：http://en.wikipedia.org/wiki/Histogram#Number_of_bins_and_width – 2009-01-16 02:03:59