问题：为什么在Python 3中“范围（1000000000000000（1000000000000001））”这么快？
据我了解，该range()函数实际上是Python 3中的一种对象类型，它会像生成器一样动态生成其内容。
在这种情况下，我本以为下一行会花费过多的时间，因为要确定1个四舍五入是否在该范围内，必须生成一个四舍五入值：
1000000000000000 in range(1000000000000001)此外：似乎无论我添加多少个零，计算多少都花费相同的时间（基本上是瞬时的）。
我也尝试过这样的事情，但是计算仍然是即时的：
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens如果我尝试实现自己的范围函数，结果将不是很好！
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的其他答案更加详细，并为那些对Python 3优化背后的历史（以及xrangePython 2中缺乏优化）感兴趣的人提供了链接。poke和wim的答案为感兴趣的人提供了相关的C源代码和说明。
回答 0
Python 3 range()对象不会立即产生数字。它是一个智能序列对象，可按需生成数字。它包含的只是您的开始，结束和步长值，然后在对对象进行迭代时，每次迭代都会计算下一个整数。
该对象还实现了object.__contains__hook，并计算您的电话号码是否在其范围内。计算是一个（近）恒定时间运算*。永远不需要扫描范围内的所有可能整数。
所述的优点
range类型通过常规list或tuple是一个范围对象将始终以相同的内存（小）数量，无论它代表的范围内的大小（因为它仅存储start，stop和step值，计算各个项目和子范围如所须）。
因此，您的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这仍然缺少实际range()支持的几项内容（例如.index()或.count()方法，哈希，相等性测试或切片），但应该可以给您一个提示。
我还简化了__contains__实现，只专注于整数测试。如果您为实物range()提供非整数值（包括的子类int），则会启动慢速扫描以查看是否存在匹配项，就好像您对所有包含的值的列表使用了包含测试一样。这样做是为了继续支持其他数字类型，这些数字类型恰好支持使用整数进行相等性测试，但也不希望同时支持整数算术。请参阅实现收容测试的原始Python问题。
* 由于Python整数是无界的，所以时间接近恒定，因此数学运算也随着N的增长而及时增长，这使其成为O（log N）运算。由于所有操作均以优化的C代码执行，并且Python将整数值存储在30位块中，因此，由于此处涉及的整数大小，您会用光内存，然后再看到任何性能影响。
回答 1
此处的根本误解是认为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一个之间的差range和一list在于，range是懒或动态序列; 它不记得所有的价值，它只是记住它start，stop和step，并根据需要创建的值__getitem__。
（作为一个旁注，如果您使用print(iter(a))，则会注意到range使用与相同的listiterator类型list。它是如何工作的？A 除了listiterator使用listC的C实现这一事实外，没有使用任何其他特殊方法__getitem__，因此对于range太。）
现在，没有什么可以说Sequence.__contains__必须是恒定时间的-实际上，对于类似的明显示例list，事实并非如此。但是没有什么可以说是不可能的。与range.__contains__仅(val - start) % step实际进行计算和测试所有值相比，仅对其进行数学检查（，但具有一些额外的复杂性来处理否定步骤）要容易实现，那么为什么不这样做会更好呢？
但是似乎没有什么语言可以保证会发生这种情况。正如Ashwini Chaudhari指出的那样，如果您给它提供一个非整数值，而不是转换为整数并进行数学测试，它将落到对所有值进行迭代并逐一进行比较的过程中。不仅因为CPython 3.2+和PyPy 3.x版本恰好包含此优化，而且这是一个显而易见的好主意且易于实现，所以Iron Iron或NewKickAssPython 3.x没有理由不能放弃它。（实际上，CPython 3.0-3.1 并未包含它。）
如果range实际上是一个生成器（如）my_crappy_range，那么以__contains__这种方式进行测试就没有意义，或者至少有一种合理的方式并不明显。如果您已经迭代了前三个值，那么生成器1仍然in是吗？测试是否应该1使其迭代并消耗所有值1（或直到第一个值>= 1）？
回答 2
使用消息来源，卢克！
在CPython中，range(...).__contains__（方法包装器）最终将委托给一个简单的计算，该计算将检查该值是否可以在该范围内。速度之所以如此，是因为我们使用关于边界的数学推理，而不是range对象的直接迭代。解释所使用的逻辑：
- 检查数字在
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);
}该行的“实质”在该行中提到：
/* 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)回答 3
为了补充Martijn的答案，这是源代码的相关部分（在C中，因为range对象是用本机代码编写的）：
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对象（int在Python 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回答 4
如果您想知道为什么将此优化添加到range.__contains__，以及为什么未将其添加到xrange.__contains__2.7：
首先，正如Ashwini Chaudhary所发现的， 发行1766304已明确打开以进行优化[x]range.__contains__。接受了此修补程序并签入了3.2版本，但没有回迁到2.7版本，因为“ xrange表现得如此之久，以至于我看不到它为什么让我们提交最新的修补程序。” （当时2.7快要淘汰了。）
与此同时：
最初xrange是一个非相当序列的对象。如 3.1文档所说：
范围对象的行为很少：它们仅支持索引，迭代和
len功能。
这不是真的。一个xrange对象实际支持，与索引和自动出现一些其他的东西len， *包括__contains__（通过线性搜索）。但是，没有人认为有必要在那时将它们完整地序列化。
然后，作为实现抽象基类 PEP的一部分，重要的是弄清楚应将哪些内置类型标记为实现哪些ABC和xrange/ range声称实现collections.Sequence，即使它仍仅处理相同的“非常少的行为”。在发布9213之前，没有人注意到这个问题。该问题的补丁不仅增加index和count3.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的补丁更新版本恢复了以前的大部分代码，包括对通用代码的后备支持，_PySequence_IterSearch这range.__contains__在不应用优化的情况下会缓慢地降低3.2 之前版本的隐式使用。
回答 5
其他答案已经很好地说明了这一点，但是我想提供另一个实验来说明范围对象的性质：
>>> 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]如您所见，范围对象是一个记住其范围的对象，可以多次使用（即使在其上进行迭代），而不仅仅是一次生成器。
回答 6
这是关于一个偷懒的办法来评估和一些额外的优化的range。直到实际使用时才需要计算范围内的值，或者由于额外的优化甚至不需要进一步计算。
顺便说一句，您的整数不是那么大，请考虑 sys.maxsize
sys.maxsize in range(sys.maxsize) 相当快
由于优化-比较给定的整数和范围的最小值和最大值很容易。
但：
Decimal(sys.maxsize) in range(sys.maxsize) 很慢。
（在这种情况下， range，因此，如果python收到意外的Decimal，则python将比较所有数字）
您应该了解实现细节，但不应依赖它，因为将来可能会改变。
回答 7
TL; DR
传回的物件range()实际上是range对象。该对象实现了迭代器接口，因此您可以按顺序迭代其值，就像生成器，列表或元组一样。
但是，它也实现了__contains__接口，该接口实际上是当对象出现在in操作员右侧时调用的接口。该__contains__()方法返回a bool左侧项目是否in在对象中。由于range对象知道其边界和步幅，因此在O（1）中非常容易实现。
回答 8
- 由于优化，将给定的整数与最小和最大范围进行比较非常容易。
- 在Python3 中range（）函数之所以如此之快，是因为这里我们对边界使用数学推理，而不是范围对象的直接迭代。
- 所以在这里解释逻辑：
- 检查数字是否在开始和停止之间。
- 检查步长精度值是否不超过我们的数字。
例如，997在range（4，1000，3）内是因为：
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
回答 9
尝试x-1 in (i for i in range(x))使用较大的x值，该值使用生成器理解来避免调用range.__contains__优化。
