据我所知,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源代码和解释。


当前回答

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

顺便说一下,您的整数没有那么大,请考虑sys.maxsize

范围内的sys.maxsize(sys.maxssize)非常快

由于优化,很容易将给定的整数与范围的最小值和最大值进行比较。

but:

范围(sys.maxsize)中的十进制(sys.mazsize)非常慢。

(在这种情况下,范围内没有优化,所以如果python收到意外的Decimal,python将比较所有数字)

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

其他回答

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

顺便说一下,您的整数没有那么大,请考虑sys.maxsize

范围内的sys.maxsize(sys.maxssize)非常快

由于优化,很容易将给定的整数与范围的最小值和最大值进行比较。

but:

范围(sys.maxsize)中的十进制(sys.mazsize)非常慢。

(在这种情况下,范围内没有优化,所以如果python收到意外的Decimal,python将比较所有数字)

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

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

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

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

TL;博士

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

但它也实现了__contains__接口,当对象出现在in运算符的右侧时,实际上会调用该接口。__contains__()方法返回一个bool,表示in左侧的项是否在对象中。因为范围对象知道它们的边界和步幅,所以这很容易在O(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]

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