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

技术背景

在Python 3中，range() 函数返回的是一个 range 对象，它与Python 2中的 xrange 类似，是一种可迭代对象。很多人认为 range() 函数像生成器一样，会在迭代时逐个生成值。因此，当使用 in 操作符检查一个非常大的数是否在 range 对象中时，可能会预期需要很长时间，因为要生成大量的值来进行判断。然而，实际情况是这个操作几乎是瞬间完成的，无论 range 对象的范围有多大。

实现步骤

理解 range 对象的特性

range 对象是一个智能的序列对象，它并不立即生成所有的值，而是在需要时根据起始值、结束值和步长来计算每个值。它实现了 __contains__ 方法，该方法会通过数学计算来判断一个数是否在 range 对象的范围内，而不是逐个生成值进行比较。

模拟 range 对象的实现

以下是一个简化的 my_range 类，用于模拟 range 对象的基本功能：

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

分析 __contains__ 方法的逻辑

__contains__ 方法的核心逻辑是先检查数是否在 range 对象的起始值和结束值之间，然后检查该数与起始值的差值是否能被步长整除。如果这两个条件都满足，则该数在 range 对象中。

核心代码

以下是CPython中 range 对象的 __contains__ 方法的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_contains_long 函数进行数学计算；否则，使用 _PySequence_IterSearch 函数进行迭代搜索。

最佳实践

利用 range 对象的性能优势

在需要检查一个数是否在某个范围内时，优先使用 range 对象，而不是手动生成一个列表。例如：

number = 1000000000000000
if number in range(1000000000000001):
    print("Number is in the range.")

注意 range 对象的类型检查

当使用非整数类型的值进行检查时，range 对象会使用迭代搜索，性能会显著下降。因此，在使用 in 操作符时，确保传入的是整数类型的值。

常见问题

为什么非整数类型的检查会变慢？

当传入的对象不是整数类型时，range 对象无法使用数学计算来判断，而是会使用迭代搜索，逐个生成值并进行比较，因此性能会变差。例如：

number = 1000000000000000.0
if number in range(1000000000000001):
    print("Number is in the range.")

Python 3是否保证 range 对象的 __contains__ 方法始终是高效的？

虽然CPython 3.2+ 和 PyPy 3.x 版本对 range 对象的 __contains__ 方法进行了优化，但Python语言本身并没有明确保证这一点。其他Python实现（如IronPython）可能没有进行相同的优化，因此在不同的实现中可能会有不同的性能表现。