python - 列表理解过滤 - "the set() trap"

Question

一个相当常见的操作是根据另一个 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)]

确认!这又是 O(n*m)，因为 python 构建 set(list_2) every 时间，而不仅仅是一次。

---

我认为这就是故事的结局——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(list_2)？

Answer 1

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

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