我需要使用 k 个同时使用的消费者合并 n 个不同大小的排序固定记录文件，其中 k
由于文件的大小可能相差很大，因此在每个步骤中使用所有 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( nn ) :这是一个糟糕的性能复杂性。
问题是“如何以最佳方式安排子排序”？
预先计算所有执行的图真的太大了，在最坏的情况下它可以和你排序的数据一样大。
我的提议是“即时”计算它，让它不是最优的，但至少避免更糟糕的情况。
我有 K=2:
在你的例子中 1 1 10 10 -> 2 20 -> 22 :它仍然是 (20 + 2) + 22 CC 所以 42 CC*
CC:比较或复制:这是我计算的复杂度为 1 的操作。
如果我有 K=1 并将结果重新注入(inject)我的排序文件数组中，我会得到:
(1 1 10 10) -> 2 10 10 -> 12 10 -> (22) : 2 CC + 12 + 22 = 46
对于不同的 K 值，复杂度略有不同
在平均情况下以概率计算该算法的复杂性将非常有趣，但如果您可以接受一些 N² 执行情况不佳的情况。
PS:
k<n 是另一个问题:它可以通过为每个文件添加一个工作器到队列(开始时 n/2 个工作器)简单地解决，并使队列由 k 个线程读取。关于algorithm - 最优k-way合并模式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53117023/