2個包含非共享列表的交集

Question

當兩個列表都包含非共享列表時，找到2個列表的交集的最有效方法是什麼？

基本上，讓我們說我有以下的列表（我完全彌補）：

A = [<foo.bar object at 0x7f267c664080>, <foo.bar object at 0x7f267c664099>] 
B = [<foo.bar object at 0x7f267c664080>, <foo.bar object at 0x123456789101>] 

我們可以看出，A的第一個元素是一樣的B第一要素。

我可以通過for循環創建做簡單的事情：

intersection = [] 

for obj_a in A: 
    for obj_b in B: 
     if ((obj_a == obj_b) and (obj_a not in intersection)): 
      intersection.extend(obj_a) 

，但我只是想知道如果有一個更有效，冷卻器，或簡單的方法。例如，有：

C = [1, 2, 3] 
D = [3, 4, 5] 
set(C).intersection(set(D)) 

...但很明顯，我不能使用非hashables set或frozenset，因爲我得到

TypeError: unhashable type: foo.bar 

有沒有這樣的非hashables什麼？

Answer 1

哈希是什麼使set有效。如果你不能散列，那麼你就無法利用這個效率 - 你必須將每個對象與其他每個對象進行比較，你會得到一個O（n2）算法，而不是一個攤銷O（n）算法。

不過，如果你只關心對象身份，而不是平等的，那麼你可以讓類型的字典映射對象ID的對象，並採取IDS的交集：

>>> class foo(object): pass 
... 
>>> f = foo() 
>>> A = [foo(), foo(), f] 
>>> B = [foo(), f, foo(), foo()] 
>>> [a for a in A if id(a) in (set(map(id, A)) & set(map(id, B))] 
[<__main__.foo object at 0x100a7e9d0>] 

如果你想一個更具代碼效率的解決方案，或者您關心對象相等，那麼@Neil's answer應該就足夠了。

Answer 2

一個簡單的解決方案，使用列表理解：intersection = [element for element in A if element in B檢查是否有相同值的兩個元素在那裏。例如，對於[1, 2, 3]和[0, 1, 5]，它將返回[1]。