algorithm - 为什么我们应该使用n路合并？它比 2-way merge 有什么优势？

Question

我试着阅读了一些关于 n-way merge 的文章，但没有理解这个概念。我对为什么要使用 n 路合并而不是 2 路合并感到困惑？比如为什么要将数组分成 3 部分，对它们进行排序，然后对 2 部分进行 2 向合并，然后将第 3 部分与合并后的 2 部分进行 2 向合并 :)

谢谢

Answer 1

在进行外部排序时，您通常最终会合并多个流。例如，假设您需要对 1 TB 的数据进行排序，并且只有(比方说)64 GB 的 RAM。

您通常会通过读取 64 GB 数据、对其进行排序，然后将其写出来完成此操作。对完整的 TB 数据重复此操作，为您可以一次保存在内存中的每个“ block ”生成一个中间文件。有很多方法可以改善这一点，但您通常希望的最好结果是生成每个约 128 GB 的已排序中间文件。

这给您留下了许多要合并在一起的中间文件——而且这个数字几乎肯定会大于 2。

如果您要定期执行此操作，则可能需要一些非常高端的硬件来执行此操作。如果您已将每个中间文件放在单独的磁盘驱动器上(并且至少还有一个用于输出)，您几乎可以肯定地通过一次合并所有数据来提高速度，而不是一次只合并两个。该过程通常是 I/O 绑定(bind)的，因此一次从(比如说)8 个磁盘读取的速度通常是一次仅从 2 个磁盘读取的速度的 4 倍左右(尽管这取决于您的输出磁盘具有那么大的带宽，这可能不是真的)。通过避免创建更多中间文件(这将需要进一步合并)，您的整体速度可能会提高一个更大的因素。