Python：在列表中查找匹配的元组

Question

什么是在另一个包含2-tuples的列表中查找匹配的最快方法？

下面的代码看起来非常低效。loc1和loc2是包含（x，y）坐标元组的列表。

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

我认为哈希是关键，但不确定如何在Python上实现它。 请教一个优雅的代码。 谢谢。

- notilas

---

你说得完全正确，哈希是关键。幸运的是，Python通过内置的set和dict类轻松实现了哈希表。因此，mgilson的答案正是你要找的。 - abarnert

Answer 1

您可以使用集合和intersection方法：

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)的操作，因为可以通过哈希找到该元素的位置。

- mgilson

---

+1 - 你也可以使用这个：loc3 = list(set(loc1) & set(loc2))。 - Tadeck

@Tadeck -- 是的，完全正确，但需要构建另一个 set :). 而我更喜欢 intersection，因为它对我来说更明确。 - mgilson

生成器表达式/生成器是具有不同时间/空间成本的另一种解决方案。 - Phil Frost

+1。我没有意识到你现在已经在你的答案中有第二个版本了，浪费时间写相同的答案... 无论如何，值得解释的是，set 是一个哈希表，检查 item in sloc2 只需要对 item 进行哈希处理，所以这正是 OP 知道他想要但不知道如何在 Python 中实现的东西。 - abarnert