python - 为什么Python 3中的“1000000000000000在范围内(1000000000000001)”如此之快?

据我所知,range()函数实际上是an object type in 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

引擎盖下的对象在做什么使其如此快速?
之所以选择Martijn Pieters' answer是因为它的完整性,但也请参见abarnert's first answer以获得有关在python 3中完整序列的意义的良好讨论,以及有关在python实现中实现range()函数优化的潜在不一致性的一些信息/警告。abarnert's other answer更详细地介绍了一些内容,并为那些对python 3中的优化背后的历史感兴趣的人提供了链接(并且在python 2中缺少对range的优化)。回答by pokeby wim为感兴趣的人提供相关的C源代码和解释。


最佳答案:

python 3range()对象不会立即生成数字;它是一个按需生成数字的智能序列对象。它所包含的只是您的开始、停止和步骤值,然后在对象上迭代时,每次迭代都会计算下一个整数。
对象还实现object.__contains__ hook,并计算您的数字是否是其范围的一部分。计算是一个O(1)常量时间操作。不需要扫描范围内所有可能的整数。
range() object documentation开始:
与常规的rangelist类型相比,tuple类型的优势在于,范围对象将始终占用相同(小)的内存量,无论其表示的范围大小如何(因为它只存储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 = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(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 issue