一个相当常见的操作是list基于另一个过滤一个list.人们很快发现这个:
[x for x in list_1 if x in list_2]
大输入速度慢 - 它是O(n*m).呸.我们如何加快速度？使用a set进行过滤查找O(1):
s = set(list_2)
[x for x in list_1 if x in s]
这给出了很好的整体O(n)行为.然而,我经常看到即使是经验丰富的编码员也会陷入The Trap ™:
[x for x in list_1 if x in set(list_2)]
确认!这也是O(n*m),因为python set(list_2) 每次构建,而不仅仅是一次.
我认为那是故事的结尾 - python无法优化它只能构建set一次.请注意陷阱.要忍受它.嗯.
#python 3.3.2+
list_2 = list(range(20)) #small for demonstration purposes
s = set(list_2)
list_1 = list(range(100000))
def f():
return [x for x in list_1 if x in s] …