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

Question

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

Answer 1

Java 提供了一个通用的排序例程，它可以用作解决您的问题的更大解决方案的一部分。对太大而无法全部放入内存的数据进行排序的常用方法是：

1) 尽可能多地读取适合主内存的数据，假设它是 1 Gb

2) 1 Gb 的快速排序（在这里您可以使用来自 Collections 框架的 Java 内置排序）

3) 将排序的 1 Gb 作为“chunk-1”写入磁盘

4) 重复步骤 1-3，直到您浏览完所有数据，将每个数据块保存在单独的文件中。因此，如果您的原始数据是 9 Gb，那么您现在将拥有 9 个已排序的数据块，标记为“chunk-1”到“chunk-9”

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

6) 一旦第 5 步完成了所有数据的读取——您的输出文件现在包含一个完全排序的数据集

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

Answer 2

处理大型数据集的最常见方法是在内存中（您现在可以购买 1 TB 的服务器）或在数据库中。

如果您不打算使用数据库（或购买更多内存），您可以轻松地自己编写它。

有一些库可以帮助执行 Map-Reduce 功能，但它们可能会增加比节省更多的复杂性。