算法题请教

老师，我想请教一个问题，希望老师能提供些思路，先谢谢老师。

假设有若干个待执行的任务，每个任务执行时间不同，有长有短。
现在可以起固定数量的线程执行这些任务，问如何规划任务的执行顺序，使得能够在最短的时间内执行完所有任务。

csh2020 2021-09-25

源自：模式匹配 2-8 Rabin-Karp 算法的性能分析

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-09-25 09:44:49

你的这个问题的描述非常不清晰，有很多细节需要商榷，对于算法问题来说，很多细节非常重要，甚至可能是问题处理的关键。我只能根据我的理解回答。

==========

首先需要说明的，你描述的问题可能无解（即不能处理所有任务），比如 10 个任务都是在 [1, 10] 之间出现，固定有五个线程的话，是不可能处理这 10 个任务的。

在这个基础上，如果我们想要使用固定的线程处理尽量多的任务，这是一个很标准的贪心模型。我们应该按照每个任务的结束时间排序，优先处理先结束的任务。因为处理了先结束的任务之后，有更多的时间更大可能性的处理剩下的任务。

整个算法大致是：

按照任务的结束时间顺序排序；
一次遍历每一个任务，对于每一个任务，看当前是否有空闲的线程（或者之前不空闲，但是在这个任务开始的时候，这个线程处理的任务已经结束了）。如果有，分配给这个线程。
如果没有，这个任务无法执行，抛弃（在真实系统中，可以重新分配一个开始时间）

其中对于第二步，对于这些线程当前状态的组织，可以使用堆或者树，把这些线程当前分配的任务的结束时间当做 key，这样可以在 log 的时间里选出可以使用的一个线程。

继续加油！：）

收起回答

csh2020 提问者 #1

抱歉，我没有描述清楚。真实问题是这样的，现在有固定数量(比如说1000个)的待编译的 .cc 文件，我们通过以往的真实数据可以大致估算出每个 .cc 文件的编译时间，现在系统中只能同时存在固定数量的线程(比如说5个)来编译这些任务，一个线程编译完一个任务后会被销毁，然后重新创建一个新的线程来处理一个新的任务，但是同时存在的线程总数需要保持不变(比如说5个)，在这种情况下，如果规划这1000个文件的编译顺序，使得总的耗时最短。

2021-09-25 11:16:37
csh2020 提问者 #2

目标是编译完所有文件(一个文件对应一个编译任务)耗时最短，每个任务的编译起始时间由我们的调度策略决定，调度该任务的时间点即作为该任务的起始时间，接下来，对应的线程会一直执行这个编译任务，直至编译完该任务，中途不会切换执行其他任务，最后线程被销毁。

2021-09-25 12:00:23
liuyubobobo 回复提问者 csh2020 #3

这个问题的最优解很有可能是指数级别的。但我可以提供一个算法，可以找到不太差的解。

将所有 1000 个 cc 文件需要编译的总时间求出来，除以 k。假设结果是 T。在最佳情况下，k 个线程编译这个 1000 个文件的时间就是 T。当然有可能所有这些时间段不能被正好分开，所以最终结果是 >= T 的。

下面，我们把 1000 个任务选出适当的任务，尽可能多的分配给一个时间 T。这是一个标准的背包问题。(想象成每个任务是重量和价值等于其时间的物品，背包容量是 T，求可以放入哪些物品，价值最高，即尽量多的占用了这段时间 T，尽量少的浪费时间)

假设用去了 c 个物品，下面要做的事情是用剩下的 1000 - c 个物品重新填入一段时间 T。

每一轮其实就是再决定一个线程要处理哪些任务，执行 k - 1 轮。

最后一轮不需要处理，最后剩下的所有任务都由最后一个线程处理。大概率的，最终剩下的任务的时间和是 > T 的（因为之前的任务分配可能不满）。完成所有任务的时间就是最后剩下的这个线程用的时间。

这个算法得到的结果应该不是最优的（我没有细想，直觉上不是最优的），但是用于实际问题应该是够用的。

继续加油！：）

2021-09-25 12:29:47