Python: 在大量列表中快速提取所有可能2组合的交集
我有一个数据集，大约有9000个长度不一的列表（每个列表的元素数量从1到10万不等）。我需要计算这个数据集中所有可能的两个列表组合之间的交集长度。需要注意的是，每个列表中的元素都是独一无二的，所以可以把它们存储为Python中的集合。
在Python中，有什么高效的方法可以做到这一点呢？
编辑 我忘了说明，我需要能够将交集的值与对应的两个列表匹配起来。感谢大家的快速回复，抱歉造成了困惑！
3 个回答
试试这个：
_lists = [[1, 2, 3, 7], [1, 3], [1, 2, 3], [1, 3, 4, 7]]
_sets = map( set, _lists )
_intersection = reduce( set.intersection, _sets )
然后获取索引：
_idxs = [ map(_i.index, _intersection ) for _i in _lists ]
谢谢，
何塞·玛丽亚·加西亚
PS：抱歉我误解了问题
因为你需要生成一个(N乘N/2)的结果矩阵，也就是O(N平方)的输出，所以无论用什么语言，任何方法都不可能比O(N平方)更快。（在你的问题中，N大约是9000）。所以，我认为没有比（a）创建你需要的N组数据和（b）遍历这些数据来生成输出更简单的方法。换句话说：
def lotsofintersections(manylists):
manysets = [set(x) for x in manylists]
moresets = list(manysets)
for s in reversed(manysets):
moresets.pop()
for z in moresets:
yield s & z
这段代码已经在尝试进行一些小的优化（例如，避免对列表进行切片或从前面删除元素，这可能会增加其他O(N平方)的复杂度）。
如果你有很多核心和/或节点可用，并且在寻找并行算法，那情况就不同了——如果是这样的话，你能说一下你拥有的集群类型、规模，以及节点和核心之间最佳的通信方式等等吗？
编辑：因为提问者在评论中随意提到他们实际上需要被交集的集合的数字（真的，为什么要省略这么重要的部分呢？！至少编辑一下问题来澄清这些内容……），这只需要将其更改为：
L = len(manysets)
for i, s in enumerate(reversed(manysets)):
moresets.pop()
for j, z in enumerate(moresets):
yield L - i, j + 1, s & z
（如果你需要“从1开始计数”以获得逐步标识符——否则就是显而易见的更改）。
但如果这是规格的一部分，你不妨使用更简单的代码——忘掉更多的集合，然后：
L = len(manysets)
for i xrange(L):
s = manysets[i]
for j in range(i+1, L):
yield i, j, s & manysets[z]
这次假设你想“从0开始计数”，只是为了变化;-)
如果你的集合存储在变量 s 中，比如：
s = [set([1, 2]), set([1, 3]), set([1, 2, 3]), set([2, 4])]
那么你可以使用 itertools.combinations 来两两组合这些集合，并计算它们的交集（注意，正如 Alex 提到的，combinations 从 2.6 版本开始才有）。这里用列表推导式（只是为了举例）：
from itertools import combinations
[ i[0] & i[1] for i in combinations(s,2) ]
或者，你也可以用循环，这可能更符合你的需求：
for i in combinations(s, 2):
inter = i[0] & i[1]
# processes the intersection set result "inter"
所以，要获取每个集合的长度，这个“处理”过程可以是：
l = len(inter)
这样做会非常高效，因为它使用迭代器来计算每一种组合，而不是提前准备好所有组合。
补充说明：请注意，使用这种方法，列表 "s" 中的每个集合实际上可以是其他返回集合的东西，比如生成器。如果你内存不够，列表本身也可以是一个生成器。不过，这样可能会慢一些，具体取决于你是如何生成这些元素的，但你不需要同时在内存中存储整个集合列表（在你的情况下，这应该不是问题）。
例如，如果每个集合是由一个函数 gen 生成的：
def gen(parameter):
while more_sets():
# ... some code to generate the next set 'x'
yield x
with open("results", "wt") as f_results:
for i in combinations(gen("data"), 2):
inter = i[0] & i[1]
f_results.write("%d\n" % len(inter))
补充说明 2：如何收集索引（根据 redrat 的评论）。
除了我在评论中提供的快速解决方案，收集集合索引的更有效方法是使用一个 (index, set) 的列表，而不是单纯的 set 列表。
新格式的示例：
s = [(0, set([1, 2])), (1, set([1, 3])), (2, set([1, 2, 3]))]
如果你反正是要构建这个列表来计算组合，那么适应你的新需求应该很简单。主要的循环变成：
with open("results", "wt") as f_results:
for i in combinations(s, 2):
inter = i[0][1] & i[1][1]
f_results.write("length of %d & %d: %d\n" % (i[0][0],i[1][0],len(inter))
在这个循环中，i[0] 和 i[1] 是一个元组 (index, set)，所以 i[0][1] 是第一个集合，i[0][0] 是它的索引。