在python中并行化这个嵌套的for循环

Question

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

我是第一次使用这个问题中解释的地图,但后来我尝试了一种更简单的方法,认为我可以找到更好的解决方案.但是我还没有拿出任何东西,所以因为这是一个不同的问题,所以我决定把它作为一个新问题发布.

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

这是代码:

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字的列表,如果我正确计算了我的系统上的执行时间将是几天.所以,任何能在一天内完成工作的事情都会很精彩!

也许只是对计算numerator和denominator中的计算calculate_similarity才能有显着的改进.

Answer 1

这是与Matt的答案相同的通用算​​法的替代实现,仅使用multiprocessing.Pool而不是concurrent.futures.ProcessPoolExecutor.它可能比他的代码更有效,因为input(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 2

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)