3

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

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

编辑我忘记指定我需要能够将交集值与相应的列表对匹配。感谢大家的及时回复，并为造成的混乱道歉！

4

3 回答 3

3

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

于 2009-11-18T17:59:17.390 回答
2

由于您需要生成 (N x N/2) 结果矩阵，即 O(N 平方) 输出，因此没有任何方法可以小于 O(N 平方) - 当然，在任何语言中。（在您的问题中，N 是“大约 9K”）。因此，我认为没有什么比（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 squared) 因素）。

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

编辑：正如 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 开始计数”，只是为了多样化；-)

于 2009-11-18T17:36:58.320 回答
0

试试这个：

_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：对不起，我误解了这个问题

于 2009-12-22T11:19:02.343 回答