12

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

现在，我正在使用 coreutils 排序命令：

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

我在 AWS EC2 的 120GB RAM 和 16 核虚拟机上运行它。这需要一天中的大部分时间。

/volatile 是一个 10TB RAID0 阵列。

'LANG=C' 技巧提供 x2 速度增益（感谢1）

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

我的理解是 gnu 'sort' 是 O(n log n) 的合并排序算法的变体，这是最快的：见2 & 3。转向 QuickSort 会有所帮助吗（我对不稳定的排序感到满意）？

我注意到的一件事是只使用了 8 个内核。这与 linux coreutils sort.c 中的 default_max_threads 设置为 8 有关（参见4）。用 16 重新编译 sort.c 会有所帮助吗？

谢谢！

跟进 ：

@dariusz

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

由于数据已经分批生成：我分别对每个桶进行了排序（在几台不同的机器上），然后使用了“sort --merge”功能。像魅力一样工作并且速度更快：O（log N / K）与O（log N）。

我还从头开始重新考虑该项目：现在在生成数据的同时执行一些数据后处理，以便在进行排序之前丢弃一些不需要的数据（噪声）。

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

感谢您的所有有用的评论。

4

3 回答 3

5

快速排序优于归并排序的好处是没有额外的内存开销。归并排序的好处是保证了 O(n log n) 的运行时间，而在枢轴点采样不佳的情况下，快速排序可能会更糟。如果您没有理由担心内存使用，请不要更改。如果你这样做了，只要确保你选择了一个快速排序实现，它会进行可靠的数据透视采样。

我不认为重新编译 sort.c 会有很大帮助。在微优化规模上可能是这样。但是这里的瓶颈将是内存/磁盘速度，而不是可用的处理器数量。我的直觉是 8 个线程已经将你的 I/O 吞吐量最大化，你不会看到性能提升，但这肯定取决于你的具体设置。

此外，您还可以通过利用数据的分布来显着提高性能。例如，均匀分布的数据可以通过单个桶排序过程非常快速地排序，然后使用合并排序对桶进行排序。这还具有减少归并排序的总内存开销的额外好处。如果合并排序的内存复杂度为 O(N)，并且您可以将数据分成 K 个桶，那么您的新内存开销为 O(N/K)。

于 2013-08-27T15:03:09.173 回答
1

只是一个想法：

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

这样一来，您的系统将花费更多时间进行排序，但结果会更快提供，因为对部分排序的数据进行排序将比对未排序的数据进行排序更快。

于 2013-08-27T15:29:27.397 回答
1

我认为，您需要分两个阶段执行该排序：

  1. 拆分为类似尝试的桶，适合内存。
  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 - 文件名和 000 - 字符串的尾部。由于这只是一条记录，因此不再需要拆分此文件。但是，文件“0”和“5”包含 4 和 3 条记录，超过了限制 2。因此，需要再次拆分它们。拆分后：

00:01 02 03

5：（空）

52：（空）

53：（空）

7：000

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

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

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

于 2013-08-29T22:02:41.320 回答