python - 并行化集合交集操作？

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() 函数相比，我在四核机器上的性能确实有了显着提高。