为什么“1000000000000000 in range(1000000000000001)”在 Python 3 中如此之快？

Question

据我了解， 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 的第一个答案，以很好地讨论 range 在 Python 3 中成为一个成熟的 _序列_，以及一些关于潜在不一致的信息/警告对于 __contains__ 跨 Python 实现的函数优化。 abarnert 的另一个答案 更详细，并为那些对 Python 3 中优化背后的历史感兴趣的人提供了链接（以及 Python 2 中缺乏 xrange 的优化）。 poke 和 wim 的回答为感兴趣的人提供了相关的 C 源代码和解释。

原文由 Rick supports Monica 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

Python 3 range() 对象不会立即产生数字；它是一个 按需 生成数字的智能 序列对象。它只包含您的开始、停止和步长值，然后当您迭代对象时，每次迭代都会计算下一个整数。

该对象还实现了 object.__contains__ 挂钩，并 计算 您的数字是否在其范围内。计算是（接近）恒定时间操作* 。永远不需要扫描范围内所有可能的整数。

来自 range() 对象文档：

range 类型优于常规 list 或 tuple --- 类型的优点是范围对象将始终占用相同（少量）的内存，无论它表示的范围的大小（因为它只存储 start 、 stop 和 step 值，根据需要计算单个项目和子范围）。

所以至少，你的 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 问题。

---

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

原文由 Martijn Pieters 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这里的根本误解是认为 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'
1

---

a range 和 list --- 之间的区别在于 range 是 惰性 或 动态 序列； it doesn’t remember all of its values, it just remembers its start , stop , and step , and creates the values on demand on __getitem__ 。

(As a side note, if you print(iter(a)) , you’ll notice that range uses the same listiterator type as list . How does那行得通吗？A 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 ）？

原文由 abarnert 发布，翻译遵循 CC BY-SA 4.0 许可协议