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

Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3?

提问by Rick supports Monica

It is my understanding that the range()function, which is actually an object type in Python 3, generates its contents on the fly, similar to a generator.

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

This being the case, I would have expected the following line to take an inordinate amount of time, because in order to determine whether 1 quadrillion is in the range, a quadrillion values would have to be generated:

在这种情况下，我预计以下行会花费过多的时间，因为为了确定 1 千万亿是否在范围内，必须生成千万亿值：

1000000000000000 in range(1000000000000001)

Furthermore: it seems that no matter how many zeroes I add on, the calculation more or less takes the same amount of time (basically instantaneous).

此外：似乎无论我添加多少个零，计算或多或少都需要相同的时间（基本上是瞬时的）。

I have also tried things like this, but the calculation is still almost instant:

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

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

If I try to implement my own range function, the result is not so nice!!

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

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

What is the range()object doing under the hood that makes it so fast?

是什么range()使得它如此之快的引擎盖下做对象？

---

---

Martijn Pieters' answerwas chosen for its completeness, but also see abarnert's first answerfor a good discussion of what it means for rangeto be a full-fledged sequencein Python 3, and some information/warning regarding potential inconsistency for __contains__function optimization across Python implementations. abarnert's other answergoes into some more detail and provides links for those interested in the history behind the optimization in Python 3 (and lack of optimization of xrangein Python 2). Answers by pokeand by wimprovide the relevant C source code and explanations for those who are interested.

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

采纳答案by Martijn Pieters

The Python 3 range()object doesn't produce numbers immediately; it is a smart sequence objectthat produces numbers on demand. All it contains is your start, stop and step values, then as you iterate over the object the next integer is calculated each iteration.

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

The object also implements the object.__contains__hook, and calculatesif your number is part of its range. Calculating is a (near) constant time operation ^*. There is never a need to scan through all possible integers in the range.

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

From the range()object documentation:

从range()对象文档：

The advantage of the rangetype over a regular listor tupleis that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stopand stepvalues, calculating individual items and subranges as needed).

与range常规listor类型相比，该类型的优势tuple在于范围对象将始终占用相同（小）内存量，无论它表示的范围大小如何（因为它仅存储start,stop和step值，计算单个项目和子范围如所须）。

So at a minimum, your range()object would do:

所以至少，你的range()对象会做：

class my_range(object):
    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('Index out of range: {}'.format(i))

    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

This is still missing several things that a real range()supports (such as the .index()or .count()methods, hashing, equality testing, or slicing), but should give you an idea.

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

I also simplified the __contains__implementation to only focus on integer tests; if you give a real range()object a non-integer value (including subclasses of int), a slow scan is initiated to see if there is a match, just as if you use a containment test against a list of all the contained values. This was done to continue to support other numeric types that just happen to support equality testing with integers but are not expected to support integer arithmetic as well. See the original Python issuethat implemented the containment test.

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

---

---

* Nearconstant time because Python integers are unbounded and so math operations also grow in time as N grows, making this a O(log N) operation. Since it's all executed in optimised C code and Python stores integer values in 30-bit chunks, you'd run out of memory before you saw any performance impact due to the size of the integers involved here.

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

回答by poke

To add to Martijn's answer, this is the relevant part of the source(in C, as the range object is written in native code):

要补充 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);
}

So for PyLongobjects (which is intin Python 3), it will use the range_contains_longfunction to determine the result. And that function essentially checks if obis in the specified range (although it looks a bit more complex in C).

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

If it's not an intobject, it falls back to iterating until it finds the value (or not).

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

The whole logic could be translated to pseudo-Python like this:

整个逻辑可以像这样转换为伪 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

回答by wim

Use the source, Luke!

使用来源，卢克！

In CPython, range(...).__contains__(a method wrapper) will eventually delegate to a simple calculation which checks if the value can possibly be in the range. The reason for the speed here is we're using mathematical reasoning about the bounds, rather than a direct iteration of the range object. To explain the logic used:

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

1. Check that the number is between startand stop, and
2. Check that the stride value doesn't "step over" our number.

1. 检查数字是否在start和之间stop，以及
2. 检查步幅值是否“越过”我们的数字。

For example, 994is in range(4, 1000, 2)because:

例如，994是range(4, 1000, 2)因为：

1. 4 <= 994 < 1000, and
2. (994 - 4) % 2 == 0.

1. 4 <= 994 < 1000， 和
2. (994 - 4) % 2 == 0.

The full C code is included below, which is a bit more verbose because of memory management and reference counting details, but the basic idea is there:

完整的 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 "meat" of the idea is mentioned in the line:

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

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

As a final note - look at the range_containsfunction at the bottom of the code snippet. If the exact type check fails then we don't use the clever algorithm described, instead falling back to a dumb iteration search of the range using _PySequence_IterSearch! You can check this behaviour in the interpreter (I'm using v3.5.0 here):

最后一点 - 查看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)

回答by abarnert

The fundamental misunderstanding here is in thinking that rangeis a generator. It's not. In fact, it's not any kind of iterator.

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

You can tell this pretty easily:

你可以很容易地说出这一点：

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

If it were a generator, iterating it once would exhaust it:

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

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

What rangeactually is, is a sequence, just like a list. You can even test this:

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

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

This means it has to follow all the rules of being a sequence:

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

>>> 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

---

---

The difference between a rangeand a listis that a rangeis a lazyor dynamicsequence; it doesn't remember all of its values, it just remembers its start, stop, and step, and creates the values on demand on __getitem__.

一个之间的差range和一list在于，range是懒或动态序列; 它不记得所有的价值，它只是记住它start，stop和step，并根据需要创建的值__getitem__。

(As a side note, if you print(iter(a)), you'll notice that rangeuses the same listiteratortype as list. How does that work? A listiteratordoesn't use anything special about listexcept for the fact that it provides a C implementation of __getitem__, so it works fine for rangetoo.)

（作为旁注，如果您使用print(iter(a))，您会注意到它range使用与 相同的listiterator类型list。它是如何工作的？Alistiterator没有使用任何特殊的东西，list除了它提供了 的 C 实现__getitem__，因此它适用于range也。）

---

---

Now, there's nothing that says that Sequence.__contains__has to be constant time—in fact, for obvious examples of sequences like list, it isn't. But there's nothing that says it can'tbe. And it's easier to implement range.__contains__to just check it mathematically ((val - start) % step, but with some extra complexity to deal with negative steps) than to actually generate and test all the values, so why shouldn'tit do it the better way?

现在，没有什么说Sequence.__contains__时间必须是恒定的——事实上，对于像 这样的序列的明显例子list，它不是。但没有什么说它不可能。与实际生成和测试所有值相比，range.__contains__仅以数学方式检查它更容易实现（(val - start) % step但处理负面步骤会增加一些额外的复杂性），那么为什么不应该以更好的方式来实现呢？

But there doesn't seem to be anything in the language that guaranteesthis will happen. As Ashwini Chaudhari points out, if you give it a non-integral value, instead of converting to integer and doing the mathematical test, it will fall back to iterating all the values and comparing them one by one. And just because CPython 3.2+ and PyPy 3.x versions happen to contain this optimization, and it's an obvious good idea and easy to do, there's no reason that IronPython or NewKickAssPython 3.x couldn't leave it out. (And in fact CPython 3.0-3.1 didn'tinclude it.)

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

---

---

If rangeactually were a generator, like my_crappy_range, then it wouldn't make sense to test __contains__this way, or at least the way it makes sense wouldn't be obvious. If you'd already iterated the first 3 values, is 1still inthe generator? Should testing for 1cause it to iterate and consume all the values up to 1(or up to the first value >= 1)?

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

回答by Stefan Pochmann

The other answers explained it well already, but I'd like to offer another experiment illustrating the nature of range objects:

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

>>> 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]

As you can see, a range object is an object that remembers its range and can be used many times (even while iterating over it), not just a one-time generator.

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

回答by abarnert

If you're wondering whythis optimization was added to range.__contains__, and why it wasn'tadded to xrange.__contains__in 2.7:

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

First, as Ashwini Chaudhary discovered, issue 1766304was opened explicitly to optimize [x]range.__contains__. A patch for this was accepted and checked in for 3.2, but not backported to 2.7 because "xrange has behaved like this for such a long time that I don't see what it buys us to commit the patch this late." (2.7 was nearly out at that point.)

首先，正如 Ashwini Chaudhary 发现的那样，问题 1766304被明确打开以优化[x]range.__contains__. 一个补丁被接受并签入 3.2，但没有向后移植到 2.7 ，因为“xrange 的行为已经很长时间了，我不明白这么晚提交补丁会给我们带来什么。” （那时 2.7 快要结束了。）

Meanwhile:

同时：

Originally, xrangewas a not-quite-sequence object. As the 3.1 docssay:

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

Range objects have very little behavior: they only support indexing, iteration, and the lenfunction.

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

This wasn't quite true; an xrangeobject actually supported a few other things that come automatically with indexing and len,^*including __contains__(via linear search). But nobody thought it was worth making them full sequences at the time.

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

Then, as part of implementing the Abstract Base ClassesPEP, it was important to figure out which builtin types should be marked as implementing which ABCs, and xrange/rangeclaimed to implement collections.Sequence, even though it still only handled the same "very little behavior". Nobody noticed that problem until issue 9213. The patch for that issue not only added indexand countto 3.2's range, it also re-worked the optimized __contains__(which shares the same math with index, and is directly used by count).^**This changewent in for 3.2 as well, and was not backported to 2.x, because "it's a bugfix that adds new methods". (At this point, 2.7 was already past rc status.)

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

So, there were two chances to get this optimization backported to 2.7, but they were both rejected.

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

---

---

_{* In fact, you even get iteration for free with indexing alone, but in 2.3xrangeobjects got a custom iterator.}

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

_{** The first version actually reimplemented it, and got the details wrong—e.g., it would give you MyIntSubclass(2) in range(5) == False. But Daniel Stutzbach's updated version of the patch restored most of the previous code, including the fallback to the generic, slow _PySequence_IterSearchthat pre-3.2 range.__contains__was implicitly using when the optimization doesn't apply.}

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

回答by S?awomir Lenart

It's all about a lazy approachto the evaluation and some extra optimizationof range. Values in ranges don't need to be computed until real use, or even further due to extra optimization.

这是关于一个偷懒的办法来评估和一些额外的优化的range。在真正使用之前不需要计算范围内的值，或者由于额外的优化甚至进一步计算。

By the way, your integer is not such big, consider sys.maxsize

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

sys.maxsize in range(sys.maxsize)is pretty fast

sys.maxsize in range(sys.maxsize)很快

due to optimization - it's easy to compare given integer just with min and max of range.

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

but:

但：

Decimal(sys.maxsize) in range(sys.maxsize)is pretty slow.

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

(in this case, there is no optimization in range, so if python receives unexpected Decimal, python will compare all numbers)

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

You should be aware of an implementation detail but should not be relied upon, because this may change in the future.

你应该知道一个实现细节，但不应该依赖它，因为这在未来可能会改变。

回答by RBF06

TL;DR

TL; 博士

The object returned by range()is actually a rangeobject. This object implements the iterator interface so you can iterate over its values sequentially, just like a generator, list, or tuple.

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

But it alsoimplements the __contains__interface which is actually what gets called when an object appears on the right hand side of the inoperator. The __contains__()method returns a boolof whether or not the item on the left-hand-side of the inis in the object. Since rangeobjects know their bounds and stride, this is very easy to implement in O(1).

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

回答by Naruto

1. Due to optimization, it is very easy to compare given integers just with min and max range.
2. The reason that range()function is so fast in Python3 is that here we use mathematical reasoning for the bounds, rather than a direct iteration of the range object.
3. So for explaining the logic here:
   • Check whether the number is between the start and stop.
   • Check whether the step precision value doesn't go over our number.

4. Take an example, 997 is in range(4, 1000, 3)because:

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

1. 由于优化，很容易将给定的整数与最小和最大范围进行比较。
2. Python3中range()函数如此之快的原因是这里我们使用数学推理来确定边界，而不是直接迭代 range 对象。
3. 所以为了解释这里的逻辑：
   • 检查数字是否在开始和停止之间。
   • 检查步进精度值是否超过我们的数字。

4. 举个例子，997 在 range(4, 1000, 3) 内，因为：

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

回答by benjimin

Try x-1 in (i for i in range(x))for large xvalues, which uses a generator comprehension to avoid invoking the range.__contains__optimisation.

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