如何在Python中对列表元素进行并行化

Question

我有一大串字典。我想从这个列表中计算一个二维矩阵，其中每个元素是列表中第I个元素和第j个元素的函数。代码如下：

    matrix=np.array([])
    biglist=self.some_method()
    matrix.resize(len(biglist),len(biglist))

    for i in range(len(biglist)):
        for j in range(i,len(biglist)):
            matrix[i,j]=self.__computeScore(biglist[i], biglist[j], i, j)[2]
            matrix[j,i]=matrix[i,j]

目前的__computeScore方法非常简单：

def __computeScore(self, dictionary1, dictionary2, i, j):
    #value=in future some computation over dictionary1 and dictionary2
    value=1 #for now is so
    return (i,j,value)

即使现在计算分数的方法非常简单，计算矩阵也需要一段时间。我想把矩阵计算并行化。最好的方法是什么？到目前为止，我已经尝试使用来自multiprocessing模块的apply_async和Pool.map，但是计算比原始代码花费的时间还要多。我试过这样的方法：

    pool = multiprocessing.Pool(processes=4)
    params=[]
    print "argument creation" #this takes a while so it's not convinient
    for i in range(len(biglist)):
        for j in range(i,len(biglist)):
            params.append((biglist[i],biglist[j],i,j))

    result=pool.map(self.__computeScore, params) #takes more time than the original code

我也试过这样的方法：

    def my_callback( result ):
        matrix[result[0],result[1]]=result[2]

    pool = multiprocessing.Pool(processes=4)
    for i in range(len(biglist)):
        rcopy=dict(biglist[i])
        for j in range(i,len(biglist)):
            ccopy=dict(biglist[j])
            pool.apply_async(self.__computeScore, args=(rcopy, ccopy, i, j), callback = my_callback)
    pool.close()
    pool.join()

但它比原始代码需要更多的时间。我错在哪里？谢谢

Answer 1

Where am I wrong?

假设在matrix[i,j]=self.__computeScore(...)级别上对多个进程进行并行化将获得显著的性能提升。你知道吗

另外，假设对代码进行一次小的修改将导致显著的加速。像你这样的“数学”问题不一定是这样。这通常需要重新构造算法，包括更有效的数据结构。你知道吗

为什么你会失望

事实上，您观察到的是，与将事情保持在一个进程甚至线程中相比，生成进程并将任务传递给它们带来了巨大的开销。这种开销只有在与任务通信时才会得到回报，与任务所需的计算时间相比，花费的时间要少得多。基于多处理的方法将大部分时间花在进程间通信上，而__computeScore(self, dictionary1, dictionary2, i, j)很可能只是让子进程厌烦。一个反例：假设你给一个进程一个文件名，然后这个进程花15秒钟从该文件中读取数据并处理这些数据。传输文件名只需几微秒。因此，在这种情况下，“定义”工作所需的时间与执行实际工作所需的时间相比可以忽略不计。这是一个多处理的场景。这其实很简单，尤其是当一个人理解了多重处理是如何工作的时候。然而，不幸的是，你在这里的误解非常普遍。你知道吗

你的情况完全不同。你需要知道计算机是如何工作的，以了解如何优化你的应用案例。首先，您应该防止在RAM中复制大量数据，特别是在进程空间之间！您正在操作的大数据应以有效的数据结构（即允许以有效的方式执行所有后续操作的数据结构）存储一次内存。然后您需要认识到Python本身并不是一种快速的语言。解决方案不是使用更快的高级语言，而是尽可能地将性能关键型代码“外部化”为已编译代码您拥有的双嵌套循环就是一个有力的指标。这个循环应该在编译的例程中执行。事实上，你已经把你的问题当作一个线性代数问题来处理，这就要求你更进一步地使用线性代数包（你已经使用了numpy，但没有因此而使用）。我发现你需要循环，因为你的很多“基本”数据都在列表或字典中。在我看来，您需要找到一种摆脱这些列表/目录的方法，并用numpy数据类型定义所有数据。这样，您就可以找到一种简单的方法，使O（N^2）操作由机器代码执行，而不是由Python解释器执行。你知道吗

结论：你应该如何处理这个问题

您不需要多个进程。您需要在一个进程（甚至线程）中使用正确的方法。您需要：

1. 更高效的数据结构
2. 一个基于线性代数的计算算法
3. 用于执行此算法的高度优化的数学库

如果你的方法是正确的，我可以向你保证你的代码运行的速度会快很多。因为numpy/scipy-under-the-hood利用了基于矢量化的CPU特性（SIMD，“单指令，多数据”），它将以最快的速度运行数据操作。而且，如果您的矩阵足够大，因此您的算法在理论上可以利用多个CPU核：numpy和scipy中甚至有OpenMP支持，通过这些支持，某些矩阵操作例程可以在多个线程上自动分配它们的工作。你知道吗