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中,a set只是一个哈希表.检查该组中是否包含项目是(大约)O(1)操作,因为通过散列找到项目的位置.