为什么在Python 3中“范围（10000000000000001）”这么快？

一尘不染

为什么在Python 3中“范围（10000000000000001）”这么快？

python

据我了解，该range()函数实际上是Python 3中的一种对象类型，它像生成器一样动态生成其内容。

在这种情况下，我本以为下一行会花费过多的时间，因为要确定1个四舍五入是否在范围内，必须生成一个四舍五入值：

1000000000000000 in range(1000000000000001)

此外：似乎无论我添加多少个零，计算多少都花费相同的时间（基本上是瞬时的）。

我也尝试过这样的事情，但是计算仍然是即时的：

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

如果我尝试实现自己的范围函数，结果将不是很好！

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

使range()物体如此之快的物体在做什么？

选择了Martijn Pieters的答案是因为它的完整性，但也看到了abarnert的第一个答案，它很好地讨论了在Python 3中range成为完整序列的含义，以及一些有关__contains__跨Python实现的函数优化潜在不一致的信息/警告。。abarnert的其他答案更加详细，并为那些对Python 3优化背后的历史（以及xrangePython 2中缺乏优化）感兴趣的人提供了链接。poke和wim的答案为感兴趣的人提供了相关的C源代码和说明。

阅读 484

2020-02-14

共1个答案

一尘不染

Python 3 range()对象不会立即产生数字。它是一个智能序列对象，可按需生成数字。它包含的只是你的开始，结束和步进值，然后在对对象进行迭代时，每次迭代都会计算下一个整数。

该对象还实现了object.__contains__hook，并计算你的电话号码是否在其范围内。计算是一个（近）恒定时间运算*。永远不需要扫描范围内所有可能的整数。

从range()对象文档中：

所述的优点range类型通过常规list或tuple是一个范围对象将始终以相同的内存（小）数量，无论它代表的范围内的大小（因为它仅存储start，stop和step值，计算各个项目和子范围如所须）。

因此，你的range()对象至少可以做到：

class my_range(object):
    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('Index out of range: {}'.format(i))

    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位块中，因此，由于此处涉及的整数大小，在看到任何性能影响之前，你将耗尽内存。

2020-02-14