如何排序非常大的文件

Question

我有一些文件应该根据每行开头的id进行排序.文件大约2-3 GB.

我试图将所有数据读入ArrayList并对它们进行排序.但记忆力还不足以让他们全部保留.这是行不通的.

线条看起来像

0052304 0000004000000000000000000000000000000041 John Teddy 000023
0022024 0000004000000000000000000000000000000041 George Clan 00013

我怎样才能对文件进行排序？

Answer 1

这不完全是Java问题.您需要研究一种有效的算法,用于对未完全读入内存的数据进行排序.对Merge-Sort的一些改编可以实现这一点.

看看这个:http: //en.wikipedia.org/wiki/Merge_sort

和:http: //en.wikipedia.org/wiki/External_sorting

基本上,这里的想法是将文件分成更小的部分,对它们进行排序(使用合并排序或其他方法),然后使用合并排序合并来创建新的排序文件.

Answer 2

您需要外部合并排序才能执行此操作.这是一个Java实现,可以对非常大的文件进行排序.

Answer 3

由于您的记录已经是平面文件文本格式,您可以将它们管道输入UNIX,sort(1)例如sort -n -t' ' -k1,1 < input > output.它将自动分块数据并使用可用内存执行合并排序/tmp.如果您需要的空间超过可用内存的空间,请添加-T /tmpdir到命令中.

很有趣的是,当你可以使用每个平台上可用的工具并且已经存在了几十年时,每个人都告诉你下载大量的C#或Java库或自己实现合并排序.

Answer 4

您可以只读取键和行开始位置的索引（也可能是长度），而不是一次将所有数据加载到内存中，例如

class Line {
   int key, length;
   long start;
}

这将使用每行大约 40 个字节。

对这个数组进行排序后，您可以使用 RandomAccessFile 按照它们出现的顺序读取这些行。

注意：由于您将随机访问磁盘，而不是使用内存，这可能会非常慢。一个典型的磁盘需要 8 毫秒来随机访问数据，如果您有 1000 万行，这大约需要一天时间。（这绝对是最坏的情况）在内存中大约需要 10 秒。