在另一个二元组列表中找到匹配二元组的最快方法是什么?
下面的代码看起来效率极低。 loc1 和 loc2 是 (x,y) 坐标的元组列表。
loc3=[]
for loc in loc1:
if loc in loc2:
loc3.append(loc)
我认为散列是关键,但不确定如何在 Python 上进行。 请教我一个优雅的代码。 谢谢。
最佳答案
您可以使用集合和交集
:
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) 操作,因为项目的位置是通过散列找到的。
关于python:在列表中查找匹配的元组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14206623/