为什么“1000000000000000 in range(100000000000001)”在 Python 3 中速度如此之快？-IT科技

摘要：问题描述：据我理解，该range()函数实际上是Python 3 中的对象类型，它可以动态生成其内容，类似于生成器。在这种情况下，我本来预计下面这行代码会花费大量的时间，因为为了确定 1 千万亿是否在范围内，必须生成千万亿个值：1_000_000_000_000_000 in range(1_000_000_...

问题描述：

据我理解，该range()函数实际上是Python 3 中的对象类型，它可以动态生成其内容，类似于生成器。

在这种情况下，我本来预计下面这行代码会花费大量的时间，因为为了确定 1 千万亿是否在范围内，必须生成千万亿个值：

1_000_000_000_000_000 in range(1_000_000_000_000_001)

此外：似乎无论我添加多少个零，计算所花费的时间大致相同（基本上是瞬间）。

我也尝试过这样的事情，但计算仍然几乎是即时的：

# count by tens
1_000_000_000_000_000_000_000 in range(0,1_000_000_000_000_000_000_001,10)

如果我尝试实现自己的范围函数，结果就不那么好了！

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

range()引擎盖下的物体在做什么使其速度如此之快？

选择Martijn Pieters 的答案是因为它的完整性，但也可以参见abarnert 的第一个答案，其中很好地讨论了Python 3 中range完整序列__contains__的含义，以及有关跨 Python 实现的函数优化的潜在不一致的一些信息/警告。abarnert的另一个答案xrange更详细地介绍了一些内容，并为那些对 Python 3 中优化背后的历史（以及Python 2 中缺乏优化）感兴趣的人提供了链接。poke和wim 的答案为感兴趣的人提供了相关的 C 源代码和解释。

解决方案 1：

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

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

来自range()对象文档：

range该类型相对于常规list或的优势tuple在于，范围对象总是占用相同（小）量的内存，无论它所代表的范围的大小如何（因为它仅存储start、stop和step值，根据需要计算单个项目和子范围）。

因此，你的对象至少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 问题。

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

解决方案 2：

这里最根本的误解是认为它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

rangea和 a之间的区别list在于 arange是惰性或动态序列；它不会记住其所有值，而只会记住其start、stop和step，并在上根据需要创建值__getitem__。

（附注：如果您print(iter(a))，您会注意到range使用listiterator与相同的类型list。它是如何工作的？除了它提供了的 C 实现之外，Alistiterator没有使用的任何特殊之处，因此它也可以很好地工作。）list`__getitem__`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）？

解决方案 3：

使用来源，卢克！

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

检查数字是否介于start和之间stop，并且
检查步幅值是否“超出”我们的数字。

例如，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);
}

评论中提到了这个想法的“实质”：

/* positive steps: start <= ob < stop */
/* negative steps: stop < ob <= start */
/* 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)

解决方案 4：

为了补充 Martijn 的回答，这是源代码的相关部分（在 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对象（在intPython 3 中），它将使用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

解决方案 5：

如果你想知道为什么要添加这个优化range.__contains__，以及为什么它没有添加到xrange.__contains__2.7中：

首先，正如 Ashwini Chaudhary 发现的那样，问题 1766304是专门为优化而提出的[x]range.__contains__。针对此问题的补丁已被接受并签入 3.2 版本，但并未移植到 2.7 版本，因为“xrange这种情况已经持续了很长时间，我看不出这么晚才提交补丁对我们有什么好处。”（当时 2.7 版本几乎已经发布。）

同时：

最初，xrange是一个不完全序列的对象。正如3.1 文档所述：

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

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

然后，作为实现抽象基类PEP的一部分，重要的是要弄清楚哪些内置类型应标记为实现哪些 ABC，以及xrange/range声称实现collections.Sequence，即使它仍然只处理相同的“非常少的行为”。直到问题 9213 ，才有人注意到这个问题。该问题的补丁不仅将index和添加count到 3.2 的range，还重新设计了优化__contains__（与共享相同的数学index，并直接由count）。** 此更改也适用于 3.2，并且未反向移植到 2.x，因为“这是一个添加新方法的错误修复”。（此时，2.7 已经过了 rc 状态。）

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

事实上，您甚至可以通过索引免费获得迭代，但是在 2.3 中 xrange对象获得了自定义迭代器。

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

解决方案 6：

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

>>> 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对象是记住其范围并可多次使用（即使在对其进行迭代时）的对象，而不仅仅是一次性生成器。

解决方案 7：

这全是关于一种惰性求值方法和一些额外的优化range。范围内的值直到实际使用时才需要计算，甚至由于额外的优化而不需要进一步计算。

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

sys.maxsize in range(sys.maxsize) 非常快

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

但：

Decimal(sys.maxsize) in range(sys.maxsize) 非常慢。

（在这种情况下，没有任何优化range，因此如果 python 收到意外的 Decimal，python 将比较所有数字）

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

解决方案 8：

总结

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

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

解决方案 9：

由于优化，仅使用最小值和最大值范围就可以很容易地比较给定的整数。
Python3 中的range()函数如此之快的原因是，这里我们使用数学推理来确定边界，而不是直接迭代范围对象。
因此，这里解释一下逻辑：

检查数字是否位于开始和停止之间。
检查步长精度值是否不超过我们的数字。

举个例子，997 在范围（4，1000，3）内，因为：

4 <= 997 < 1000, and (997 - 4) % 3 == 0.

解决方案 10：

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

解决方案 11：

TLDR；
这range是一个算术序列，因此它可以非常轻松地计算出对象是否存在。如果它是列表，它甚至可以非常快速地获取它的索引。

解决方案 12：

__contains__方法直接与范围的开始和结束进行比较