在python中查找大量列表的交集

Question

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

set(a) & set(b)  

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

Answer 1

我认为您可以通过创建一个倒排索引来优化这一点，也就是说，一个mappingnumber=>；包含这个数字的行的列表。例如，如果10出现在第5、100、200行，则

10: [5, 100, 200]

要进一步优化，可以将行列表存储为一组对：

^{pr2}$

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

Answer 2

第一个想法是先建立所有的集合一次，如果它们都能放入内存，然后将它们相交。在

如果你真的需要30万线和30万线的所有交叉口，无论如何都需要时间。也许你应该重新考虑你的问题。在

Answer 3

您应该在这里使用生成器表达式，它们执行延迟求值并节省大量内存：

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])

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

^{pr2}$

代码： 使用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])