python - 为什么 Python 3 中的 "1000000000000000 in range(1000000000000001)"这么快？

Question

我的理解是range()函数，其实是an object type in 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's answer因其完整性而被选中，但另见 abarnert's first answer很好地讨论了 range 在 Python 3 中成为一个成熟的 sequence 意味着什么，以及一些关于 __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() 对象一个非整数值(包括 int 的子类)，就会启动一个慢速扫描来查看是否有匹配，就像如果您对所有包含值的列表使用包含测试。这样做是为了继续支持其他恰好支持整数相等测试但预计也不支持整数算术的数字类型。见原文Python issue实现了收容测试。

---

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