一个相当常见的操作是在另一个list
的基础上过滤一个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)]
Ack!这又是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并没有进行这种优化。我试着进一步研究python3在做什么,但不幸的是,dis.dis
无法探究理解表达式的内部结构。基本上所有有趣的东西都变成了MAKE_FUNCTION
。
所以现在我想知道,为什么python 3.x可以优化set literal,只构建一次,而不构建set(list_2)
?
为了优化set(list_2)
,解释器需要证明list_2
(及其所有元素)在迭代之间不会发生变化。在一般情况下,这是一个棘手的问题,如果口译员甚至不尝试解决它,我也不会感到惊讶
另一方面,集合文字不能在迭代之间更改其值,因此优化是安全的。
来自Python 3.2的新增功能:
Python的窥视孔优化器现在将
x in {1, 2, 3}
这样的模式识别为对一组常量的成员资格的测试。优化器将集合重铸为frozenset并存储预先构建的常量。
所以现在我想知道-为什么python 3.x可以优化掉这个集合literal只生成一次,但不设置(list_2)?
还没有人提到这个问题:你怎么知道set([1,2,3])
和{1, 2, 3}
是一回事?
>>> import random
>>> def set(arg):
... return [random.choice(range(5))]
...
>>> list1 = list(range(5))
>>> [x for x in list1 if x in set(list1)]
[0, 4]
>>> [x for x in list1 if x in set(list1)]
[0]
你不能掩盖文字;可以对set
进行阴影处理。因此,在考虑提升之前,您不仅需要知道list1
没有受到影响,还需要确保set
是您所认为的。有时,您可以在编译时的限制条件下或在运行时更方便地做到这一点,但这绝对是不平凡的。
这有点有趣:通常当有人建议进行这样的优化时,一个阻力是,尽管它们很好,但它会让人们更难推理Python的性能会是什么样子,即使是在算法上。你的问题为这种反对意见提供了一些证据。
注释太长
这与优化细节或v2与v3的差异无关。但当我在某些情况下遇到这种情况时,我发现用数据对象制作上下文管理器是有用的:
class context_set(set):
def __enter__(self):
return self
def __exit__(self, *args):
pass
def context_version():
with context_set(list_2) as s:
return [x for x in list_1 if x in s]
使用这个我看到:
In [180]: %timeit context_version()
100 loops, best of 3: 17.8 ms per loop
在某些情况下,它在理解之前创建对象和在理解中创建对象之间提供了一个很好的权宜之计,并且如果你想要的话,它还允许自定义拆卸代码
可以使用contextlib.contextmanager
制作更通用的版本。这是我的意思的一个快速而肮脏的版本。
def context(some_type):
from contextlib import contextmanager
generator_apply_type = lambda x: (some_type(y) for y in (x,))
return contextmanager(generator_apply_type)
然后可以做:
with context(set)(list_2) as s:
# ...
或者同样容易
with context(tuple)(list_2) as t:
# ...
基本原因是文字真的不会改变,而如果它是像set(list_2)
这样的表达式,那么评估目标表达式或理解的可迭代性可能会改变set(list_2)
的值。例如,如果你有
[f(x) for x in list_1 if x in set(list_2)]
CCD_ 23可能对CCD_。
即使对于一个简单的[x for x in blah ...]
表达,理论上blah
的__iter__
方法也有可能修饰list_2
。
我想有一些优化的空间,但当前的行为使事情变得更简单。如果你开始添加优化,比如"如果目标表达式是一个裸名称,而可迭代的是一个内置列表或dict……",那么在任何给定的情况下都会发生什么,这会使计算变得更加复杂。