为什么在Python 3中“范围(10000000000000001)”这么快?

发布于 2021-02-02 23:20:21

据我了解,该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源代码和说明。

关注者
0
被浏览
75
1 个回答
  • 面试哥
    面试哥 2021-02-02
    为面试而生,有面试问题,就找面试哥。

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


知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看