有效刪除所有重複記錄

Question

我有一個文件，可能是30 + GB或更多。並且在該文件中的每一行被稱爲一個記錄並且由2 COLS，這是這樣的

ID1 ID2

這2個id的所有爲整數（32位）。我的工作是編寫一個程序來刪除所有重複記錄，使記錄具有唯一性，最後將唯一的id2輸出到文件中。

有一些限制，30G內存被允許最多，更好地把工作由非多線程/進程程序高效地完成。

最初我想出了一個主意：由於內存的限制，我決定讀取文件n次，每次只記錄那些記錄與id1 % n = i (i = 0,1,2,..,n-1)。我使用的數據結構是std::map<int, std::set<int> >，它將id1作爲關鍵字，並將id2放在id1的std::set中。

這樣，內存約束不會被違反，但它很慢。我認爲這是因爲隨着std::map和std::set變大，插入速度下降。此外，我需要讀取文件n次，每輪完成後，我必須清除下一輪的std::map，這也需要一些時間。

我也試過哈希，但它並不滿足我要麼，我想可能有太多的衝突甚至300W桶。

所以，我在這裏發佈我的問題，幫助你們爲我提供更好的數據結構或算法。

非常感謝。

PS

腳本（殼，蟒）是期望的，如果它能夠有效地做到這一點。

Answer 1

除非我忽略了一個要求，應該有可能做到這一點在Linux shell作爲

sort -u inputfile > outputfile 

許多實現使您能夠在一個並行化的方式使用sort還有：

sort --parallel=4 -u inputfile > outputfile 

最多四次並行執行。

請注意，sort可能會在/tmp中臨時使用大量空間。如果您的磁盤空間不足，則可以使用-T選項將其指向磁盤上的另一個位置以用作臨時目錄。

---

（編輯:)關於效率的幾句話：

• 的（執行過程中花費的時間的任何問題的解決方案的一部分顯著）將在IO花費，一些sort是高度優化。
• 除非你有非常多的RAM，否則你的解決方案很可能最終會在磁盤上執行一些工作（就像sort）。再次，優化這意味着很多工作，而對於sort所有這些工作已經完成。
• sort的一個缺點是它對輸入行的字符串表示進行操作。如果你要編寫你自己的代碼，你可以做的一件事就是將輸入行轉換爲64位整數並散列它們。如果你有足夠的內存，如果你的IO和整數轉換速度非常快，那麼這可能是一種在速度方面擊敗sort的方法。我懷疑它可能不值得努力，因爲sort很容易使用，而我認爲–足夠快。

Answer 2

我只是不認爲你可以做到這一點，而不使用一堆磁盤。任何形式的數據結構都會帶來如此多的內存和/或存儲開銷，以至於您的算法會受到影響。所以我希望排序解決方案在這裏最好。

我覺得你可以一次對大塊文件進行排序，然後合併（即 from merge-sort）之後的那些塊。在對一個塊進行排序後，顯然它必須返回到磁盤。您可以只替換輸入文件中的數據（假設它是二進制文件），或寫入臨時文件。

就記錄而言，您只有一堆64位值。憑藉30GB RAM，您一次可以保存近40億條記錄。這很漂亮。你可以使用quicksort對很多內容進行排序，或者對mergesort進行排序。你可能不會得到一個連續的大小的內存塊。所以你將不得不分手。這會讓quicksort有點棘手，所以你可能也想在RAM中使用mergesort。

在最後的合併過程中，丟棄重複是很簡單的。合併可能完全基於文件，但在最壞的情況下，您將使用相當於輸入文件中記錄數的兩倍的磁盤量（一個文件用於臨時文件，一個文件用於輸出）。如果您可以使用輸入文件作爲臨時文件，那麼您還沒有超出內存限制或磁盤限制（如果有）。

我認爲這裏的關鍵是要求它不應該是多線程的。這非常適合基於磁盤的存儲。大部分時間將用於磁盤訪問。所以你想確保你儘可能有效地做到這一點。特別是，當您合併排序時，您希望儘量減少搜索量。你有大量的內存作爲緩衝區，所以我相信你可以做到這一點非常有效。

假設你的文件是60GB（我認爲它是二進制的），所以大概有80億條記錄。如果你在RAM中進行合併排序，你一次可以處理15GB。這相當於閱讀和（一次）寫入文件。現在有四個塊。如果你想做純粹的合併排序，那麼你總是隻處理兩個數組。這意味着您再次讀取和寫入文件兩次：一次將每個15GB的塊合併到30GB中，最後一次合併（包括丟棄重複）。

我不認爲這太糟糕。三次進出。如果你找出一個很好的快速排序方式，那麼你可以用少一遍的文件來完成。我想像deque這樣的數據結構可以很好地工作，因爲它可以處理非連續的內存塊......但是，您可能想要自己構建並精細調整排序算法以利用它。

Answer 3

而不是std::map<int, std::set<int> >使用std::unordered_multimap<int,int>。如果你不能使用C++ 11 - 寫你自己的。

std::map是基於節點的，它在每次插入時調用malloc，這可能是爲什麼它很慢。使用未經過處理的映射（散列表），如果您知道記錄數量，則可以預先分配。即使你沒有，malloc的數量將是O(log N)而不是O(N)與std::map。

我敢打賭，這將比使用外部的sort -u快幾倍，更高的內存效率。

Answer 4

當文件中沒有太多重複記錄時，此方法可能會有所幫助。

第一關。爲Bloom filter分配大部分內存。從輸入文件中散列每對，並將結果放入Bloom過濾器。將Bloom過濾器找到的每個副本寫入臨時文件（該文件還將包含一定數量的誤報，但不是重複的）。

第二次通過。加載臨時文件並從其記錄構建映射。關鍵是std::pair<int,int>，值是一個布爾標誌。這個映射可以作爲std :: unordered_map/boost :: unordered_map或std :: map來實現。

第3遍。再次讀取輸入文件，搜索地圖中的每條記錄，如果未找到或標記尚未設置，則輸出其id2，然後設置此標誌。