小编典典

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

javascript

据我了解,该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()对象是什么让它如此之快?


阅读 209

收藏
2022-01-30

共2个答案

小编典典

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

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

从range()对象文档:

该range类型优于常规listor的优点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()or.count()方法、散列、相等测试或切片),但应该给你一个想法。

我还简化了__contains__实现,只关注整数测试;如果您给一个真实range()对象一个非整数值(包括 的子类int),则会启动慢速扫描以查看是否存在匹配项,就像您对所有包含值的列表使用包含测试一样。这样做是为了继续支持其他恰好支持整数相等测试但预计也不支持整数算术的数字类型。请参阅实现包含测试的原始Python 问题。

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

2022-01-30
小编典典

这里的基本误解是认为它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

rangea和 a的区别在于listarange惰性动态序列;它不会记住它的所有值,它只记住它的start,stopstep, 并在 上按需创建值__getitem__

(作为旁注,如果你print(iter(a)),你会注意到它range使用与 相同的listiterator类型list。它是如何工作的?Alistiterator没有使用任何特殊的东西,list除了它提供了 C 的实现__getitem__,所以它适用于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)?

2022-01-30