并行化一个集合交集操作

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个不同的集合，每个集合的长度约为1,000。有两个瓶颈:

• 读取文件
• 计算路口长度

第一个可能是不可避免的，但第二个可以改进。我有一台64核的机器，所以我想知道如何并行化这个程序。是否有某种map reduce库可用于多核机器?

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()使用cpu_count()返回的进程数将l中的每个位置的任务并行化。

在https://gist.github.com/c576fd7f48be5f66deaa上有一个完整的工作示例，对于大型数据集，与在单个进程上运行内置的map()函数相比，我确实在四核机器上获得了显着的性能改进。