python：在列表中查找匹配的元組

Question

在另一個2元組列表中找到匹配2元組的最快方法是什麼？

以下代碼看起來效率極低。 loc1和loc2是（x，y）座標的元組列表。

loc3=[] 
for loc in loc1: 
    if loc in loc2: 
     loc3.append(loc) 

我認爲哈希是關鍵，但不知道如何在Python上做到這一點。 請教我一個優雅的代碼。 謝謝。

Answer 1

您可以使用集和intersection：

loc3 = set(loc1).intersection(loc2) 

這給你一個set是無序的，並不會包含重複（並強制的項目是可哈希）。如果這是一個問題，請參閱Phil Frost的其他答案。但是，如果訂單和重複是不必要的，這應該會更有效率。

甲順序保存液，其可以包含重複，但需要的項目hashability（在loc2）如下：

sloc2 = set(loc2) 
loc3 = [ item for item in loc1 if item in sloc2 ] #still O(m) 

在Python中，set僅僅是一個哈希表。檢查一個項目是否包含在該集合中是一個（大約）O（1）操作，因爲該項目的位置是通過散列查找的。