如何在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（这是必须的）。通常情况下，decimals_array的长度超过40。元素的数量通常是decimals_array长度的一半。

计算的时间非常长。我想让这些计算可以同时进行，所以我最开始考虑创建一个包含所有组合的数组，然后把这个数组的部分内容发送给多个进程来处理，但在创建这个数组的时候，我很快就遇到了内存错误。

现在我在寻找更好的方法来让这段代码支持多进程。

有什么好的方法可以在多个核心上运行这个算法吗？

或者有没有更好（更快）的方法来进行这样的计算？

谢谢大家提前提供的一些想法。

Answer 1

这里有一个解决方案，虽然不是特别简洁。这个想法是使用多个进程，每个进程负责一个interval（区间）。不过，由于itertools.combinations是按顺序处理的，所以每个进程必须循环遍历一些不必要的组合，直到找到正确的区间。当处理完正确的区间后，进程就会停止。这个代码来自于这本书。

import itertools
from tqdm import tqdm
from math import factorial
from multiprocessing import Process
import itertools

def total_combo(n, r):
    return factorial(n) // factorial(r) // factorial(n-r)


def cal_combo(var,noCombo,start,end):
    data = itertools.combinations(range(var),noCombo)
    for i in enumerate(tqdm(data)):
        if i[0] >= start:
            if i[0] < start+10: print(i)
            if i[0] > end: break

if __name__=='__main__':

    noCombo=3
    var=1000

    print(total_combo(var,noCombo),'combinations for',noCombo,'of',var,'variants')
    noProc=6
    interval=total_combo(var,noCombo)/noProc
    if interval%1==0:
        print(interval)

        procs=[]

        for pid in range(noProc):
            proc = Process(target=cal_combo, args=(var,noCombo, interval*pid, interval*(pid+1)))
            procs.append(proc)
            proc.start()

        for proc in procs:
            proc.join()

Answer 2

要真正实现并行处理，你需要解决 combinations() 是顺序执行的问题，这样每个进程才能生成自己的组合。其他部分的问题已经可以并行处理了。

从40个中选20个组合大约有1380亿种组合，所以提前生成这些组合或者在每个进程中生成都会很麻烦。如果一个包含20个元素的列表大约占224字节（根据 sys.getsizeof() 的说法），那么一次性生成所有组合会占用大约30多TB的内存。难怪你会内存不足。你也不能真的把生成器在不同的进程之间分开；换句话说，如果你这么做，每个进程都会得到生成器的一个副本。

解决方案1是设置一个专门的进程来生成组合，并把它们放入一个队列中，可能是分批次放入，以减少进程间通信的开销，其他进程则从这个队列中取出组合。

解决方案2是编写一个非顺序版本的 combinations，可以直接返回第N个组合，而不需要计算其他组合。这是完全可行的，因为对于排列是可以做到的，而组合实际上是排列的一个内部排序子集。然后，Pool 中的每个进程可以根据起始位置和步长N生成自己的组合，比如进程一计算组合 0, 3, 6...，进程二计算组合 1, 4, 7...，以此类推。不过，如果不使用C/Cython，这样做可能会更慢。

解决方案3（或者可能是解决方案0？）是去数学相关的论坛询问，看看是否有数学上的解决方案，而不是计算上的解决方案。