Python：快速提取大量列表中所有可能的2组合之间的交集

我有一个大约的数据集。 9K 可变长度列表（1 到 100K 元素）。我需要计算交集的长度所有可能的 2 列表组合在此数据集中。请注意，每个列表中的元素都是唯一的，因此它们可以在 python 中存储为集合。

在 python 中执行此操作最有效的方法是什么？

Edit我忘记指定我需要能够将交集值与相应的列表对进行匹配。感谢大家的及时回复并对造成的困惑表示歉意！

如果你的集合存储在 s 中，例如：

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

然后你可以使用itertools.combinations http://docs.python.org/library/itertools.html?highlight=itertools#itertools.combinations将它们两两相交，并计算交集（请注意，正如亚历克斯指出的那样，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)

这将非常有效，因为它使用迭代器来计算每个组合，并且不会提前准备所有组合。

Edit：请注意，使用此方法，列表“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))

Edit 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] and i[1]将是一个元组(index, set), so i[0][1]是第一组，i[0][0]它的索引。