为何在Python 3中“1000000000000000 in range(1000000000000001)”如此之快？

技术背景

在Python 3里，当我们运用in操作符对range对象开展成员检查时，像1000000000000000 in range(1000000000000001)这种操作的执行速度极快。这和我们常规认知里需要遍历整个序列来判断元素是否存在的情况大不相同。要理解这一现象，就需要了解range对象的特性和其内部实现机制。

实现步骤

1. range对象特性

range对象属于智能的序列对象，它不会立刻生成所有数字，而是按需生成。该对象仅存储起始值（start）、终止值（stop）和步长值（step），在迭代过程中，每次迭代都会计算出下一个整数。

2. __contains__方法实现

range对象实现了__contains__方法，此方法能够直接计算出给定数字是否处于其范围内，而无需遍历所有可能的整数。

3. 计算逻辑

• 检查数字是否处于start和stop之间。
• 检查步长是否会“跳过”该数字。

核心代码

Python模拟实现

class my_range:
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi, step = stop, start, -step
        else:
            lo, hi = start, stop
        self.length = 0 if lo > hi else ((hi - lo - 1) // step) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('my_range object index out of range')

    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

CPython C代码实现

static int
range_contains_long(rangeobject *r, PyObject *ob)
{
    int cmp1, cmp2, cmp3;
    PyObject *tmp1 = NULL;
    PyObject *tmp2 = NULL;
    PyObject *zero = NULL;
    int result = -1;

    zero = PyLong_FromLong(0);
    if (zero == NULL) /* MemoryError in int(0) */
        goto end;

    /* Check if the value can possibly be in the range. */

    cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
    if (cmp1 == -1)
        goto end;
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    }
    else { /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }

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

    /* Check that the stride does not invalidate ob's membership. */
    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);
  end:
    Py_XDECREF(tmp1);
    Py_XDECREF(tmp2);
    Py_XDECREF(zero);
    return result;
}

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

最佳实践

利用range对象特性

在需要处理连续整数序列时，优先使用range对象，而非手动创建列表，这样可以节省内存，提升性能。

注意类型匹配

当对range对象进行成员检查时，要确保检查的对象为整数类型，否则可能会触发较慢的迭代搜索。

常见问题

非整数类型检查慢

若检查的对象并非整数类型（如Decimal），range对象会回退到迭代搜索，这会显著降低性能。例如：

import sys
from decimal import Decimal

print(sys.maxsize in range(sys.maxsize))  # 很快
print(Decimal(sys.maxsize) in range(sys.maxsize))  # 很慢

不同Python版本差异

虽然CPython 3.2+和PyPy 3.x版本对range.__contains__进行了优化，但不能保证所有Python实现都具备此优化，使用时需留意。