Python 在运算符中 - 短路

Question

我在 Short-Circuiting in Python 上读到一个有趣的 post 并且想知道这是否适用于 in 运算符。我的简单测试得出的结论是：

%%timeit -n 1000
0 in list(range(10))
1000 loops, best of 3: 639 ns per loop

%%timeit -n 1000
0 in list(range(1000))
1000 loops, best of 3: 23.7 µs per loop
# larger the list, the longer it takes. however, i do notice that a higher 
# value does take longer.

%%timeit -n 1000
999 in list(range(1000))
1000 loops, best of 3: 45.1 µs per loop

有没有详细解释为什么999比0用的时间长。 in 运算符像循环吗？

此外，有没有办法在找到值后告诉 in 运算符 "stop the loop"（或者这是我没有看到的已经默认的行为）？

最后 - 是否还有另一个 operator/function 我正在跳过，它与我所说的 "short-circuiting" in 相关？

Answer 1

确实发生了短路。 in 运算符调用 __contains__ 方法，该方法又根据 class 以不同方式实现（在您的情况下为 list）。搜索 999 花费的时间大约是搜索 0 的两倍，因为一半的工作是创建列表，另一半是遍历它，这在 [= 的情况下是短路的14=].

Answer 2

这是散列对象的另一种外观，set:

from time import time

qlist = list(range(1000))
qset = set(qlist)

start = time()
for i in range(1000):
    0 in qlist
print time() - start

start = time()
for i in range(1000):
    999 in qlist
print time() - start

start = time()
for i in range(1000):
    0 in qset
print time() - start

start = time()
for i in range(1000):
    999 in qset
print time() - start

输出：

0.000172853469849    0 in list
0.0399038791656    999 in list
0.000147104263306i   0 in set
0.000195980072021  999 in set

正如其他人所说，list 实现必须进行顺序搜索。集合包含使用散列值，与在检查的第一个元素中查找项目不相上下。

Answer 3

list 对象的 in 实现在 list_contains 中找到。它执行列表扫描，如果最后一次比较找到该元素，它会提前退出，没有必要继续那里。

涉及的循环是：

for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
    cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                       Py_EQ);

如果 cmp 是 1（从 PyObject_RichCompareBool 返回的匹配值），for 循环条件 (cmp == 0 && i < Py_SIZE(a)) 变为假并且终止。

对于内置的列表对象，in 调用的是一个 C 函数（对于 CPython）。对于 Python 的其他实现，这可以是使用不同语言结构的不同语言。

对于Python中用户自定义的类，所谓的在参考手册Membership test operations中定义的，看一下运行-记下被调用的内容。

你也可以通过时间得出这个结论：

l = [*range(1000)]    
%timeit 1 in l
85.8 ns ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit 999 in l
22 µs ± 221 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

越远的元素越需要扫描。如果它没有短路，所有 in 操作都会产生相似的时序。

Python 在运算符中 - 短路

Python In Operator - Short Circuit

python

python-internals

short-circuiting