我需要使用k个同时消费者合并n个不同大小的已排序固定记录文件，其中k<n.因为k(可能很多)比n小，所以合并将在多次迭代/步骤中完成。挑战在于在每一步中选择要合并的正确文件。
因为文件的大小可能相差很大，所以在每一步使用所有k个消费者的简单贪婪方法可能是非常不理想的。
一个简单的例子说明了这一点。考虑4个文件分别具有1、1、10和10条记录以及3个使用者的情况。我们需要两个合并步骤来合并所有文件。第一步从3个消费者开始。合并序列((1,1,10)，10)导致(内部)步骤1中的12个读/写操作和(外部)步骤2中的22个操作，总共34个操作。序列(1，(1,10,10))甚至更糟，21+22=43个操作。相比之下，如果我们在第一步中只使用2个消费者，在第二步中使用3个消费者，则合并模式((1,1)，10,10)只需要2+22=24个操作。在这里，我们的克制得到了丰厚的回报。
我在每一步中选择合适数量的消费者的解决方案如下。所有可能的合并状态都可以被排序到有向图(我想这是一个晶格)中，每个边上从一个状态移动到另一个状态的操作数作为代价。然后我可以使用最短路径算法来确定最优序列。
这种解决方案的问题是，即使文件数量不多(比如说数百个)，甚至在应用了一些合理的约束(比如按大小对文件进行排序，只允许合并该列表的前2..k)之后，节点数量也会激增。此外，我无法摆脱这样一种感觉，即这个问题可能有一个"分析"的解决方案，或者至少有一个非常接近最优的简单启发式方法。
任何想法都将不胜感激。
我可以用另一种方式介绍它吗：
传统的合并排序复杂度是o(n.ln(n))，但在我的子列表大小不同的情况下，在最坏的情况下如果一个文件很大，而其他文件都很小(这就是你给出的例子)，则复杂度可能是o(n.n)：这是一个糟糕的性能复杂度。
问题是"如何以最佳方式安排亚发射"？
预先计算所有执行的图形真的太大了，在最坏的情况下，它可能和你排序的数据一样大
我的建议是"动态"计算它，让它不是最优的，但至少避免更坏的情况。
- 我的第一个天真印象是简单地按大小对文件进行排序，然后从较小的文件开始：这样你就可以在迭代过程中优先删除小文件
我有K=2：在你的例子中，1 10 10->2 20->22：它仍然是(20+2)+22 CC，所以42 CC*
CC：比较或复制：这是我计算复杂性为1的操作。
如果我的K=1，并将结果重新插入我的排序文件Array中，我会得到：(1 1 10 10)->2 10 10->12 10->(22)：2立方厘米+12+22=46对于K的不同值，的复杂度略有不同
在平均情况下用概率计算该算法的复杂性将非常令人困惑，但如果你能接受一些针对坏情况的N²执行。
PS:
事实上，k<n是另一个问题：它将通过为队列中的每两个文件添加一个工作者(一开始是n/2个工作者)，并使队列由k个线程读取来简单地解决。
首先是一种替代算法
read all record keys (N reads) with a fileid
sort them
read all files and place the records in the final position according to the sorted key (N R/W)
如果您的文件系统无法处理N+1个打开的文件，或者您的随机文件访问读写速度较慢，则可能会出现问题。即随机读取或随机写入将更快。
优点是只有N*2次读取和N次写入。
回到你的算法
在合并过程中随机将大文件与小文件合并是否值得？无
- 例如(1,1,10,10)->((1,10)，(1,10。((1,1)，10,10)只有24
- 合并大文件和小文件会导致大文件的内容被R/W占用额外的时间
先合并大文件是否划算？无
- E.g(1,10,10,10)->(1,10，(10,10))20+31 ops与((1,10)，10,10
- 再次，我们会因为多次对大文件执行操作而受到惩罚
在最后一次合并时合并少于K个文件是否会付费？是
- 例如(1,2,3,4,5,6)->(((1,2)，3,4)，5,6)3+10+21 vs((1,2,3)，(4,5,6))6+15+21
- 再说一遍，合并最大的文件要花更多的时间是个坏主意
除了第一次合并外，合并少于K个文件是否值得？是
- 例如！1(1,2,3,4,5,6)->((1,2)，3,4)，5,6)3+10+21=34 vs((1,2,3)，4)，5,六)6+10+21=37
- 3号文件被复制了一段额外的时间
- 例如#2(((1，1)，10)，100100)。在这里，我们在前两个步骤中使用k=2，取2+12+212=226个操作。在第二步中使用k=3的替代方案((1，1)，10100)，100)是2+112+212=326个操作
新的启发式
while #files is larger than 1
sum size of smallest files until K or next larger file is greater than the sum.
K-merge these
ToDo证明，在这种情况下，加法的总和将小于所有其他方法。