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

Question

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

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

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

Answer 1

如果您的集合存储在 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] 是它的索引。

Answer 2

由于您需要生成一个（N × N/2）结果矩阵，即 O(N 平方) 输出，因此任何方法都不能小于 O(N 平方)——当然，在任何语言中。 （N在你的问题中是“大约9K”）。因此，我认为本质上没有什么比 (a) 制作所需的 N 个集合，以及 (b) 迭代它们以产生输出更快的方法了——即最简单的方法。 IOW：

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 平方) 因子）。

如果您有许多可用的核心和/或节点，并且正在寻找并行算法，那么当然情况不同 - 如果这是您的情况，您能否提及您拥有的集群类型、其大小、节点和核心如何最好地通信，等等？

编辑：正如OP在评论中随意提到的那样（！），他们实际上需要相交的集合的数量（真的，为什么要省略规范中如此重要的部分？！至少编辑问题为了澄清它们...），这只需要将其更改为：（

  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 开始计数”，只是为了多样性；-)

Answer 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：抱歉我误解了这个问题