8

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

谢谢

4

2 回答 2

15

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

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

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

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

于 2013-02-05T17:55:46.627 回答
12

在“正常”合并排序中，您将数组除以 2，直到达到深度，然后开始合并。两个大小数组的每次合并也需要操作。log2nm2m

这使您得到以下公式（在时序分析中）：

n/2 * 2 + n/4 * 4 + ... 1 * n = n * log 2 n

现在，如果您进行三路合并，您会将数组除以 3。与前一种方法的区别是双重的：

  • 划分的深度是现在。log3n
  • 在合并期间，您需要找到最少的 3 个元素，而不是比较 2 个元素。

这意味着，在最基本的实现中，你会得到这样一个公式：

n/3 * 2*3 + n/9 * 2*9 + ... 1 * 2*n = 2 * n * log 3 n

请注意，要乘以 2，因为找到三个元素中的最小值包含 2 个操作。

渐近，这两个都是Θ(nlogn)。但是，也许（我没有尝试过）在实践中，三路归并排序会因为它的. 然而，由于n = 1000000 仅为 20，而对于相同的数字为 12.5，我怀疑这种优化是否真的有效，除非它非常大。log3nlog2nlog3nn

通过巧妙的实现，k-way 合并可能确实对合并排序有很好的影响。这个想法是，一旦你找到了元素的最小值，你就已经知道了其余不是最小值k的元素之间的关系。k-1因此，一旦从其各自的列表中消耗了该最小元素，您只需比较该列表的新值并找到其相对于其余k-1元素的排序。使用堆，这将是微不足道的。

一定要看看杰瑞的回答。我同意他的观点，多路合并的真正力量来自处理多个磁盘和并行处理。

于 2013-02-05T17:54:09.210 回答