基於文件的合併在Java中的大型數據集上排序

Question

給定的大型數據集不適合內存，是否有任何庫或API在Java中執行排序？ 該實現可能類似於Linux實用程序排序。

Answer 1

Java提供了一個通用的排序程序，可以用作問題的更大解決方案的一部分。到過大，無法全部裝入內存中的數據進行排序的常用方法是這樣的：

1）閱讀儘可能多的數據將適用於主內存，讓我們說這是1千兆

2）快速排序是1 GB（這裏就是你會使用從集合框架Java的內置排序）

3）編寫整理的1 Gb到磁盤「塊-1」

4）重複步驟1-3，直到你瀏覽了所有數據，將每個數據塊保存在一個單獨的文件中。因此，如果您的原始數據是9 Gb，現在您將有9個標記爲「塊-1」的數據塊通過「塊-9」

5）您現在只需要最終合併排序來合併9個排序的塊整合到一個完全排序的數據集中。合併排序將對這些預先排序的塊非常有效地工作。它基本上會打開9個文件讀取器（每個塊一個），另外還有一個文件寫入器（用於輸出）。然後比較每個讀取文件中的第一個數據元素並選擇寫入輸出文件的最小值。從中選擇的值的讀者進入其下一個數據元素，重複9路比較過程以找到最小值，再次將答案寫入輸出文件。重複此過程，直到從所有塊文件中讀取所有數據。

6）一旦第5步已經讀完了所有你做的數據 - 你的輸出文件現在包含一個完全排序的數據集

通過這種方法，你可以很容易地編寫自己的通用「megasort」實用它採用文件名和maxMemory參數，並通過使用臨時文件有效地對文件進行排序。我敢打賭，你可以在這裏找到至少幾個實現，但是如果沒有，你可以像上面描述的那樣推出自己的實現。

Answer 2

處理大型數據集的最常見方式是在內存中（您現在可以購買1 TB的服務器）或數據庫中。

如果你不打算使用數據庫（或購買更多的內存），你可以很容易地寫出它自己。

有些庫可能會幫助執行Map-Reduce功能，但它們可能會增加比它們節省的更多的複雜性。