N路合并算法

Question

作为Mergesort算法的一部分,广泛研究了双向合并.但我有兴趣找出一个可以执行N路合并的最佳方式吗？

可以说,我有一些N文件,每个文件已经排序了100万个整数.我必须将它们合并为1个单独的文件,这将有1亿个排序整数.

请记住,此问题的用例实际上是基于磁盘的外部排序.因此,在实际场景中也会存在内存限制.因此,一次合并2个文件(99次)的天真方法将无效.假设我们每个阵列只有一个小的可用内存滑动窗口.

我不确定是否已经存在这种N路合并的标准化解决方案.(谷歌搜索并没有告诉我太多).

但是如果你知道一个好的n路合并算法,请发布algo/link.

时间复杂度:如果我们大大增加N要合并的文件()的数量,那将如何影响算法的时间复杂度？

谢谢你的回答.

我没有被问过这个问题,但我觉得这可能是一个有趣的面试问题.因此标记.

Answer 1

以下想法怎么样:

1. 创建优先级队列
   
   
2. 遍历每个文件f
   1. 使用第一个值作为优先级密钥对该对(nextNumberIn(f),f)进行入队
      
      
3. 队列不空
   1. 出队头(M,F)队列的
   2. 输出m
   3. 如果˚F不会枯竭
      1. 入队(nextNumberIn(f),f)

由于向优先级队列添加元素可以在对数时间内完成,因此项目2是O(N×log N).由于while循环的(几乎所有)迭代添加了一个元素,因此整个while循环是O(M×log N),其中M是要排序的数字的总数.

假设所有文件都有一个非空数字序列,我们有M> N,因此整个算法应该是O(M×log N).

Answer 2

搜索"Polyphase merge",查看经典 - Donald Knuth和EHFriend.

此外,您可能需要查看Seyedafsari和Hasanzadeh 提议的Smart Block Merging,与早期的建议类似,它使用优先级队列.

另一个有趣的原因是Kim&Kutzner的In Place Merging Algorithm.

我还推荐Vitter的这篇论文:外部存储器算法和数据结构:处理海量数据.

Answer 3

一个简单的想法是保持要合并的范围的优先级队列,以这样的方式存储,即首先从队列中移除具有最小的第一元素的范围.然后,您可以执行N路合并,如下所示:

1. 将所有范围插入优先级队列,不包括空范围.
2. 优先级队列不为空时:
   1. 从队列中取出最小元素.
   2. 将此范围的第一个元素附加到输出序列.
   3. 如果它是非空的,则将序列的其余部分插回到优先级队列中.

这种算法的正确性本质上是对双向合并正确工作的证明的推广 - 如果你总是从任何范围添加最小元素,并且所有范围都被排序,你最终将整个序列排序.

该算法的运行时复杂性可以如下找到.设M是所有序列中元素的总数.如果我们使用二进制堆,那么我们最多从优先级队列中进行O(M)插入和O(M)删除,因为对于写入输出序列的每个元素,有一个dequeue来拉出最小的序列,然后是排队将序列的其余部分放回队列中.这些步骤中的每一步都采用O(lg N)操作,因为从其中包含N个元素的二进制堆中插入或删除需要O(lg N)时间.这给出了O(M lg N)的净运行时间,其与输入序列的数量的增长小于线性.

可能有一种方法可以更快地实现这一点,但这似乎是一个非常好的解决方案.内存使用量为O(N),因为我们需要二进制堆的O(N)开销.如果我们通过存储指向序列的指针而不是序列本身来实现二进制堆,除非你有一个真正荒谬的序列要合并,否则这不应该是一个太大的问题.在这种情况下,只需将它们合并到适合内存的组中,然后合并所有结果.

希望这可以帮助!