python - 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 的另一个答案。但是，在不需要顺序和重复的情况下，这应该会更有效。

可以包含重复项但需要项目 (in loc2) 的哈希性的顺序保留解决方案如下：

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

在 python 中，aset只是一个哈希表。检查一个项目是否包含在该集合中是一个（大约）O(1) 操作，因为该项目的位置是通过散列找到的。