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


这是我的理解 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优化背后的历史感兴趣的人提供了链接(并且没有优化 xrange 在Python 2)。答案 通过戳 和 通过wim 为感兴趣的人提供相关的C源代码和解释。


1368
2018-05-06 15:32


起源


不要试试这个 xrange() 但是在Python 2中。 - Ashwini Chaudhary
请注意,只有当我们检查的项目是a时才会出现这种情况 bool 要么 long 类型,与其他对象类型,它会发疯。试试: 100000000000000.0 in range(1000000000000001) - Ashwini Chaudhary
谁告诉你的 range 是发电机? - abarnert
@abarnert我认为我做的编辑留下了完整的混乱。 - Rick Teachey
@Superbest xrange() 对象没有 __contains__ 方法,因此项目检查必须遍历所有项目。此外,还有其他一些变化 range(),就像它支持切片(它再次返回一个 range 对象)现在也有 count 和 index 使其兼容的方法 collections.Sequence ABC。 - Ashwini Chaudhary


答案:


Python 3 range() 对象不会立即产生数字;它是一个产生数字的智能序列对象 一经请求。它包含的只是你的开始值,停止值和步长值,然后在迭代对象时,每次迭代计算下一个整数。

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

来自 range() 对象文档

的优点 range 键入常规 list 要么 tuple 是一个范围对象将始终采用相同(小)的内存量,无论它所代表的范围的大小(因为它只存储 startstop 和 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() object一个非整数值(包括的子类) int),启动慢速扫描以查看是否存在匹配,就像对所有包含值的列表使用包含测试一样。这样做是为了继续支持恰好支持使用整数进行相等性测试的其他数值类型,但也不希望支持整数运算。看原文 Python问题 实施了遏制测试。


1357
2018-05-06 15:33



好的,所以,计算一下 range(1000000000)[index_number] 例如,可能是这样的: return start + step * index_number? - Rick Teachey
@RickTeachey:是的。如果您可以计算它,则无需生成任何中间号码。 - Martijn Pieters♦
@Veedrac:我不想让这句话更费力,并且深入研究迭代器与迭代的细节。我会看看我是否可以重新调整一下。 - Martijn Pieters♦
有趣的事实:因为你有一个有效的实现 __getitem__ 和 __len__, __iter__ 实施其实是不必要的。 - Lucretiel
@ stefan.schwetschke:对,最初编写补丁时,范围仅支持起始值和停止值 sys.maxsize,所以有一个上限。相比 len(range_object),数字比较/模数是 接近足够的常数 这里的分析无关紧要。 - Martijn Pieters♦


这里的根本误解在于思考 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之间的区别 range 和a list 是那个 range 是一个  要么 动态 序列;它不记得它的所有价值,只记得它 startstop,和 step,并根据需要创建值 __getitem__

(作为旁注,如果你 print(iter(a)),你会注意到的 range 使用相同的 listiterator 输入为 list。这是如何运作的?一个 listiterator 不使用任何特别的东西 list 除了提供C实现的事实 __getitem__,所以它的工作正常 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 仍然 in 发电机?应该测试 1 使它迭代并消耗所有值 1 (或达到第一个值 >= 1)?


567
2018-05-06 16:01



这是一个非常重要的事情。我想Python 2和3之间的差异可能导致我在这一点上的困惑。无论如何,我应该意识到 以来 range 列出(连同 list 和 tuple)作为序列类型。 - Rick Teachey
@RickTeachey:实际上,在2.6+(我想;也许是2.5+), xrange 也是一个序列。看到 2.7文档。事实上,它总是一个几乎顺序。 - abarnert
@RickTeachey:实际上,我错了;在2.6-2.7(和3.0-3.1)中,它 索赔 成为一个序列,但它仍然只是一个序列。看到我的其他答案。 - abarnert
它不是一个迭代器,它是一个序列(就Java而言是Iterable,C#的IEnumerable) - .__iter__() 将返回迭代器的方法。它反过来只能使用一次。 - Smit Johnth
@ThomasAhle:因为 range 当它不是一个整数时,它不会检查类型,因为类型总是有一个类型 __eq__ 与...兼容 int。当然, str 显然不起作用,但他们不想通过明确检查所有类型来减慢速度 不能 在那里(毕竟,一个 str 子类可以覆盖 __eq__ 并被包含在 range)。 - ShadowRanger


使用 资源,卢克!

在CPython中, range(...).__contains__ (方法包装器)最终将委托给一个简单的计算,该计算检查该值是否可能在该范围内。这里速度的原因是我们正在使用 关于边界的数学推理,而不是范围对象的直接迭代。解释使用的逻辑:

  1. 检查数字是否介于两者之间 start 和 stop,和
  2. 检查步幅值是否“跳过”我们的号码。

例如, 994 在... range(4, 1000, 2) 因为:

  1. 4 <= 994 < 1000,和
  2. (994 - 4) % 2 == 0

完整的C代码包含在下面,由于内存管理和引用计数细节,它有点冗长,但基本思路是:

static int
range_contains_long(rangeobject *r, PyObject *ob)
{
    int cmp1, cmp2, cmp3;
    PyObject *tmp1 = NULL;
    PyObject *tmp2 = NULL;
    PyObject *zero = NULL;
    int result = -1;

    zero = PyLong_FromLong(0);
    if (zero == NULL) /* MemoryError in int(0) */
        goto end;

    /* Check if the value can possibly be in the range. */

    cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
    if (cmp1 == -1)
        goto end;
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    }
    else { /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }

    if (cmp2 == -1 || cmp3 == -1) /* TypeError */
        goto end;
    if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
        result = 0;
        goto end;
    }

    /* Check that the stride does not invalidate ob's membership. */
    tmp1 = PyNumber_Subtract(ob, r->start);
    if (tmp1 == NULL)
        goto end;
    tmp2 = PyNumber_Remainder(tmp1, r->step);
    if (tmp2 == NULL)
        goto end;
    /* result = ((int(ob) - start) % step) == 0 */
    result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
  end:
    Py_XDECREF(tmp1);
    Py_XDECREF(tmp2);
    Py_XDECREF(zero);
    return result;
}

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

这个想法的“肉”在提到 这条线

/* result = ((int(ob) - start) % step) == 0 */ 

最后一点 - 看看 range_contains 功能位于代码段的底部。如果确切的类型检查失败,那么我们不使用所描述的聪明算法,而是回退到使用该范围的哑迭代搜索 _PySequence_IterSearch!您可以在解释器中检查此行为(我在这里使用v3.5.0):

>>> x, r = 1000000000000000, range(1000000000000001)
>>> class MyInt(int):
...     pass
... 
>>> x_ = MyInt(x)
>>> x in r  # calculates immediately :) 
True
>>> x_ in r  # iterates for ages.. :( 
^\Quit (core dumped)

286
2018-05-06 15:41



很好的答案。这也是我最喜欢的人性化使用的例子 goto。 - brian_o
@brian_o用a实现更好 try: finally: 和a return 代替 goto... - wizzwizz4


为了增加Martijn的答案,这是相关部分 来源 (在C中,由于范围对象是用本机代码编写的):

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

因此对于 PyLong 对象(即 int 在Python 3)中,它将使用 range_contains_long 确定结果的功能。而该功能实质上是检查 ob 在指定的范围内(虽然它在C中看起来有点复杂)。

如果它不是 int 对象,它回退到迭代,直到找到值(或不)。

整个逻辑可以像这样翻译成伪Python:

def range_contains (rangeObj, obj):
    if isinstance(obj, int):
        return range_contains_long(rangeObj, obj)

    # default logic by iterating
    return any(obj == x for x in rangeObj)

def range_contains_long (r, num):
    if r.step > 0:
        # positive step: r.start <= num < r.stop
        cmp2 = r.start <= num
        cmp3 = num < r.stop
    else:
        # negative step: r.start >= num > r.stop
        cmp2 = num <= r.start
        cmp3 = r.stop < num

    # outside of the range boundaries
    if not cmp2 or not cmp3:
        return False

    # num must be on a valid step inside the boundaries
    return (num - r.start) % r.step == 0

106
2018-05-06 15:41



@ChrisWesseling:我认为这是不同的 - 足够的信息,编辑Martijn的答案在这里不合适。这是一个判断性的呼吁,但人们通常会因为没有对其他人的答案做出重大改变而犯错误。 - abarnert


如果你想知道 为什么 此优化已添加到 range.__contains__,为什么呢  添加到 xrange.__contains__ 在2.7:

首先,正如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.Sequence,即使它仍然只处理相同的“非常小的行为”。直到没有人注意到这个问题 问题9213。该问题的补丁不仅添加了 index 和 count 到3.2的 range,它还重新优化了 __contains__ (与...共享相同的数学运算 index,并直接使用 count)。**  这种变化 也进入了3.2,并没有向后移植到2.x,因为“这是一个增加新方法的错误修正”。 (此时,2.7已经超过了rc状态。)

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


*实际上,你甚至可以免费获得迭代 len 和索引,但 在2.3  xrange 对象有一个自定义迭代器。然后他们在3.x中丢失,使用相同的 listiterator 输入为 list

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


79
2018-05-06 21:42



从这里的评论: 提高 xrange.__contains__,看起来他们并没有将它向后移植到Python 2只是为了给用户留下一个惊喜元素而且为时已晚o_O。该 count 和 index  补丁 后来加入了。当时的档案: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c - Ashwini Chaudhary
我怀疑一些核心python开发者偏爱python 2.x的“强烈爱”,因为他们想鼓励人们切换到远远优越的python3 :) - wim
另外我敢打赌,为旧版本添加新功能是一个巨大的负担。想象一下,如果你去了甲骨文并且说:“看,我正在使用Java 1.4,我应该得到lambda表达式!无需支持它们。” - Robert Grant
@RickTeachey是的,这只是一个例子。如果我说1.7它仍然适用。这是一个不定性的数量差异。基本上(无偿的)开发人员不能永远在3.x中创建很酷的新东西,并且对于那些不想升级的人来说它向后端移动到2.x.这是一个巨大而荒谬的负担。你觉得我的推理还有问题吗? - Robert Grant
@RickTeachey:2.7介于3.1和3.2之间,而不是3.3左右。这意味着当最后一次更改为3.2时,2.7在rc中,这使得错误评论更容易理解。无论如何,我认为他们在回顾过程中犯了一些错误(特别是假设人们会通过移民 2to3 而不是通过图书馆的帮助,通过双版本代码 six这就是为什么我们得到的东西 dict.viewkeys 没有人会使用),并且有一些变化在3.2中来得太晚,但在大多数情况下2.7是令人印象深刻的“最后2.x永远”版本。 - abarnert


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

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

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


35
2018-05-06 16:04



我不会过分夸大切片对象的相似性;它似乎让更多人感到困惑而不是它有所帮助。 (一旦有人意识到这一点,他们开始想知道为什么首先有两种不同的类型,并且需要一些时间向他们解释。然后他们中的一些去设计其他语言,如Swift,而不用解决它,并且我们得到了各种令人讨厌的问题,他们在最终提出合理的设计之前,为5个测试版进行了来回反复...) - abarnert
@abarnert你认为我应该删除那部分吗?我从来没有明确地创建切片对象。我刚添加它是因为它们相似,至少对我来说,切片对象是“静态的”感觉更直观,因为数据不是来自它们,而是来自它们所使用的序列。 - Stefan Pochmann
我认为你的直觉肯定有助于使它更清晰......但我不知道你是否可以将其作为答案。也许通过明确地调用 indices 方法?但在那一点上,可能它离主要点太远了? - abarnert
@abarnert Nah,因为我从未明确使用切片对象,我甚至不知道索引方法,我现在不想考虑它。我将从答案中删除该部分。 - Stefan Pochmann


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

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

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

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

但:

float(sys.maxsize) in range(sys.maxsize)  很慢

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


3
2018-03-16 10:47