python:在列表中查找匹配的元组

Question

在另一个二元组列表中找到匹配二元组的最快方法是什么？

下面的代码看起来效率极低。loc1 和 loc2 是 (x,y) 坐标的元组列表。

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

我认为散列是关键，但不确定如何在 Python 上进行。请教我一个优雅的代码。谢谢。

Answer 1

您可以使用集合和交集:

loc3 = set(loc1).intersection(loc2)

这为您提供了一个 set，它是无序的并且不包含重复项(并强制项目是可散列的)。如果这是一个问题，请参阅 Phil Frost 的其他答案。但是，在不需要顺序和重复的情况下，这应该会显着提高效率。

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

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

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