Linux:对包含10^10条记录的500 10文本文件进行排序

Question

我有一个500 in的文本文件，包含大约100亿行，需要按字母顺序排序。最好的算法是什么？我的实现和设置可以改进吗？

目前，我使用的是coreutils排序命令：

LANG=C
sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile

我正在一个120 16的内存和16核虚拟机上运行AWS EC2。这需要一天的大部分时间。

/volatile是一个10 is的RAID0数组。

“LANG=C”技巧提供了x2速度增益(多亏了1)

默认情况下，“排序”使用50%的可用RAM。提高到80%-90%是有改进的。

我的理解是，gnu‘排序’是与O(n log )合并排序算法的一个变体，它是最快的:参见2 & 3.。搬到QuickSort会有帮助吗(我对不稳定的情况很满意)？

我注意到的一件事是，只有8个核心被使用。这与LinuxCoreutilssort.c中的default_max_threads设置为8有关(参见4.)。用16重新编译sort.c会有帮助吗？

谢谢!

跟进：

@dariusz

下面我用了克里斯和你的建议。

由于数据已经成批生成:我分别(在几台不同的机器上)对每个桶进行排序，然后使用“排序-合并”函数。工作起来很有魅力，而且速度更快: O(log /K)与O(log )。

我还从头到尾重新思考了这个项目:现在在生成数据时执行一些数据后处理，以便在进行排序之前可以丢弃一些不需要的数据(噪声)。

总之，数据大小的缩减&排序/合并导致了实现我的目标所需的计算资源的大量减少。

谢谢你所有有益的评论。

Answer 1

与mergesort相比，快速排序的好处是没有额外的内存开销。合并的好处是保证O(n log n)的运行时间，在出现差的枢轴点采样的情况下，作为快速排序可能会更糟。如果你没有理由担心内存的使用，不要改变。如果是这样的话，只需确保您选择了一个执行可靠枢轴采样的快速排序实现。

我不认为重新编译sort.c会有什么帮助。这可能是，在一个微观的优化规模。但是这里的瓶颈将是内存/磁盘速度，而不是可用的处理器数量。我的直觉是，8个线程将使您的I/O吞吐量达到最大，您将不会看到性能的提高，但这肯定取决于您的特定设置。

此外，通过利用数据的分布，您可以获得显著的性能提升。例如，均匀分布的数据可以通过单个桶排序传递来快速排序，然后使用mergesort对桶进行排序。这还具有降低mergesort的总内存开销的额外好处。如果合并的内存容量为O(N)，并且可以将数据分离到K桶中，则新的内存开销为O(N/K)。

Answer 2

只是一个想法：

我假设文件内容是在相当长的时间内生成的。编写应用程序(脚本？)它会周期性地将直到现在生成的文件移动到不同的位置，将其内容附加到另一个文件，对该不同的文件执行排序，然后重复，直到收集到所有数据。

这样，您的系统将花费更多的时间排序，，但结果将在之前可用，因为排序部分排序的数据将比排序未排序的数据更快。

Answer 3

我想，你需要分两个阶段来完成这样的表演：

1. 分裂成trie -like桶，放入内存中。
2. 按照字母顺序迭代桶，取每一个，排序，并附加到输出文件。

这是个例子。

想象一下，您的桶限制只有2行，您的输入文件是：

婴儿: 0000 0001 0002 0003 5 53 52 7000

在第一次迭代中，您读取您的输入文件“超级桶，空前缀”，并按照第一个字母拆分。

将有3个输出文件：

0: 000 001 002 003

5：(空)3 2

7: 000

正如您所看到的，带有文件名/前缀7的桶只包含一个记录000，即"7000"，拆分为字符串的7-文件名和1000尾。因为这只是一条记录，所以不需要再分割这个文件了。但是，文件"0“和"5”包含4和3条记录，比限制2更多。因此，需要再次拆分它们。分裂后：

00: 01 02 03

5：(空)

52：(空)

53：(空)

7: 000

正如您所看到的，前缀为"5“和"7”的文件已经分裂。所以，只需要拆分文件"00“。

正如您所看到的，在拆分之后，您将拥有一组相对较小的文件。此后，运行第二阶段：

对文件名进行排序，并根据排序顺序处理文件名。对每个文件进行排序，并将结果追加到输出，并将文件名添加到输出字符串中。