列表推导式中的过滤 - "set() 陷阱"

Question

一种相当常见的操作是基于另一个 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)？

- roippi

---

感谢您引起我对此细节的关注。 - Hyperboreus

如果使用 frozenset 而不是 set，似乎 f 会快一点。 - asmeurer

虽然有些晚了，但是万一您与此同时还没有弄清楚：您也可以使用dis.dis在内部代码对象上，只需从外部代码对象的co_consts中挖出代码对象即可。例如：f = lambda: {a for b in c}; dis.dis(f.func_code.co_consts[1]) - Aleksi Torhamo

FYI，集合字面量优化是由于这个错误引入的：http://bugs.python.org/issue6690，在Py3开发期间得到解决，但没有回溯。 - ShadowRanger

Answer 1

为了优化set(list_2)，解释器需要证明在迭代过程中list_2及其所有元素都不会改变。这在一般情况下是一个困难的问题，如果解释器甚至没有试图解决这个问题，那也就不足为奇了。

另一方面，一个集合字面值在迭代过程中不能改变其值，因此这种优化是安全的。

- NPE

---

我认为这为引入“where”子句到理解语法中提出了论据，以便可以在表达式中声明变量。 - Marcin

确实，您可以创建一个在推导过程中发生更改的病态“list_2”。 - wim

然而，解释器甚至不会优化 set([0,1,2,...,19]) —— 它的运行速度与 set(list_2) 一样慢。 - Zaz

啊，解释器还需要证明set函数在迭代之间不会改变。这就是为什么它不会优化set([0,1,2,...,19])的原因。 - Zaz

Answer 2

来自Python 3.2的新功能：

Python的Peephole优化器现在可以识别这样的模式，例如x in {1, 2, 3}，作为对常量集合成员关系的测试。优化器将集合转换为不可变集合并存储预构建的常量。

- Ashwini Chaudhary

---

据推测，它也是可传递的，早先已经认识到list2是一个整数常量范围，因此可以替换set(list2)。 - chepner

这并没有回答问题：“为什么Python 3.x可以将集合字面量优化为只构建一次，但不能对set（list_2）进行相同的优化？” 引用没有解答为什么不能对set（list_2）进行相同的优化。 - Bakuriu

@martineau 是的，但是为什么它不认识其他的东西呢？我的意思是：这就像在说“Python 优化了集合字面值而不是其他东西，因为它只优化了集合字面值”。他只确认 OP 的推论是正确的，其他情况没有被优化。为什么很容易理解：因为集合字面值是编译时常量，而 set 函数的调用则不是，解释器在运行时没有太多时间进行优化。这一点在答案中并没有提到。 - Bakuriu

编译器永远无法优化 set(x)，因为它在运行时无法知道名称 set 将绑定到什么。 - asmeurer

另一个问题是：计算对象的集合通常会产生副作用。该对象可能是一个迭代器，它已经运行完毕了。而且对象的 __hash__ 可以做任何事情。我认为这里的例子之所以有效，是因为它是字面量的集合。 - asmeurer

Answer 3

所以我现在想知道 - 为什么Python 3.x可以将集合字面量优化为仅构建一次，但不能对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]

您不能遮蔽（shadow）文字字面值（literal），但可以遮蔽set。因此，在考虑变量提升之前，您需要知道的不仅仅是list1不会受到影响，还需要确保set是您所认为的那个。有时，您可以在编译时的限制条件下或者更方便地在运行时进行这样的确认，但这绝对是费力的。

这有点有趣：通常，当类似于执行此类优化的建议出现时，一个反对意见是，尽管它们很好用，但它使得更难以推断 Python 的性能，甚至是算法上的。您的问题为这一反对提供了一些证据。

- DSM

---

基本上，每个可变对象都需要一个计数器，当对象被修改时，该计数器会递增。然后可以对mylist进行备忘录，其中mylist具有与构建set时相同的计数器值，即它没有被修改。这将为大量操作（每个项目或属性分配）添加开销，而这些功能通常并不常用。 - kindall

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:
    # ...

- ely

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 ...] 表达式，blah 的 __iter__ 方法理论上也可能修改 list_2。

我想应该有一些优化的空间，但当前的行为保持了事物的简单性。如果开始添加像“如果目标表达式是单个裸名称且可迭代对象是内置列表或字典，则只计算一次…”这样的优化，将会使得在任何情况下都更难确定会发生什么。

- BrenBarn