列表理解过滤 - "set()陷阱"

Question

一个相当常见的操作是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]
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_GLOBALa LOAD_FAST.

#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(list_2)？

Answer 1

为了优化set(list_2),解释器需要证明list_2(及其所有元素)在迭代之间不会改变.这在一般情况下是一个难题,如果翻译甚至没有尝试解决它,我也不会感到惊讶.

另一方面,集合文字不能在迭代之间改变其值,因此已知优化是安全的.

Answer 2

来自Python 3.2中的新功能:

Python的窥孔优化器现在可以识别模式,例如x in {1, 2, 3}测试一组常量中的成员资格.优化程序将set重新设置为冻结集并存储预先构建的常量.

Answer 3

所以现在我想知道 - 为什么python 3.x可以优化设置文字只能构建一次,但不能设置(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的性能,甚至算法.您的问题为此异议提供了一些证据.

Answer 4

评论太久了

这与优化细节或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:
    # ...

Answer 5

基本原因是文字实际上不能改变,而如果它是一个表达式set(list_2),那么评估目标表达式或理解的可迭代性可能会改变它的值set(list_2).例如,如果你有

[f(x) for x in list_1 if x in set(list_2)]

有可能f修改list_2.

即使对于一个简单的[x for x in blah ...]表达式,理论上也可以修改该__iter__方法.blahlist_2

我认为有一些优化的余地,但目前的行为使事情变得更简单.如果你开始添加优化,例如"如果目标表达式只是一个裸名称,而且迭代是内置列表或字典......那么它只被评估一次",你会弄清楚任何事情会发生什么变得更复杂给定的情况.