68

一个相当常见的操作是list基于另一个过滤一个list。人们很快发现：

[x for x in list_1 if x in list_2]

对于大输入来说很慢 - 它是 O(n*m)。呸。我们如何加快速度？使用 aset进行过滤查找 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)，因为 pythonset(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()这种情况下更快，大概是因为它可以将 a 替换为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)？

4

5 回答 5

51

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

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

于 2013-11-18T19:52:58.760 回答
39

来自Python 3.2 的新增功能：

Python 的窥孔优化器现在可以识别模式，例如x in {1, 2, 3}测试一组常量的成员资格。优化器将集合重铸为 freezeset 并存储预构建的常量。

于 2013-11-18T19:54:34.317 回答
18

所以现在我想知道 - 为什么 python 3.x 可以优化 set 文字只构建一次，而不是 set(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 的性能会是什么样子，甚至是算法上的。您的问题为这一反对意见提供了一些证据。

于 2013-11-18T20:11:14.867 回答
13

评论太长了

这不会涉及优化细节或 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:
    # ...
于 2013-11-18T20:22:22.233 回答
10

基本原因是文字真的不能改变，而如果它是一个类似的表达式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__也blah可以修改list_2.

我想有一些优化的空间，但目前的行为让事情变得更简单。如果您开始为诸如“如果目标表达式是单个裸名称并且可迭代是内置列表或字典...”之类的事物添加优化，那么您将更复杂地弄清楚任何情况下会发生什么给定的情况。

于 2013-11-18T19:54:12.173 回答