xrange未定义 - python3 xrange用法




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

TL; DR

range() 返回的对象实际上是一个 range 对象。 该对象实现了迭代器接口,因此您可以像生成器一样顺序遍历其值,但它也实现了 __contains__ 接口,该接口实际上是在对象出现在 in 运算符右侧时调用的接口。 __contains__() 方法返回该项是否在对象中的bool。 由于 range 对象知道它们的界限和步幅,因此在O(1)中很容易实现。

我的理解是, 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的第一个答案 ,可以很好地讨论 range 在Python 3中成为一个完整的 序列的意义 ,以及关于 __contains__ 函数优化的潜在不一致的一些信息/警告Python实现。 abarnert的另一个答案 更详细,并为那些对Python 3中优化背后的历史感兴趣的人提供了链接(并且缺乏Python 2中 xrange 的优化)。 poke 和 wim的 答案 为 感兴趣的人 提供了相关的C源代码和解释。


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

该对象还实现了 object.__contains__ hook ,并 计算 您的数字是否是其范围的一部分。 计算是O(1)恒定时间操作。 永远不需要扫描范围内的所有可能的整数。

来自 range() 对象文档

range 类型相对于常规 listtuple 的优点是范围对象总是占用相同(小)的内存量,无论它表示的范围大小(因为它只存储起始值, 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() 方法,散列,等式测试或切片),但应该给你一个想法。

我还简化了 __contains__ 实现,只关注整数测试; 如果给一个真正的 range() 对象一个非整数值(包括 int 子类),则启动慢速扫描以查看是否存在匹配,就像对所有包含值的列表使用包含测试一样。 这样做是为了继续支持恰好支持使用整数进行相等性测试的其他数值类型,但也不希望支持整数运算。 查看实现包含测试的原始 Python问题


其他答案已经很好地解释了,但我想提供另一个实验来说明范围对象的本质:

>>> r = range(5)
>>> for i in r:
        print(i, 2 in r, list(r))

0 True [0, 1, 2, 3, 4]
1 True [0, 1, 2, 3, 4]
2 True [0, 1, 2, 3, 4]
3 True [0, 1, 2, 3, 4]
4 True [0, 1, 2, 3, 4]

如您所见,范围对象是一个记住其范围的对象,可以多次使用(即使在迭代时也是如此),而不仅仅是一次性生成器。


如果你想知道 为什么 这个优化被添加到 range.__contains__ ,以及为什么它 没有被 添加到2.7中的 xrange.__contains__

首先,正如Ashwini Chaudhary所发现的, 问题1766304 被明确地打开以优化 [x]range.__contains__ 。 这个补丁被 接受并检查了3.2 ,但没有向后移植到2.7,因为“xrange的行为已经这么长时间了,以至于我没看到它买了这个补丁这么晚了。” (2.7当时差不多了。)

与此同时:

最初, xrange 是一个不完全序列的对象。 正如 3.1文档 所说:

Range对象的行为很少:它们只支持索引,迭代和 len 函数。

这不是真的; 一个 xrange 对象实际上支持了一些其他通过索引和 len 自动生成的东西,包括 __contains__ (通过线性搜索)。 但当时没有人认为值得制作完整的序列。

然后,作为实现 抽象基类 PEP的一部分,重要的是要弄清楚哪些内置类型应该被标记为实现哪些ABCs和 xrange / range 声称实现 collections.Sequencexrange ,即使它仍然只处理相同的“非常小小的行为“。 在 问题9213 之前,没有人注意到这个问题。 针对该问题的补丁不仅将 indexcount 添加到3.2的 range ,还重新设计了优化的 __contains__ (与 index 共享相同的数学,并且直接由 count )。 ** 此更改同样 适用于3.2,并且没有向后移植到2.x,因为“它是添加新方法的错误修正”。 (此时,2.7已经超过了rc状态。)

因此,有两次机会将此优化反向移植到2.7,但它们都被拒绝了。

*实际上,你甚至可以通过 len 和indexing免费获得迭代,但 在2.3 xrange 对象中得到了一个自定义迭代器。 然后它们在3.x中丢失,它使用与 list 相同的 listiterator 类型。

**第一个版本实际上重新实现了它,并且错误地得到了细节 - 例如,它会 MyIntSubclass(2) in range(5) == False 给你 MyIntSubclass(2) in range(5) == False 但Daniel Stutzbach的补丁更新版本恢复了之前的大部分代码,包括回 _PySequence_IterSearch 泛型,慢 _PySequence_IterSearch ,3.2之前的 range.__contains__ 在优化不适用时隐式使用。


这完全是关于评估的懒惰方法和 range 一些额外优化。 范围中的值不需要在实际使用之前计算,或者甚至由于额外的优化而进一步计算。

顺便说一句,你的整数不是那么大,考虑 sys.maxsize

sys.maxsize in range(sys.maxsize) 中的 sys.maxsize in range(sys.maxsize) 非常快

由于优化 - 很容易将给定的整数与最小和最大范围进行比较。

但:

float(sys.maxsize) in range(sys.maxsize) 非常慢

(在这种情况下, range 没有优化,所以如果python收到意外的浮点数,python会比较所有数字)

您应该了解实现细节但不应该依赖,因为将来可能会发生变化。


这里的根本误解在于认为 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))
[]

实际上是一个序列,就像一个列表一样。 你甚至可以测试这个:

>>> 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

rangelist 之间的区别在于 range 惰性 动态 序列; 它不记得它的所有值,它只记得它的 startstopstep ,并在 __getitem__ 上按需创建值。

(作为旁注,如果你 print(iter(a)) ,你会发现该 range 使用与 list 一样的 listiterator 类型。它是如何工作的? listiterator 器不会对 list 使用任何特殊的东西,除了事实是它提供了 __getitem__ 的C实现,所以它也适用于 range 。)

现在,没有任何东西可以说 Sequence.__contains__ 必须是恒定的时间 - 事实上,对于像 list 这样的序列的明显例子,它不是。 但没有什么能说它 不可能 。 并且更容易实现 range.__contains__ 以数学方式检查( (val - start) % step ,但处理否定步骤有一些额外的复杂性)而不是实际生成和测试所有值,所以为什么 不应该 这样做它更好的方式?

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

如果 range 实际上是一个生成器,比如 my_crappy_range ,那么以这种方式测试 __contains__ 是没有意义的,或者至少它有意义的方式并不明显。 如果你已经迭代了前3个值,那么 1 还在生成器中吗? 如果测试 1 导致它迭代并消耗所有值,最多 1 (或第一个值 >= 1 )?





python-internals