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

Question

我有大约的数据集可变长度（1至100K元素）的9K列表。我需要计算的所有可能的2-list的此数据集的组合的交点的长度。请注意，在每个列表元素是唯一的，这样它们可以被存储为在集蟒。

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

修改我忘记指定我需要有对交叉值匹配到相应的一对列表的能力。谢谢大家为迅速反应和道歉的混乱！

Answer 1

如果您的集存储在S，例如：

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

然后可以使用 itertools.combinations 把他们两个两个，并计算交点（注意，亚历克斯指出，combinations仅提供自2.6版本）。这里与列表comrehension（只是为了示例的目的）：

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 / 2 N）结果矩阵，即，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 ]

干杯，

何塞玛丽亚莫加西亚

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