python - 在 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 个组合而不计算其余组合。这绝对是可能的，因为排列是可能的，而组合是排列的内部排序子集。然后，Pool 中的每个进程都可以根据 N 的开始和步骤生成自己的进程 - 进程一个计数组合 0, 3, 6...，进程两个计数组合1, 4, 7... 等等，例如。不过，除非您使用 C/Cython，否则这可能会更慢。

解决方案 3(或可能是解决方案 0？)是转到数学堆栈交换并询问是否有针对此问题的数学解决方案而不是计算解决方案。