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

1)读取与主内存相符的数据,假设它是1 Gb

2)1 Gb的Quicksort(这里是从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参数,并通过使用临时文件来有效地排序文件.我敢打赌,你可以在这里找到至少几个实现,但如果不是,你可以按照上述方式滚动自己的.