1

我有一个文件，每行包含空格分隔的数字。每行对应一个数字列表。
现在大约有 300,000 条这样的行（每行平均包含大约 100 个数字）。
我想找到所有此类列表的相互交集，即第一个列表与所有其他列表相交，然后第二个列表与所有其他列表相交，依此类推。
我在用 

set(a) & set(b)

其中 a 和 b 是我在双循环中迭代的列表。
但这需要太多时间。例如：对于与所有其他列表相交的第一个列表，大约需要 3 分钟。
我怎样才能有效地做到这一点？（可能与其他一些语言/工具一起使用）

4

3 回答 3

5

您应该在这里使用生成器表达式，它们会进行惰性计算并节省大量内存：

In [46]: from itertools import imap

In [47]: a = [[1,2,3], [2,3,4], [3,4,5]]

In [48]: reduce(set.intersection,imap(set,a))
Out[48]: set([3])

考虑到您的文件如下所示：

1 2 3
2 3 4
3 4 5

代码：使用itertools.combinations()：

with open("abc.txt") as f:
    lines=(map(int,x.split()) for x in f)
    for x in combinations(lines,2):
        print x,'-->',reduce(set.intersection,imap(set,x))
   ....:         
([1, 2, 3], [2, 3, 4]) --> set([2, 3])
([1, 2, 3], [3, 4, 5]) --> set([3])
([2, 3, 4], [3, 4, 5]) --> set([3, 4])
于 2013-01-22T10:21:59.247 回答
1

出现的第一个想法是首先构建所有集合一次，如果它们都适合内存，然后将它们相交。

如果你真的需要 300000 行与 300000 行的所有交点，无论如何都需要时间。也许你应该重新考虑你的问题。

于 2013-01-22T10:42:38.447 回答
1

我认为您可以通过创建倒排索引来优化这一点，即映射编号 => 包含此编号的行列表。例如，如果10发生在第 5、100、200 行，那么您将拥有

10: [5, 100, 200]

为了进一步优化这一点，您可以将行列表存储为一组对：

10: set( (5,100), (5,200), (100,200) )

然后，要计算 list_a + list_b 的交集，只需找到关联的 rowlist 包含的所有数字(list_a, list_b)。

于 2013-01-22T11:25:26.640 回答