为什么在Python3中"1000000000000000 in range(1000000000000001)“这么快？
我的理解是，range()函数实际上是Python 3中的对象类型，它动态地生成它的内容，类似于生成器。
在这种情况下，我希望下面这一行会花费过多的时间，因为为了确定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
returnrange()对象在引擎盖下做什么使它如此快速？
之所以选择Martijn Pieters的回答是因为它的完整性，但也请参阅艾伯纳特的第一个答案，以便很好地讨论在Python3中range是一个完整的序列意味着什么，以及关于__contains__函数在整个__contains__实现中可能存在的不一致性的一些信息/警告。艾伯纳特的另一个答案详细介绍了一些细节，并为那些对Python3中的优化背后的历史感兴趣的人提供了链接(以及缺少对Python2中xrange的优化)。答案被戳和韦姆为感兴趣的人提供了相关的C源代码和解释。
回答 10
Stack Overflow用户
发布于 2015-05-06 16:01:17
这里的基本误解是认为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'
1range和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仍然是in生成器吗？对1的测试是否应该导致它迭代和使用直到1 (或到第一个值>= 1)的所有值？
Stack Overflow用户
发布于 2015-05-06 15:41:18
用来源，卢克！
在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);
}在评论中提到了这个想法的“肉”：
/* 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)Stack Overflow用户
发布于 2015-05-06 15:41:13
为了补充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对象(在Python3中是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 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 == 0https://stackoverflow.com/questions/30081275
复制相似问题
腾讯云开发者
