Parallelize this nested for loop in python

Question

I am again trying to improve the execution time of this piece of code. Since computing is really time-consuming, I believe that parallelizing the code would be the best solution.

I first worked with maps, as described in this question, but then I tried a simpler approach, thinking that I could find a better solution. However, I could not think of anything, since this is another problem, I decided to publish it as a new question.

I work on a Windows platform using Python 3.4.

Here is the code:

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 

This is the calculate_similarity function:

 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 

And the code explanation:

• word_count - the total number of unique words stored in the list
• t_matrix is a matrix containing a value for each word pair
• the output should be similarity_matrix , the size of which word_count x word_count also contains a similarity value for each pair of words
• normally store both matrices in memory
• after these calculations, I can easily find the most similar word for each word (or the top three similar words, as may be required)
• calculate_similarity accepts two lists of floats, each for a separate word (each row in t_matrix)

I work with a list of 13k words, and if I correctly calculated the runtime on my system, it would be a few days. So, everything that does the work in one day would be wonderful!

Perhaps only simplifying the calculation of numerator and denominator in calculate_similarity will improve significantly.

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

Here's an alternative implementation of the same general algorithm as Matt's answer , using multiprocessing.Pool instead of concurrent.futures.ProcessPoolExecutor . It can be more efficient than its code, because input values ​​( t_matrix ) are only serialized once and passed to the initializer function in each workflow.

 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

You use a lot of lists for so much data. I highly recommend the numpy module. If this is an option, you can do:

 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 )