小编典典

为什么在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源代码和说明。


阅读 551

收藏
2020-02-14

共1个答案

小编典典

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

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

range()对象文档中:

所述的优点range类型通过常规listtuple是一个范围对象将始终以相同的内存(小)数量,无论它代表的范围内的大小(因为它仅存储startstopstep值,计算各个项目和子范围如所须)。

因此,你的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