算法的N路合并 [英] Algorithm for N-way merge

问题描述

一个2路合并被广泛​​研究作为归并算法的一部分。 但我有兴趣了解可以执行N路合并的最佳方法是什么？

可以说，我有已经整理各包含1百万整数 N 文件。 我将它们合并到这将有那些亿排序整数1单个文件。

请记住，使用情况下，这个问题实际上是基于磁盘的外部排序。因此，在实际情况下会有存储器限制，以及。因此，合并2个文件在同一时间的天真的做法（99次）将无法正常工作。比方说，我们有可用内存为每个阵列只有一小滑动窗口。

我不知道是否有已经是一个标准化的解决方案，这N路合并。 （谷歌搜索没有告诉我多少）的。

但是，如果你知道一个良好的n路合并算法，请张贴算法中/链接。

时间复杂度：如果我们大大提高文件的数量（ N ）进行合并，将如何影响的时间复杂度的算法？

谢谢您的回答。

我还没有问过这个任何地方，但我觉得这可能是一个有趣的面试问题。因此标记。的

解决方案

如何以下思路：

1. 创建一个优先级队列
   
   
2. 在遍历每个文件的 F 的
   1. 在排队的一对的（nextNumberIn（F），F）的使用的第一个值作为优先重点
      
      
3. 当队列不为空
   1. 在出队头的（M，F）队列的
   2. 在输出的 M 的
   3. 如果 F 的不会枯竭
      1. 在排队的（nextNumberIn（F），F）的

由于添加元素优先级队列可以在对数时间内完成，2项是的 O（N＆倍;日志N）的。自（几乎全部），而循环的迭代增加了一个元件，整体而环是 0（M＆倍;日志N）的其中 M 的是数字的总数排序。

假设所有文件都数的非空序列，我们的 M> N 的，因此整个算法应的 O（M＆倍;日志N）的。

A 2-way merge is widely studied as a part of Mergesort algorithm. But I am interested to find out the best way one can perform an N-way merge?

Lets say, I have N files which have sorted 1 million integers each. I have to merge them into 1 single file which will have those 100 million sorted integers.

Please keep in mind that use case for this problem is actually external sorting which is disk based. Therefore, in real scenarios there would be memory limitation as well. So a naive approach of merging 2 files at a time (99 times) won't work. Lets say we have only a small sliding window of memory available for each array.

I am not sure if there is already a standardized solution to this N-way merge. (Googling didn't tell me much).

But if you know if a good n-way merge algorithm, please post algo/link.

Time complexity: If we greatly increase the number of files (N) to be merged, how would that affect the time complexity of your algorithm?

Thanks for your answers.

I haven't been asked this anywhere, but I felt this could be an interesting interview question. Therefore tagged.

解决方案

How about the following idea:

1. Create a priority queue
   
   
2. Iterate through each file f
   1. enqueue the pair (nextNumberIn(f), f) using the first value as priority key
      
      

3. While queue not empty
   1. dequeue head (m, f) of queue
   2. output m
   3. if f not depleted
      1. enqueue (nextNumberIn(f), f)

Since adding elements to a priority queue can be done in logarithmic time, item 2 is O(N × log N). Since (almost all) iterations of the while loop adds an element, the whole while-loop is O(M × log N) where M is the total number of numbers to sort.

Assuming all files have a non-empty sequence of numbers, we have M > N and thus the whole algorithm should be O(M × log N).

这篇关于算法的N路合并的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！