在 python 中进行 itertools.combinations 计算多进程？

Question

我正在使用这样的算法对小数数组进行一些计算：

fkn = Decimal('0')
for bits in itertools.combinations(decimals_array, elements_count):
    kxn = reduce(operator.mul, bits, Decimal('1'))
    fkn += kxn

我正在使用 Python 3.4 x64。 小数的精度>300（这是必须的）。len(decimals_array) 大多数时候超过 40。 elements_count 大多数时候是 len(decimals_array)/2。

计算需要很长时间。我想让它们成为多进程，所以首先我考虑制作一个所有组合的数组，并将该数组的一部分发送到许多进程 - 但在制作这样的数组期间，我很快就得到了 MemoryError 异常。

现在我正在寻找更好的方法来使该代码多进程。

在多核上运行该算法的好方法是什么？

或者也许有更好（更快）的方法来进行此类计算？

预先感谢您的一些想法。

Answer 1

为了真正并行化，您需要绕过combinations()顺序，以便每个进程都可以生成自己的组合。问题的其余部分已经可以并行化了。

40 选择 20 大约有 1380 亿种组合，因此预先生成或在每个过程中生成它都会造成伤害。一个包含 20 个元素的列表大约需要 224 字节（如sys.getsizeof()），如果一次性生成整个列表，则需要 30 TB 左右。难怪你内存不足。您也无法真正跨进程拆分生成器；或者更确切地说，如果这样做，每个进程都会获得自己的生成器副本。

解决方案 1 是让一个进程的唯一工作是生成组合并将它们推入队列（可能是分批进行），以节省 IPC 开销，并让其他进程使用该队列中的组合。

解决方案 2 是编写一个非顺序版本，combinations返回第 N 个组合而不计算其余组合。这绝对是可能的，因为排列是可能的，并且组合是排列的内部排序子集。然后，a 中的每个进程Pool可以基于 N 个进程一计数组合0, 3, 6...、进程二计数组合1, 4, 7...等的开始和步骤生成自己的进程。除非您使用 C/Cython，否则这可能会更慢。

解决方案 3（或者可能是解决方案 0？）是转到数学堆栈交换并询问该问题是否有数学解决方案而不是计算解决方案。