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

Question

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

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

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

Answer 1

假设较长的列表具有较大的内存大小，your_list 具有可通过以下代码检索的内存大小：

import sys
sys.getsizeof(your_list)

（注意：这取决于Python实现。请阅读How many bytes per element are there in a Python list (tuple)?）

您可以通过多种方式继续操作。如果您的原始 "pipeline" 列表可以按 key=sys.getSizeof 排序，那么您可以切片并分配给处理 N 每 N 个元素 (Pythonic way to return list of every nth item in a larger list)。

示例：

sorted_pipeline = [list1,list2,list3,.......]
sorted_pipeline[0::10] # every 10th item, assign to the first sub-process of 10

这将以公平的方式平衡负载，同时由于原始排序而保持复杂度 O(NlogN)，然后保持不变（如果列表被复制则为线性）以分配列表。

将 10 个元素分成 3 组的插图（按要求）：

>>> my_list = [0,1,2,3,4,5,6,7,8,9]
>>> my_list[0::3]
[0, 3, 6, 9]
>>> my_list[1::3]
[1, 4, 7]
>>> my_list[2::3]
[2, 5, 8]

最终解决方案：

assigned_groups = {}
for i in xrange(size):
    assigned_groups[i] = sorted_pipeline[i::size]

如果这不可能，您始终可以保留每个子流程管道的总队列大小的计数器，并调整概率或选择逻辑以将其考虑在内。

Answer 2

One approach I could think of is to try and assign the lists in such a way that the sum of the lengths of the lists assigned to each process is as similar as possible.

假设处理时间与列表长度的总和完全成比例，并且您的处理器容量是同类的，这实际上就是您想要的。这称为 multiprocessor scheduling problem, which is very close to the bin packing problem，但箱数恒定，最大容量最小化。

一般来说这是一个NP-hard问题，所以你不会得到完美的解决方案。最简单合理的方法是贪婪地为分配给它的工作最少的处理器选择最大的工作块。

在 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)

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

Most efficent way to assign lists of irregular length to sub-processes for processing

python

list

mpi

bin-packing