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

我在每行中都有一個包含空格分隔數字的文件。每行對應於一個數字列表。
現在有大約300,000這樣的行（每行平均包含大約100個數字）。
我想找到所有這些列表的相互交集，即第一個列表與所有其他列表相交，然後第二個列表與所有其他列表相交，依此類推。
我使用在python中查找大量列表的交集

set(a) & set(b)

其中A和B都列出我得到一個雙循環迭代。
但這需要太多時間。例如：對於與所有其他列表相交的第一個列表，大約需要3分鐘。
我該如何有效地做到這一點？（可能是與其他一些語言/工具）

來源

2013-01-22 Happy Mittal

我們可以看到你的代碼嗎？ –

您是否在找到相交b相交....？「相互交叉」是什麼意思？ – sidi

300,000 x 300,000 = 900億列表。即使你設法計算所有可能的組合，我想知道你將如何存儲它們。 – georg

您應該使用生成器表達式在這裏，他們做懶的評價，節省了大量的內存：

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-22 10:21:59

我不想一次全部交叉。我只想要一次交叉兩個列表。因此，對於例如：list1＆list2，然後是list1＆list3，然後是list2＆list1，然後是list2＆list3，然後是list3＆list1，然後是list3＆list2。 –

@HappyMittal你在這裏尋找'itertools.combinations'。 –

@HappyMittal'list1＆list2'和'list2＆list1'實際上是一回事。 –

來的第一個想法是首先構建所有集合，如果它全部適合內存，然後相交它們。

如果你真的需要300000行與300000行的所有交點，無論如何都需要時間。也許你應該重新思考你的問題。

來源

2013-01-22 10:42:38 MatthieuW

我想你可以通過創建一個倒排索引，即映射數字=>包含這個數字的行列表來優化它。例如，如果發生的行5中，100 10，200那麼你就必須

10: [5, 100, 200]

爲了進一步優化這個，可以將存儲rowlist爲一組對：

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

然後，要計算list_a + list_b的交集，只需查找其關聯的行列表包含(list_a, list_b)的所有數字。

來源

2013-01-22 11:25:26 georg

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

回答

相關問題