Распараллеливание заданной операции пересечения?

Question

У меня есть файл, подобный следующему:

A 1
A 1
A 2
A 3
B 2
B 3
C 2
C 3

, который я преобразовал в следующую структуру данных:

s = [set([1, 2, 3]), set([2, 3]), set([2,3])]

Чтобы найти длину пересечения всех 2-комбинаций,Я использую следующее:

from itertools import combinations
for i in combinations(s, 2):
    inter = i[0] & i[1]
    print len(inter)

Размер s составляет 300 000 различных наборов, каждый из которых имеет длину около 1000.Есть два узких места:

• Чтение файла
• Вычисление длины пересечения

Возможно, первое неизбежно, но второеможет быть улучшена.У меня есть машина с 64 ядрами, поэтому мне было интересно, как распараллелить эту программу.Есть ли какая-нибудь библиотека сокращения карт, доступная для многоядерного компьютера?

Answer 1

Если вы еще этого не сделали, проверьте модуль multiprocessing. Кроме того, хотя это удобно, нет необходимости использовать itertools.combinations(), чтобы получить набор всех уникальных 2-комбинаций. Если вы можете согласиться с использованием глобальных переменных, вы можете использовать multiprocessing.Pool.map() для передачи его в пул процессов. Например:

from multiprocessing import Pool

def tally(n):
    return [len(s[n] & t) for t in s[n+1:]]

p=Pool()
for resultset in p.map(tally, xrange(len(s)), chunksize=1):
    for result in resultset:
        print result

tally() выполняет пересечение множества на множестве в l в позиции n со всеми последующими позициями в l в одном процессе. p.map() распараллеливает эту задачу для каждой позиции в l, используя столько процессов, сколько возвращено в cpu_count().

Существует полный рабочий пример на https://gist.github.com/c576fd7f48be5f66deaa, и для больших наборов данных я получаю значительное улучшение производительности на четырехъядерном компьютере по сравнению с выполнением только встроенной функции map() на одном процесс.