列表理解过滤-“ set（）陷阱”

Question

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

[x for x in list_1 if x in list_2]

对于大输入而言，速度很慢-为O（n * m）。uck 我们如何加快速度？使用aset进行过滤查找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），因为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()这种情况下甚至更快，大概是因为它可以用代替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（及其所有元素）在迭代之间没有变化。在一般情况下，这是一个难题，如果口译员甚至不尝试解决它，也不会令我感到惊讶。

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