Python:快速提取大量列表中所有可能的2-组合之间的交叉点。

Question

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

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

编辑我忘了指定我需要能够将交集值匹配到对应的一对列表。感谢大家的及时回应，并为混乱表示歉意！

Answer 1

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

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

然后，您可以使用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)

这将是相当有效的，因为它使用迭代器来计算每一个组合，而不是预先准备好所有的组合。

编辑：注意，使用此方法，列表"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计数”作为累进标识符-否则会发生明显的更改)。

但是，如果这是规范的一部分，您也可以使用更简单的代码--忘记moresets，并且：

  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 ]

干杯,

何塞·玛丽亚·加西亚

对不起，我误解了这个问题。