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


当前回答

其他答案已经很好地解释了这一点,但我想提供另一个实验来说明距离物体的性质:

>>> 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]

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

其他回答

如果您想知道为什么要将此优化添加到范围中__contains_,以及为什么没有将其添加到xrange中__包含2.7中的_:

首先,正如Ashwini Chaudhary所发现的,1766304期被明确地开放,以优化[x]范围__包含_。这个补丁已经被接受并以3.2的价格签入,但没有被移植到2.7,因为“xrange已经这么长时间了,我看不出它能让我们这么晚才提交补丁。”

同时:

最初,xrange是一个不太序列的对象。正如3.1文档所说:

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

这并不完全正确;一个xrange对象实际上还支持一些其他的东西,这些东西是通过索引和len自动实现的,包括contains(通过线性搜索)。但当时没有人认为制作完整的序列是值得的。

然后,作为实现抽象基类PEP的一部分,重要的是弄清楚哪些内置类型应该标记为实现哪些ABC,以及xrange/range声称实现集合.Sequence,尽管它仍然只处理相同的“非常少的行为”。直到第9213期,没有人注意到这个问题。针对该问题的补丁不仅将索引和计数添加到了3.2的范围,还重新使用了优化的__contains__(它与索引共享相同的数学,并且直接由计数使用)。**这一更改也适用于3.2,并且没有后移到2.x,因为“这是一个添加新方法的错误修复程序”。(此时,2.7已经超过了rc状态。)

因此,有两次机会将优化后移到2.7,但都被拒绝了。


*事实上,您甚至可以仅通过索引免费获得迭代,但在2.3xrange中,对象有一个自定义迭代器。

**第一个版本实际上重新实现了它,并错误地获得了详细信息,例如,它将在范围(5)==False中为您提供MyIntSubclass(2)。但Daniel Stutzbach的补丁更新版本恢复了以前的大部分代码,包括回退到3.2之前的通用、缓慢的_PySequence_IterSearch__当优化不适用时,contains被隐式使用。

其他答案已经很好地解释了这一点,但我想提供另一个实验来说明距离物体的性质:

>>> 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]

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

对于较大的x值,请尝试x-1 in(i代表i in range(x)),这使用生成器理解来避免调用范围__包含优化。

由于优化,很容易将给定的整数与最小和最大范围进行比较。在Python3中,range()函数速度如此之快的原因是这里我们对边界使用数学推理,而不是直接迭代range对象。因此,为了解释这里的逻辑:

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

举个例子,997在范围(4、1000、3)内,因为:4<=997<1000,以及(997-4)%3==0。

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