为什么Python3中的“10000000000000 in range(10000000000001)”这么快?

  • 问题:
  • 我的理解是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

    range()对象在引擎盖下做什么使它如此快?在

    Martijn Pieters’ answer因为其完整性而被选中,但也请参见abarnert的第一个回答是很好地讨论了在Python 3中,范围是一个完整的序列,以及一些关于跨Python实现的包含函数优化的潜在不一致性的信息/警告。abarner的另一个答案更为详细,并为那些对python3中的优化背后的历史感兴趣的人提供了链接(以及python2中缺少对xrange的优化)。答案按戳by wim为感兴趣的人提供相关的C源代码和解释。在

  • 答案:
  • python3range()对象不会立即生成数字;它是一个smart sequence object按需产生数字。它只包含开始值、停止值和步长值,然后在迭代对象时,每次迭代都会计算下一个整数

    对象还实现object.__contains__ hook,并且计算如果您的数字是其范围的一部分。计算是一个(接近)恒定时间操作*。不需要扫描范围内所有可能的整数

    range() object documentation公司名称:

    与常规列表或元组相比,范围类型的优势在于,范围对象将始终占用相同(少量)的内存,而不管它所代表的范围大小(因为它只存储开始停止步骤值,根据需要计算单个项目和子范围)

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

    这仍然缺少一些realrange()支持的功能(例如.index().count()方法、哈希、相等性测试或切片),但应该能让您有所了解

    如果一个包含的整数代码的实现包含一个包含的实数代码,那么就使用一个包含的实数代码。这样做是为了继续支持其他数值类型,这些类型恰好支持整数的相等性测试,但不希望也支持整数算术。看原稿Python issue实施了遏制试验

    *Near常量时间,因为Python整数是无界的,因此数学运算也会随着N的增长而增长,因此这是一个O(logn)操作。由于它都是用经过优化的C代码执行的,而且Python将整数值存储在30位的块中,因此在看到这里涉及的整数的大小对性能的影响之前,内存就会耗尽