为什么在Python 3中“1000000000000000（1000000000000001）”这么快？
我的理解是， range()函数实际上是Python 3中的一个对象types ，它在运行中生成其内容，类似于生成器。
在这种情况下，我预料到下面这一行需要花费过多的时间，因为为了确定是否在这个范围内，需要生成四十亿个值：
1000000000000000 in range(1000000000000001)
此外：似乎不pipe我添加了多less零，计算或多或less需要相同的时间量（基本上是瞬时的）。
我也尝试过这样的事情，但计算仍然几乎是即时的：
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
如果我试图实现我自己的范围function，结果是不是很好！
def my_crappy_range(N): i = 0 while i < N: yield i i += 1 return
range()对象在引擎盖下做什么使它如此之快？
编辑：这已经certificate是一个比我预期的更细致的话题 – 似乎有一段历史背后的优化range() 。
Martijn Pieters的答案是为了它的完整性而被选中的，但是也可以看一下abarnert的第一个答案 ，那就是在Python 3中对range是一个完整序列意味着什么，以及关于__contains__函数优化的潜在不一致性的一些信息/警告Python实现。 abarnert的其他答案更详细一些，并为那些对Python 3优化背后的历史感兴趣的人提供链接（并且缺乏Python 2中的xrange优化）。 由poke和wim提供的答案为有兴趣的人提供了相关的C源代码和解释。
Python 3 range()对象不会立即产生数字; 这是一个聪明的序列对象，可以根据需要产生数字。 它包含的是你的开始，停止和步进值，然后当迭代对象时，每次迭代计算下一个整数。
该对象还实现了object.__contains__ hook ，并计算您的数字是否是其范围的一部分。 计算是一个O（1）常数时间操作。 从来没有需要扫描范围内的所有可能的整数。
从range()对象文档 ：
rangetypes优于常规list或tuple的优点在于，范围对象总是会占用相同（小）的内存量，而不pipe它所表示的范围的大小（因为它只存储start，stop和step值，根据需要计算单个项目和子范围）。
所以至less你的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 = stop, start else: lo, hi = start, stop self.length = ((hi - lo - 1) // abs(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
这仍然缺less一些真正的range()支持的东西（例如.index()或.count()方法，哈希，相等性testing或切片），但应该给你一个想法。
我也简化了__contains__实现，只关注整型testing; 如果给实际的range()对象一个非整数值（包括int子类），就会启动一个慢速扫描来查看是否存在匹配，就像对包含所有值的列表使用包含testing一样。 这样做是为了继续支持其他刚好支持用整数进行等式testing的数字types，但也不希望支持整数算术。 查看实施遏制testing的原始Python问题 。
这里最基本的误解就是认为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是一个序列，就像一个列表。 你甚至可以testing这个：
>>> 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是一个懒惰或dynamic的序列; 它不记得它的所有值，它只是记住它的start ， stop和step ，并在__getitem__上按需创build值。
（作为一个方面说明，如果你print(iter(a)) ，你会注意到range使用与list相同的listiteratortypes。这是如何工作的？ listiterator者不使用关于list任何特殊的东西，它提供了__getitem__的C实现，所以它也适用于range 。）
现在，没有什么说Sequence.__contains__必须是恒定的 – 事实上，对于像list这样的序列的明显例子，事实并非如此。 但没有什么说不可能 。 而且实现range.__contains__更容易range.__contains__只是在math上（ (val - start) % step检查它，但是处理负面步骤需要一些额外的复杂性，而不是实际生成和testing所有的值，为什么不这样做呢？这是更好的方法？
但是在语言上似乎没有任何东西可以保证这种情况发生。 正如Ashwini Chaudhari所指出的那样，如果你给它一个非整数值，而不是转换为整数并进行mathtesting，它将回退到迭代所有值并逐一比较它们。 只是因为CPython 3.2+和PyPy 3.x版本碰巧包含了这个优化，而且这是一个明显的好主意，并且很容易做，所以IronPython或者NewKickAssPython 3.x没有理由不把它抛出去。 （实际上CPython 3.0-3.1 没有包含它。）
如果range实际上是一个生成器，比如my_crappy_range ，那么用这种方法testing__contains__是没有意义的，至less它的意义不明显。 如果你已经迭代了前3个值，那么1仍然in发生器中？ 应该testing1会导致它迭代并消耗所有值最多为1 （或直到第一个值>= 1 ）？
使用源码 ，卢克！
在CPython中， range(...).__contains__ （方法包装器）将最终委托给一个简单的计算，检查值是否可能在范围内。 这里速度的原因是我们使用关于边界的math推理，而不是范围对象的直接迭代 。 解释使用的逻辑：
- 检查数字是在
start和stop之间，并且 - 检查步幅值是否“超越”我们的数字。
例如， 994在range(4, 1000, 2) 994 range(4, 1000, 2)因为：
-
4 <= 994 < 1000， -
(994 - 4) % 2 == 0。
完整的C代码包含在下面，由于内存pipe理和引用计数的细节，这个代码更加冗长，但是其基本思想是：
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); }
这个想法的“肉” 在行中提到：
/* result = ((int(ob) - start) % step) == 0 */
作为最后的注意事项 – 查看代码片段底部的range_contains函数。 如果确切的types检查失败，那么我们不使用所描述的巧妙的algorithm，而是使用_PySequence_IterSearch返回到范围的一个愚蠢的迭代search！ 你可以在解释器中检查这个行为（我在这里使用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的答案，这是源的相关部分（在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是否在指定的范围内（尽pipe在C中看起来更复杂）。
如果它不是一个int对象，它将回落到迭代直到find值（或不）。
整个逻辑可以像这样转换成伪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所发现的那样， 问题1766304被明确地打开以优化[x]range.__contains__ 。 这个补丁已经被接受和检查了3.2 ，但没有回到2.7，因为“xrange已经这么长时间地performance出来了，我没有看到它买了我们这个迟到的补丁。 （当时2.7差不多了）
与此同时：
最初， xrange是一个不完全顺序的对象。 正如3.1文档所说：
Range对象的行为很less：它们只支持索引，迭代和
len函数。
这不是真的; 一个xrange对象实际上支持一些其他的东西，这些东西会自动带有索引和len ， *包括__contains__ （通过线性search）。 但是当时没有人认为这是值得让他们完整的序列。
然后，作为实现抽象基类 PEP的一部分，找出哪些内buildtypes应被标记为实现哪些ABCs，以及声称实现collections.Sequence xrange / range是非常重要的。即使它仍然只处理相同的“非常小小的行为“。 没有人注意到这个问题，直到问题9213 。 针对该问题的补丁不仅增加了index和count到3.2的range ，还重新__contains__了优化后的__contains__ （它与index共享相同的mathindex ，并直接被count ）。 ** 这个变化也是3.2，而且没有反向到2.x，因为“这是一个错误修正，增加了新的方法”。 （此时，2.7已经过了rc状态。）
所以有两次机会让这个优化回到2.7，但他们都被拒绝了。
*事实上，你甚至可以免费使用len和indexing进行迭代，但在2.3 xrange对象中有一个自定义的迭代器。 然后他们在3.x中丢失了，它使用与list相同的listiteratortypes。
**第一个版本实际上重新实现它，并得到了错误的细节，例如，它会给你MyIntSubclass(2) in range(5) == False 。 但Daniel Stutzbach修补程序的更新版本恢复了大部分以前的代码，包括后退到通用的慢速_PySequence_IterSearch ，在3.2版本以前的版本包含_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]
正如你所看到的，范围对象是一个记住它的范围的对象，可以被多次使用（即使在迭代它的时候），而不仅仅是一次性的生成器。
