为什么Python 3中的“1000000000000000范围（1000000000000001）”这么快？

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

如果您的数字是其范围的一部分，该对象还实现#0钩子和计算。计算是一个（接近）恒定时间操作^*。永远不需要扫描范围内所有可能的整数。

从#0对象留档：

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

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

class my_range:def __init__(self, start, stop=None, step=1, /):if stop is None:start, stop = 0, startself.start, self.stop, self.step = start, stop, stepif step < 0:lo, hi, step = stop, start, -stepelse:lo, hi = start, stopself.length = 0 if lo > hi else ((hi - lo - 1) // step) + 1
def __iter__(self):current = self.startif self.step < 0:while current > self.stop:yield currentcurrent += self.stepelse:while current < self.stop:yield currentcurrent += self.step
def __len__(self):return self.length
def __getitem__(self, i):if i < 0:i += self.lengthif 0 <= i < self.length:return self.start + i * self.stepraise IndexError('my_range object index out of range')
def __contains__(self, num):if self.step < 0:if not (self.stop < num <= self.start):return Falseelse:if not (self.start <= num < self.stop):return Falsereturn (num - self.start) % self.step == 0

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

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

*近常量时间，因为Python整数是无界的，所以数学操作也会随着N的增长而随着时间的增长，因此这是一个O（log N）操作。由于它都在优化的C代码中执行，并且Python将整数值存储在30位块中，因此由于此处涉及的整数的大小，你会在看到任何性能影响之前运行内存溢出。

为了补充Martijn的答案，这是的来源的相关部分（在C中，因为范围对象是用本机代码编写的）：

static intrange_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 iteratingreturn any(obj == x for x in rangeObj)
def range_contains_long (r, num):if r.step > 0:# positive step: r.start <= num < r.stopcmp2 = r.start <= numcmp3 = num < r.stopelse:# negative step: r.start >= num > r.stopcmp2 = num <= r.startcmp3 = r.stop < num
# outside of the range boundariesif not cmp2 or not cmp3:return False
# num must be on a valid step inside the boundariesreturn (num - r.start) % r.step == 0

使用来源，卢克！

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

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

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

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

下面包含完整的C代码，由于内存管理和引用计数细节，这有点冗长，但基本思想是存在的：

static intrange_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 intrange_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)

这里的基本误解是认为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]         # indexable3>>> len(a)       # sized5>>> 3 in a       # membershipTrue>>> reversed(a)  # reversible<range_iterator at 0x101cd2360>>>> a.index(3)   # implements 'index'3>>> a.count(3)   # implements 'count'1

range和list之间的区别在于range是懒惰或动态序列；它不记得它的所有值，它只记得它的start、stop和step，并在__getitem__上按需创建值。

（顺便说一句，如果你print(iter(a))，你会注意到range使用了与list相同的listiterator类型。这是如何工作的？listiterator没有使用list的任何特殊之处，除了它提供了__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仍然是生成器吗？测试1是否应该导致它迭代并消耗直到1（或直到第一个值>= 1）的所有值？

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

>>> 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.__contains__，为什么它不是在2.7中添加到xrange.__contains__：

首先，正如Ashwini Chaudhary发现的那样，问题1766304被显式打开以优化[x]range.__contains__。为此，一个补丁是接受并签到3.2，但没有向后移植到2.7，因为“xrange已经这样做了很长时间，我看不出这么晚提交补丁有什么好处。

同时：

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

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

这不是完全正确的；xrange对象实际上支持一些其他自动索引和len、^*（包括__contains__（通过线性搜索））的东西。但当时没有人认为值得让它们成为完整的序列。

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

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

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

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

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

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

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

由于优化-很容易将给定的整数与范围的min和max进行比较。

但是：

Decimal(sys.maxsize) in range(sys.maxsize)是相当缓慢

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

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

太长别读

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

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

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

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

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

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

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

TLDR；range是一个算术序列，因此它可以非常容易地计算对象是否在那里。如果它是非常快速的列表，它甚至可以获得它的索引。

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