为什么在Python 3 1000000000000001中“100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

performance range python python-3.x python-internals

2022-09-05 00:45:59

我的理解是，该函数实际上是Python 3中的对象类型，它动态生成其内容，类似于生成器。range()

在这种情况下，我本来以为以下行会花费过多的时间，因为为了确定1千万亿是否在该范围内，必须生成一个千万亿的值：

1_000_000_000_000_000 in range(1_000_000_000_000_001)

此外：似乎无论我添加多少个零，计算或多或少都需要相同的时间（基本上是瞬时的）。

我也尝试过这样的事情，但计算仍然几乎是即时的：

# count by tens
1_000_000_000_000_000_000_000 in range(0,1_000_000_000_000_000_000_001,10)

如果我尝试实现自己的范围函数，结果就不那么好了！

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

物体在引擎盖下做了什么，使它如此之快？range()

Martijn Pieters的答案因其完整性而被选中，但也参见abarnert的第一个答案，以很好地讨论Python 3中成为一个成熟的序列意味着什么，以及一些关于Python实现中函数优化的潜在不一致的信息/警告。abarnert的另一个答案更详细地介绍了一些细节，并为那些对Python 3中优化背后的历史（以及Python 2中缺乏优化）感兴趣的人提供了链接。通过poke和wim的答案为那些感兴趣的人提供了相关的C源代码和解释。range__contains__xrange

答案 1

Python 3对象不会立即生成数字;它是一个智能序列对象，可按需生成数字。它所包含的只是您的开始，停止和步长值，然后当您迭代对象时，每次迭代都会计算下一个整数。range()

该对象还实现object.__contains__挂钩，并计算您的数字是否在其范围内。计算是一个（接近）常量时间操作 ^*。永远不需要扫描范围内所有可能的整数。

从 range（） 对象文档：

与常规对象相比，该类型的优点是，无论它表示的范围大小如何，范围对象都将始终占用相同（小）的内存量（因为它仅存储和值，根据需要计算单个项目和子范围）。rangelisttuplestartstopstep

因此，您的对象至少可以执行以下操作：range()

class my_range:
    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('my_range object index out of range')

    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

这仍然缺少一些真正支持的东西（例如or方法，散列，相等性测试或切片），但应该给你一个想法。range().index().count()

我还简化了实现，只关注整数测试;如果为真实对象指定一个非整数值（包括的子类），则会启动慢速扫描以查看是否存在匹配项，就像对所有包含的值的列表使用包含测试一样。这样做是为了继续支持其他数字类型，这些数字类型恰好支持整数的相等性测试，但预计不会支持整数算术。请参阅实现包含测试的原始 Python 问题。__contains__range()int

* 接近常量时间，因为Python整数是无界的，因此数学运算也会随着N的增长而随时间增长，使其成为O（log N）运算。由于它都是在优化的C代码中执行的，并且Python将整数值存储在30位块中，因此在看到由于此处涉及的整数大小而导致的任何性能影响之前，您的内存就会耗尽。

答案 2

这里根本的误解在于认为这是一个发电机。事实并非如此。事实上，它不是任何类型的迭代器。range

你可以很容易地看出这一点：

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

如果它是一个生成器，迭代一次就会耗尽它：

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

实际上，是一个序列，就像一个列表。您甚至可以测试以下内容：range

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

这意味着它必须遵循成为序列的所有规则：

>>> a[3]         # indexable
3
>>> len(a)       # sized
5
>>> 3 in a       # membership
True
>>> reversed(a)  # reversible
<range_iterator at 0x101cd2360>
>>> a.index(3)   # implements 'index'
3
>>> a.count(3)   # implements 'count'
1

a 和 a 之间的区别在于 a 是一个惰性或动态序列;它不记得它的所有值，它只是记住它的、和，并根据需要创建值。rangelistrangestartstopstep__getitem__

（作为旁注，如果您，您会注意到使用与相同的类型。这是如何运作的？A 没有使用任何特别的东西，除了它提供了的 C 实现，所以它也可以正常工作。print(iter(a))rangelistiteratorlistlistiteratorlist__getitem__range

现在，没有什么说它必须是恒定的时间 - 事实上，对于像这样的序列的明显例子，它不是。但没有什么可以说它不可能。而且，通过数学方法检查它（但处理否定步骤需要一些额外的复杂性）比实际生成和测试所有值更容易实现，那么为什么它不应该以更好的方式做到这一点呢？Sequence.__contains__listrange.__contains__(val - start) % step

但是语言中似乎没有任何东西可以保证这种情况会发生。正如Ashwini Chaudhari所指出的那样，如果你给它一个非整数值，而不是转换为整数并进行数学测试，它将回退到迭代所有值并逐个比较它们。仅仅因为CPython 3.2 +和PyPy 3.x版本恰好包含这种优化，并且这是一个明显的好主意并且很容易做到，因此没有理由IronPython或NewKickAssPython 3.x不能将其排除在外。（事实上，CPython 3.0-3.1不包括它。

如果实际上是一个生成器，比如，那么以这种方式进行测试是没有意义的，或者至少它有意义的方式不会很明显。如果已经迭代了前 3 个值，则生成器是否仍为生成器？测试是否会导致它迭代并使用所有值，直到（或直到第一个值）？rangemy_crappy_range__contains__1in11>= 1