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

Python 3 range() 对象不会立即产生数字；它是一个智能的sequence object，可以按需生成数字。它只包含您的开始、停止和步长值，然后当您迭代对象时，每次迭代都会计算下一个整数。

该对象还实现了 object.__contains__ hook，并且计算您的数字是否在其范围内。计算是（接近）恒定时间操作^*。永远不需要扫描范围内所有可能的整数。

从 range() object documentation：

范围类型优于常规列表或元组的优点是范围对象将始终占用相同（少量）的内存，无论它代表的范围大小（因为它只存储开始、停止和步长值，根据需要计算单个项目和子范围）。

因此，您的 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

这仍然缺少真正的 range() 支持的几件事（例如 .index() 或 .count() 方法、散列、相等测试或切片），但应该会给您一个想法。

我还简化了 __contains__ 实现，只关注整数测试；如果您给一个真正的 range() 对象一个非整数值（包括 int 的子类），则会启动慢速扫描以查看是否存在匹配项，就像您对所有对象的列表使用包含测试一样包含的值。这样做是为了继续支持其他恰好支持整数相等测试但预计也不支持整数算术的数字类型。请参阅实施遏制测试的原始 Python issue。

接近恒定时间，因为 Python 整数是无界的，所以数学运算也会随着 N 的增长而增长，这使得它成为 O(log N) 运算。由于它全部在优化的 C 代码中执行，并且 Python 将整数值存储在 30 位块中，因此由于此处涉及的整数的大小，您会在看到任何性能影响之前耗尽内存。

---

这里的基本误解是认为 range 是一个生成器。它不是。事实上，它不是任何类型的迭代器。

你可以很容易地告诉这个：

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

如果它是一个生成器，迭代一次就会耗尽它：

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

range 实际上是一个序列，就像一个列表。你甚至可以测试这个：

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

这意味着它必须遵循序列的所有规则：

>>> a[3]         # indexable
3
>>> len(a)       # sized
5
>>> 3 in a       # membership
True
>>> reversed(a)  # reversible
<range_iterator at 0x101cd2360>
>>> a.index(3)   # implements 'index'
3
>>> a.count(3)   # implements 'count'
1

range 和 list 的区别在于 range 是 lazy 或 dynamic 序列；它不会记住它的所有值，它只记住它的 start、stop 和 step，并在 __getitem__ 上按需创建值。

（附带说明一下，如果您是 print(iter(a))，您会注意到 range 使用与 list 相同的 listiterator 类型。这是如何工作的？listiterator 没有使用任何关于 {4 } 除了它提供了 __getitem__ 的 C 实现，因此它也适用于 range。）

现在，没有什么说 Sequence.__contains__ 必须是常数时间 - 事实上，对于像 list 这样的序列的明显示例，它不是。但是没有什么可以说它不可能。并且实现 range.__contains__ 以仅在数学上检查它（(val - start) % step，但处理负面步骤有一些额外的复杂性）比实际生成和测试所有值更容易，所以为什么不应该 它做得更好吗？

但是语言中似乎没有任何东西可以保证这会发生。正如 Ashwini Chaudhari 指出的那样，如果你给它一个非整数值，而不是转换为整数并进行数学测试，它将退回到迭代所有值并一一比较它们。仅仅因为 CPython 3.2+ 和 PyPy 3.x 版本恰好包含这种优化，而且这显然是一个好主意并且很容易做到，IronPython 或 NewKickAssPython 3.x 没有理由不能忽略它。 （事实上，CPython 3.0-3.1 并没有包含它。）

如果 range 实际上是一个生成器，例如 my_crappy_range，那么以这种方式测试 __contains__ 是没有意义的，或者至少它有意义的方式并不明显。如果您已经迭代了前 3 个值，那么 1 仍然是 in 生成器吗？对 1 的测试是否应该导致它迭代并使用直到 1（或直到第一个值 >= 1）的所有值？

---

使用 source，卢克！

在 CPython 中，range(...).__contains__（一个方法包装器）最终将委托给一个简单的计算，该计算检查该值是否可能在该范围内。这里速度的原因是我们使用关于边界的数学推理，而不是范围对象的直接迭代。解释使用的逻辑：

检查数字是否在开始和停止之间，并检查步幅值是否“跨过”我们的数字。

例如，994 位于 range(4, 1000, 2) 中，因为：

4 <= 994 < 1000，并且 (994 - 4) % 2 == 0。

完整的 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);
}

the line 中提到了这个想法的“肉”：

/* result = ((int(ob) - start) % step) == 0 */ 

最后一点 - 查看代码片段底部的 range_contains 函数。如果确切的类型检查失败，那么我们不使用所描述的聪明算法，而是使用 _PySequence_IterSearch 回退到范围的愚蠢迭代搜索！您可以在解释器中检查此行为（我在这里使用 v3.5.0）：

>>> x, r = 1000000000000000, range(1000000000000001)
>>> class MyInt(int):
...     pass
... 
>>> x_ = MyInt(x)
>>> x in r  # calculates immediately :) 
True
>>> x_ in r  # iterates for ages.. :( 
^\Quit (core dumped)

---

添加到 Martijn 的答案中，这是 the source 的相关部分（在 C 中，因为范围对象是用本机代码编写的）：

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);
}

因此，对于 PyLong 对象（在 Python 3 中为 int），它将使用 range_contains_long 函数来确定结果。该函数本质上检查 ob 是否在指定范围内（尽管它在 C 中看起来有点复杂）。

如果它不是 int 对象，它会退回到迭代直到找到值（或没有）。

整个逻辑可以像这样翻译成伪 Python：

def range_contains (rangeObj, obj):
    if isinstance(obj, int):
        return range_contains_long(rangeObj, obj)

    # default logic by iterating
    return any(obj == x for x in rangeObj)

def range_contains_long (r, num):
    if r.step > 0:
        # positive step: r.start <= num < r.stop
        cmp2 = r.start <= num
        cmp3 = num < r.stop
    else:
        # negative step: r.start >= num > r.stop
        cmp2 = num <= r.start
        cmp3 = r.stop < num

    # outside of the range boundaries
    if not cmp2 or not cmp3:
        return False

    # num must be on a valid step inside the boundaries
    return (num - r.start) % r.step == 0

---

如果您想知道为什么将此优化添加到 range.__contains__，以及为什么在 2.7 中没有将它添加到 xrange.__contains__：

首先，正如 Ashwini Chaudhary 所发现的，issue 1766304 被明确打开以优化 [x]range.__contains__。对此的补丁是 accepted and checked in for 3.2，但没有向后移植到 2.7，因为“xrange 的行为已经很长时间了，我看不出我们这么晚才提交补丁有什么好处。” （那时 2.7 差不多了。）

同时：

最初，xrange 是一个不完全序列的对象。正如 the 3.1 docs 所说：

Range 对象的行为很少：它们只支持索引、迭代和 len 函数。

这并不完全正确。 xrange 对象实际上支持索引和 len,^* 自动附带的其他一些东西，包括 __contains__（通过线性搜索）。但当时没有人认为值得制作完整的序列。

然后，作为实现 Abstract Base Classes PEP 的一部分，重要的是要弄清楚哪些内置类型应该被标记为实现了哪些 ABC，并且 xrange/range 声称实现了 collections.Sequence，尽管它仍然只处理同样的“很少的行为”。在 issue 9213 之前没有人注意到这个问题。该问题的补丁不仅将 index 和 count 添加到 3.2 的 range 中，还重新设计了优化的 __contains__（与 index 共享相同的数学，并直接由 { 8}).^** This change 也适用于 3.2，并且没有向后移植到 2.x，因为“这是一个添加新方法的错误修复”。 （此时，2.7 已经过了 rc 状态。）

因此，有两次机会将此优化向后移植到 2.7，但都被拒绝了。

_{* 实际上，您甚至可以通过单独的索引免费获得迭代，但是 in 2.3 xrange 对象有一个自定义迭代器。}

_{** 第一个版本实际上重新实现了它，但细节错误——例如，它会给你 MyIntSubclass(2) in range(5) == False。但 Daniel Stutzbach 的补丁更新版本恢复了大部分以前的代码，包括回退到 3.2 之前的 range.__contains__ 在优化不适用时隐式使用的通用、缓慢的 _PySequence_IterSearch。}

---

其他答案已经很好地解释了它，但我想提供另一个实验来说明范围对象的性质：

>>> r = range(5)
>>> for i in r:
        print(i, 2 in r, list(r))
        
0 True [0, 1, 2, 3, 4]
1 True [0, 1, 2, 3, 4]
2 True [0, 1, 2, 3, 4]
3 True [0, 1, 2, 3, 4]
4 True [0, 1, 2, 3, 4]

如您所见，range 对象是一个可以记住其范围并且可以多次使用（甚至在对其进行迭代时）的对象，而不仅仅是一次性生成器。

---

这完全是关于评估的惰性方法和range的一些额外优化。范围内的值在实际使用之前不需要计算，甚至由于额外的优化而进一步计算。

顺便说一句，您的整数不是那么大，请考虑 sys.maxsize

sys.maxsize in range(sys.maxsize) 相当快

由于优化 - 很容易将给定的整数与范围的最小值和最大值进行比较。

但：

Decimal(sys.maxsize) in range(sys.maxsize) 很慢。

（在这种情况下，range中没有优化，所以如果python收到意外的Decimal，python会比较所有数字）

您应该了解实现细节，但不应依赖它，因为将来可能会发生变化。

---

TL;博士

range() 返回的对象实际上是一个 range 对象。该对象实现了迭代器接口，因此您可以按顺序迭代其值，就像生成器、列表或元组一样。

但它也实现了 __contains__ 接口，当对象出现在 in 运算符的右侧时，该接口实际上会被调用。 __contains__() 方法返回 in 左侧的项目是否在对象中的 bool。由于 range 对象知道它们的边界和步幅，这在 O(1) 中很容易实现。

---

由于优化，很容易将给定的整数与最小和最大范围进行比较。在 Python3 中 range() 函数如此之快的原因是，这里我们使用数学推理来计算边界，而不是直接迭代 range 对象。所以为了解释这里的逻辑：

检查数字是否在开始和停止之间。

检查步长精度值是否不超过我们的数字。

举个例子，997 在 (4, 1000, 3) 范围内，因为：4 <= 997 < 1000，并且 (997 - 4) % 3 == 0。

---

对较大的 x 值尝试 x-1 in (i for i in range(x))，它使用生成器推导来避免调用 range.__contains__ 优化。

---

TLDR; range 是一个算术级数，因此它可以很容易地计算出对象是否存在。如果它像列表一样很快，它甚至可以得到它的索引。

---