一种相当常见的操作是基于另一个 list
进行筛选。人们很快发现这样做:
[x for x in list_1 if x in list_2]
对于大量输入数据而言,它速度慢 - 它的复杂度是O(n*m)。噫,怎样才能加快速度呢?使用set
来使过滤查询变为O(1):
s = set(list_2)
[x for x in list_1 if x in s]
这可以实现良好的O(n)整体性能。然而,我经常看到即使是经验丰富的编码人员也会陷入“陷阱”。
[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]
def g():
return [x for x in list_1 if x in set(list_2)]
def h():
return [x for x in list_1 if x in {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}]
%timeit f()
100 loops, best of 3: 7.31 ms per loop
%timeit g()
10 loops, best of 3: 77.4 ms per loop
%timeit h()
100 loops, best of 3: 6.66 ms per loop
哦,Python(3.3)能够优化去除一个集合字面量。在这种情况下,它甚至比
f()
更快,可能是因为它可以用LOAD_FAST
替换LOAD_GLOBAL
。#python 2.7.5+
%timeit h()
10 loops, best of 3: 72.5 ms per loop
值得注意的是,Python 2没有进行这种优化。我尝试深入研究Python 3正在做什么,但不幸的是dis.dis
无法探索理解表达式的内部。基本上所有有趣的东西都会变成MAKE_FUNCTION
。
现在我想知道——为什么Python 3.x可以将集合字面量优化为仅构建一次,而不能优化set(list_2)
?
f
会快一点。 - asmeurerdis.dis
在内部代码对象上,只需从外部代码对象的co_consts
中挖出代码对象即可。例如:f = lambda: {a for b in c}; dis.dis(f.func_code.co_consts[1])
- Aleksi Torhamo