在 python 中并行化此嵌套 for 循环

Question

我又在努力改善这段代码的执行时间。由于计算非常耗时，我认为最好的解决方案是并行化代码。

我首先按照问题中的解释使用地图，但后来我尝试了一种更简单的方法，认为我可以找到更好的解决方案。但是我还没有想出任何办法，所以因为这是一个不同的问题，所以我决定 post 它作为一个新问题。

我正在 Windows 平台上工作，使用 Python 3.4.

代码如下：

similarity_matrix = [[0 for x in range(word_count)] for x in range(word_count)]
for i in range(0, word_count):
    for j in range(0, word_count):
        if i > j:
            similarity = calculate_similarity(t_matrix[i], t_matrix[j])
            similarity_matrix[i][j] = similarity
            similarity_matrix[j][i] = similarity

这是calculate_similarity函数：

def calculate_similarity(array_word1, array_word2):
      denominator = sum([array_word1[i] + array_word2[i] for i in range(word_count)])
      if denominator == 0:
          return 0
      numerator = sum([2 * min(array_word1[i], array_word2[i]) for i in range(word_count)])
      return numerator / denominator

以及代码的解释：

word_count 是存储在列表中的唯一单词的总数
t_matrix 是一个矩阵，其中包含每对单词的值
输出应该是similarity_matrix，其维度是word_count x word_count，还包含每对单词的相似度值
将两个矩阵都保存在内存中就可以了
经过这些计算后，我可以很容易地找到每个词最相似的词（或前三个相似词，视任务需要而定）
calculate_similarity 采用两个浮点列表，每个列表对应一个单独的单词（每个都是 t_matrix 中的一行）

我处理一个 13k 单词的列表，如果我计算正确，我系统上的执行时间将是几天。所以，任何能在一天内完成工作的东西都很棒！

也许仅在 calculate_similarity 中对 numerator 和 denominator 的计算进行并行化会带来显着改进。

Answer 1

from concurrent.futures import ProcessPoolExecutor, Future, wait
from itertools import combinations
from functools import partial

similarity_matrix = [[0]*word_count for _ in range(word_count)]

def callback(i, j, future):
    similarity_matrix[i][j] = future.result()
    similarity_matrix[j][i] = future.result()

with ProcessPoolExecutor(max_workers=4) as executer:
    fs = []
    for i, j in combinations(range(wordcount), 2):
        future = excuter.submit(
                    calculate_similarity, 
                    t_matrix[i], 
                    t_matrix[j])

        future.add_done_callback(partial(callback, i, j))
        fs.append(future)

    wait(fs)

Answer 2

这是与中相同的通用算法的替代实现，只是使用 multiprocessing.Pool 而不是 concurrent.futures.ProcessPoolExecutor。它可能比他的代码更有效，因为输入的值 (t_matrix) 只被序列化一次并传递给每个工作进程中的 initializer 函数。

import multiprocessing
import itertools

def worker_init(matrix):
    global worker_matrix
    worker_matrix = matrix

def worker(i, j):
    similarity = calculate_similarity(worker_matrix[i], worker_matrix[j])
    return i, j, similarity

def main(matrix):
    size = len(matrix)
    result = [[0]*size for _ in range(size)]
    with multiprocessing.Pool(initializer=worker_init, initargs=(matrix,)) as pool:
        for i, j, val in pool.starmap(worker, itertools.combinations(range(size), 2)):
            result[i][j] = result[j][i] = val
    return result

if __name__ == "__main__":
    # get t_matrix from somewhere
    main(t_matrix)

Answer 3

您对如此大量的数据使用了很多列表推导式。我强烈推荐 numpy 模块。如果这是一个选项，您可以这样做：

import numpy as np
import itertools

t = np.array(t_matrix)

s = np.sum(t,axis=1)

denom = s[:,None] + s[None,:]
num = np.zeros((word_count,word_count))

for i,j in itertools.product(range(word_count),repeat=2):
    num[i,j] = np.where(t[i] <= t[j], t[i], t[j]).sum()

similarity_matrix = np.where(denom != 0.0, 2.*num/denom, 0 )

在 python 中并行化此嵌套 for 循环

Parallelize this nested for loop in python

python

parallel-processing

multiprocessing

python-multithreading

python-multiprocessing