python - 为什么 "1000000000000000 in range(1000000000000001)"在 Python 3 中如此之快？

Question

据我了解，range()函数，实际上是 an object type in Python 3 , 动态生成其内容，类似于生成器。
在这种情况下，我预计以下行会花费过多的时间，因为为了确定 1 千万亿是否在范围内，必须生成千万亿值:

1000000000000000 in range(1000000000000001)

此外:似乎无论我添加多少个零，计算或多或少都需要相同的时间(基本上是瞬时的)。
我也尝试过这样的事情，但计算仍然几乎是即时的:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

如果我尝试实现我自己的 range 函数，结果就不那么好了!!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

什么是range()在引擎盖下做的对象使它如此之快？

Martijn Pieters' answer因其完整性而被选中，但也请参阅 abarnert's first answer很好地讨论了 range 的含义成为 Python 3 中完整的序列，以及关于 __contains__ 的潜在不一致的一些信息/警告跨 Python 实现的函数优化。 abarnert's other answer更详细地介绍了一些细节，并为那些对 Python 3 中优化背后的历史感兴趣的人提供了链接(以及 Python 2 中 xrange 缺乏优化)。答案 by poke和 by wim为有兴趣的人提供相关的C源代码和解释。

Answer 1

Python 3 range()对象不会立即产生数字；它是一个智能sequence object按需生成数字。它包含的只是你的开始、停止和步长值，然后当你迭代对象时，每次迭代都会计算下一个整数。
该对象还实现了 object.__contains__ hook ，并计算您的数字是否在其范围内。计算是一个(接近)恒定时间操作*。永远不需要扫描范围内所有可能的整数。
来自 range() object documentation :

The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).

所以至少，您的 range()对象会做:

class my_range:
    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('my_range object index out of range')

    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() object 一个非整数值(包括 int 的子类)，启动慢速扫描以查看是否存在匹配，就像您对所有包含值的列表使用包含测试一样。这样做是为了继续支持其他恰好支持整数相等测试但预计不支持整数算术的数字类型。见原文Python issue实现了遏制测试。

* 接近恒定时间，因为 Python 整数是无界的，所以数学运算也会随着 N 的增长而随时间增长，这使得它成为 O(log N) 运算。由于它都是在优化的 C 代码中执行的，并且 Python 将整数值存储在 30 位块中，因此在您看到由于此处涉及的整数的大小而导致的任何性能影响之前，您已经耗尽了内存。