python - 将不规则长度的列表分配给子流程进行处理的最有效方法

Question

我有许多对象（大约530,000）。这些对象被随机分配给一组列表（实际上不是随机的，但我们假设它是随机的）。groups这些列表被连续索引并根据它们的索引分配给一个名为 的字典。我知道对象的总数，但我不提前知道每个列表的长度（在这种特殊情况下，它恰好在1和之间变化36000）。

接下来我必须处理列表中包含的每个对象。为了加快此操作，我使用MPI将它们发送到不同的进程。天真的方法是简单地分配每个进程len(groups)/size（其中size包含使用的进程数）列表，分配任何可能的余数，让它处理包含的对象，返回结果并等待。然而，这显然意味着，如果一个进程获得了很多非常短的列表，而另一个进程获得了所有非常长的列表，那么第一个进程将大部分时间处于空闲状态，并且性能提升不会很大。

分配列表的最有效方法是什么？我能想到的一种方法是尝试分配列表，使分配给每个进程的列表长度之和尽可能相似。但我不确定如何最好地实现这一点。有人有什么建议吗？

标签： pythonlistmpibin-packing

Answer 1

我能想到的一种方法是尝试分配列表，使分配给每个进程的列表长度之和尽可能相似。

假设处理时间与列表长度的总和完全一致，并且您的处理器容量是同质的，这实际上就是您想要的。这被称为多处理器调度问题，它非常接近于装箱问题，但具有恒定数量的箱，使最大容量最小化。

通常这是一个 NP 难题，因此您不会得到完美的解决方案。最简单合理的方法是贪婪地为分配给它的最小工作的处理器选择最大的工作块。

在 python 中实现这一点很简单（示例使用列表列表）：

greedy = [[] for _ in range(nprocs)]
for group in sorted(groups, key=len, reverse=True):
    smallest_index = np.argmin([sum(map(len, assignment)) for assignment in greedy])
    greedy[smallest_index].append(group)

如果您有大量处理器，您可能希望smallest_index通过使用优先级队列来优化计算。这将产生比 Attersson 推荐的简单排序拆分更好的结果：

( https://gist.github.com/Zulan/cef67fa436acd8edc5e5636482a239f8 )