为什么Python 3中的“1000000000000000 in range（1000000000000001）”速度如此之快？

据我所知，range（）函数实际上是Python 3中的一种对象类型，它动态生成其内容，类似于生成器。

在这种情况下，我预计下一行将花费大量时间，因为为了确定1万亿是否在该范围内，必须生成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中是一个完整的序列意味着什么，以及关于Python实现中__contains_函数优化的潜在不一致性的一些信息/警告。abarnert的另一个答案更为详细，并为那些对Python 3优化背后的历史感兴趣的人提供了链接（以及Python 2中xrange的优化不足）。poke和wim的答案为感兴趣的人提供了相关的C源代码和解释。

当前回答

使用来源，卢克！

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

检查数字是否介于开始和停止之间，以及检查步幅值是否“超过”我们的数字。

例如，994在范围（41000，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)

2015-05-06 15:41:18

其他回答

太长，读不下去了范围是一个算术级数，因此它可以非常容易地计算对象是否存在。它甚至可以得到它的索引，如果它真的像列表一样快速。

2020-10-09 16:29:58

这里的根本误解是认为射程是一个发生器。事实并非如此。事实上，它不是任何类型的迭代器。

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

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

实际的范围是一个序列，就像一个列表。你甚至可以测试一下：

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

范围和列表的区别在于，范围是一个惰性或动态序列；它不记得所有的值，只记得开始、停止和步骤，并根据需要在getitem上创建值。

（顺便说一句，如果您打印（iter（a）），您会注意到range使用与list相同的listiterator类型。这是如何工作的？listiterator除了提供了__getitem_的C实现之外，并没有使用任何关于list的特殊功能，所以它也适用于range。）

现在，没有什么能说明序列__事实上，contains必须是常数时间，对于像list这样的序列的明显例子，它不是。但没有什么能说明这是不可能的。而且实现射程更容易__包含只是在数学上检查它（（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是否仍在生成器中？对1的测试是否会导致它迭代并消耗所有值，直到1（或直到第一个值>=1）？

2015-05-06 16:01:17

其他答案已经很好地解释了这一点，但我想提供另一个实验来说明距离物体的性质：

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

正如您所看到的，范围对象是一个记住其范围的对象，可以多次使用（即使在对其进行迭代时），而不仅仅是一个一次性生成器。

2015-05-06 16:04:37

如果您想知道为什么要将此优化添加到范围中__contains_，以及为什么没有将其添加到xrange中__包含2.7中的_：

首先，正如Ashwini Chaudhary所发现的，1766304期被明确地开放，以优化[x]范围__包含_。这个补丁已经被接受并以3.2的价格签入，但没有被移植到2.7，因为“xrange已经这么长时间了，我看不出它能让我们这么晚才提交补丁。”

同时：

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

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

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

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

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

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

**第一个版本实际上重新实现了它，并错误地获得了详细信息，例如，它将在范围（5）==False中为您提供MyIntSubclass（2）。但Daniel Stutzbach的补丁更新版本恢复了以前的大部分代码，包括回退到3.2之前的通用、缓慢的_PySequence_IterSearch__当优化不适用时，contains被隐式使用。

2015-05-06 21:42:53