Java中大型数据集的基于文件的合并排序

Question

给定不适合内存的大型数据集，是否有任何库或api在Java中执行排序？该实现可能类似于linux实用程序排序。

Answer 1

Java提供了一个通用的排序例程，该例程可用作您的问题的大型解决方案的一部分。排序太大而无法容纳在内存中的数据的常用方法是：

1）读取尽可能多的数据，使其适合主存储器，比如说1 Gb

2）快速排序1 Gb（在这里使用Collections框架中的Java内置排序）

3）将排序后的1 Gb作为“块1”写入磁盘

4）重复步骤1-3，直到遍历所有数据，然后将每个数据块保存在单独的文件中。因此，如果您的原始数据为9 Gb，则现在将有9个分类为“ chunk-1”到“
chunk-9”的数据块

5）现在，您只需要最后的合并排序即可将9个已排序的块合并到一个完全已排序的数据集中。合并排序将非常有效地处理这些预排序的块。它实际上将打开9个文件读取器（每个块一个），以及一个文件写入器（用于输出）。然后，它比较每个读取文件中的第一个数据元素，并选择最小值，该最小值将被写入输出文件。所选值所来自的读取器前进到其下一个数据元素，并重复9路比较过程以找到最小值，并将答案再次写入输出文件。重复此过程，直到从所有块文件中读取了所有数据为止。

6）第5步完成所有数据的读取后，您就可以完成了-输出文件现在包含已完全排序的数据集

使用这种方法，您可以轻松地编写自己的通用“
megasort”实用程序，该实用程序采用文件名和maxMemory参数，并通过使用临时文件有效地对文件进行排序。我敢打赌，您至少可以找到一些实现此目的的方法，但是如果没有，您可以按照上述方法自行开发。