' x in range(…)'检查的奇怪速度

Question

对于r = range(1500, 2500)，我对x in r进行基准测试，x低于/在/高于范围:

1000 in r :   58 ns ± 0 ns
2000 in r :  101 ns ± 1 ns
3000 in r :   58 ns ± 0 ns

检查1000比检查2000快?这是有道理的，对于1000,Python只检查下限就知道结果，而对于2000，它需要检查两个边界。

检查3000比检查2000快?这是有道理的，对于3000,Python只检查范围的上界就知道结果，而对于2000，它需要检查两个界。

嘿…等一下……

它如何知道首先检查哪个绑定?为什么检查1000和3000都比2000快?

基准代码(在线试用!):

from timeit import repeat
from statistics import mean, stdev
setup = 'r = range(1500, 2500)'
n = 10**4
for _ in range(3):
for x in 1000, 2000, 3000:
code = f'{x} in r'
ts = repeat(code, setup, number=n, repeat=100)
ts = [t/n * 1e9 for t in sorted(ts)[:10]]
print(code, ':  %3d ns ± %d ns' % (mean(ts), stdev(ts)))
print()

Answer 1

在CPython中，实现首先根据两个端点检查值:

if (cmp1 == 1) { /* positive steps: start <= ob < stop */
cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
}

如果其中一个为假，它可以立即退出:

if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
result = 0;
goto end;
}

如果两个检查都为真，那么它必须检查stride是否拒绝该值。(例如，2000 in range(1501, 2500)为真，但2000 in range(1501, 2500, 2)为假)

tmp1 = PyNumber_Subtract(ob, r->start);
if (tmp1 == NULL)
goto end;
tmp2 = PyNumber_Remainder(tmp1, r->step);
if (tmp2 == NULL)
goto end;
/* result = ((int(ob) - start) % step) == 0 */
result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);

这最后一步使得2000 in range(1500, 2500)比任何一个越界检查都慢。

(完整实现见https://github.com/python/cpython/blob/main/Objects/rangeobject.c#L381)

Answer 2

如果我们看一下CPython的实现，我们可以看到range_contains_long函数确实包含了一个快速的边界检查，专门用于正负步骤。

这解释了为什么外部情况都快得多，但当然，这是特定于单个实现的，并且可以随时更改。