为什么 "1000000000000000 in range(1000000000000001)" 在 Python3 里速度那么快?

在我理解 range() 函数作为 an object type in Python 3 生成的内容和生成器差不多快.

我测试如下语句

1000000000000000 in range(1000000000000001)

不管我加了多少个 0 这个计算的结果时间都差不多

我还试了下这个, 结果差不多, 非常快:

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

但是我自己写了个代码速度就非常慢:

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

所以我想问为啥 range() 如此之快?

Python3 的 range() 对象并不会立即产生数值;它会在需要时来产生.它包含你的起始, 终止和步长, 它会随着每次迭代来产生下一个数值.

这个对象通过 object.__contains__ hook 来实现的.计算的时间复杂度为 O(1).在迭代的过程中其实是不需要一下计算出所有的数值的.

根据 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 = 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() 方法,但是应当可以给你些启发.