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

Rick supports Monica 1890 python performance range python-3.x python-internals

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

Martijn Piet.. 1933

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

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

range()对象文档:

所述的优点range类型通过常规listtuple是一个范围对象将始终以相同的内存(小)数量,无论它代表的范围内的大小(因为它仅存储start,stopstep值,计算各个项目和子范围如所须).

所以至少你的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

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

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

  • 有趣的事实:因为你有__getitem__`和`__len__`的`工作实施中,`__iter__`实施实际上是不必要的. (32认同)
  • @ stefan.schwetschke:对,当最初编写补丁时,范围只支持起始值和停止值,最多为`sys.maxsize`,所以有一个上限.与`len(range_object)`相比,数字比较/模数*足够接近常数*对于此处的分析无关紧要. (12认同)
  • @Lucretiel:[在Python 2.3中](https://docs.python.org/2/whatsnew/2.3.html#optimizations),特别添加了一个特殊的`xrangeiterator`,因为它不够快.然后在3.x的某个地方(我不确定它是3.0还是3.2)它被抛出并且他们使用`list`使用的相同`listiterator`类型. (2认同)
  • @MartijnPieters比较两个任意数m和n(任意精度的数量)应为O(log min(m,n)).当m和n的大小和精度存在硬编码上限时,O(1)才是真的. (2认同)

abarnert.. 771

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

一个之间的差range和一list在于,range动态序列; 它不记得所有的价值,它只是记住它start,stopstep,并根据需要创建的值__getitem__.

(作为旁注,如果你print(iter(a)),你会注意到它range使用相同的listiterator类型list.它是如何工作的?除了提供C实现的事实之外,A listiterator没有使用任何特殊的东西,所以它适用于太.)list__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)?

  • 这是非常重要的事情.我想Python 2和3之间的差异可能导致我在这一点上的困惑.无论如何,我应该已经意识到[因为`range`被列出(连同`list`和`tuple`)作为序列类型](https://docs.python.org/3/library/stdtypes.html# typesseq). (7认同)
  • @RickTeachey:实际上,我错了; 在2.6-2.7(和3.0-3.1)中,它_claims_是一个序列,但它仍然只是一个几乎序列.看到我的其他答案. (5认同)
  • @RickTeachey:实际上,在2.6+(我认为;可能是2.5+)中,`xrange`也是一个序列.参见[2.7 docs](https://docs.python.org/2/library/stdtypes.html#sequence-types-str-unicode-list-tuple-bytearray-buffer-xrange).事实上,它总是一个几乎顺序. (4认同)
  • @ThomasAhle:因为`range`在不是整数时不检查类型,因为类型总是有可能`__eq__`与`int`兼容.当然,`str`显然不起作用,但是他们不想通过显式检查_不能存在的所有类型来减慢速度(毕竟,`str`子类可以覆盖`__eq__`和包含在`范围')中. (4认同)
  • 它不是一个迭代器,而是一个序列(就Java而言是可迭代的,C#的IEnumerable)-带有`.__ iter __()`方法的东西,它将返回一个迭代器。依次只能使用一次。 (2认同)

wim.. 356

使用来源,卢克!

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

  1. 检查的数量之间start以及stop
  2. 检查步幅值是否"跳过"我们的号码.

例如,994range(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)

  • @ wizzwizz4从什么时候C支持try/finally?(某些特定于供应商的扩展除外......) (23认同)
  • @brian_o最好用`try:finally:`和`return`代替`goto`来实现... (2认同)

poke.. 133

要添加到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

  • @ChrisWesseling:我认为编辑Martijn的答案在这里是不合适的,足够的信息(足够了).这是一个判断,但人们通常会错误地对其他人的答案做出重大改变. (11认同)

abarnert.. 98

如果您想知道为什么要添加此优化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之前,没有人注意到这个问题.该问题的补丁不仅增加indexcount3.2的range,它也重新工作的优化__contains__(共享相同的数学与index,并直接使用count).** 此更改同样适用于3.2,并且没有向后移植到2.x,因为"它是添加新方法的错误修正".(此时,2.7已经超过了rc状态.)

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


*实际上,你甚至可以免费使用xrange和索引进行迭代,但在2.3 MyIntSubclass(2) in range(5) == False对象中有一个自定义迭代器.然后它们在3.x中丢失,它使用的是相同的_PySequence_IterSearch类型range.__contains__.

**第一个版本实际上重新实现了它,并且错误地得到了细节 - 例如,它会给你range.__contains__.但是,Daniel Stutzbach的补丁更新版本恢复了以前的大部分代码,包括回退到泛型,慢xrange.__contains__于3.2之前[x]range.__contains__在优化不适用时隐式使用.

  • 我怀疑一些核心python开发者偏爱python 2.x的"强烈爱",因为他们想鼓励人们切换到远远优越的python3 :) (12认同)
  • 从这里的评论:[改进`xrange .__ contains _`](http://bugs.python.org/issue1766304),看起来他们没有将它向后移植到Python 2只是为了给用户留下一个惊喜元素太晚了o_O.稍后添加了`count`和`index` [patch](https://hg.python.org/cpython/file/e2dec9c0d13c/Objects/rangeobject.c).当时的文件:https://hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c (4认同)
  • 另外我敢打赌,为旧版本添加新功能是一个巨大的负担.想象一下,如果你去了甲骨文并且说:"看,我正在使用Java 1.4,我应该得到lambda表达式!它们什么都不用." (4认同)
  • @RickTeachey:2.7介于3.1和3.2之间,而不是3.3左右.这意味着当最后一次更改为3.2时,2.7在rc中,这使得bug注释更容易理解.无论如何,我认为他们在回想起时犯了一些错误(特别是假设人们会在`six`这样的库的帮助下通过`2to3`而不是通过双版本代码进行迁移,这就是为什么我们得到像`dict.viewkeys'这样的东西.没有人会使用),并且有一些变化在3.2中来得太晚,但在大多数情况下2.7是令人印象深刻的"最后2.x永远"版本. (3认同)
  • @RickTeachey是的,这只是一个例子.如果我说1.7它仍然适用.这是一个不定性的数量差异.基本上(无偿的)开发人员不能永远在3.x中制作很酷的新东西,并且对于那些不想升级的人来说它向后端移动到2.x. 这是一个巨大而荒谬的负担.你觉得我的推理还有问题吗? (2认同)

Stefan Pochm.. 45

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

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

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

  • 我不会过分夸大切片对象的相似性; 它似乎让更多人感到困惑而不是帮助.(一旦有人意识到这一点,他们开始想知道为什么首先有两种不同的类型,并且需要一些时间来向他们解释.然后他们中的一些去设计其他语言,如Swift,而不用解决它,并且我们得到了各种令人讨厌的问题,他们在最终提出合理的设计之前,他们在5个测试版之间来回徘徊......) (5认同)

Sławomir Len.. 20

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

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

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

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

但:

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

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

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

  • 小心浮动大整数。在大多数机器上,即使`sys.maxsize-float(sys.maxsize)== 0`,`float(sys.maxsize)!= sys.maxsize)`。 (2认同)

Sanan Fatali.. 15

这是类似的实现C#.你可以看到Contains在O(1)时间内是如何完成的.

public struct Range
{
    private readonly int _start;
    private readonly int _stop;
    private readonly int _step;

    // other members omitted for brevity

    public bool Contains(int number)
    {
        // precheck - if the number is not in a valid step point, return false
        // for example, if start=5, step=10, stop=1000, it is obvious that 163 is not in this range (due to remainder)

        if ((_start % _step + _step) % _step != (number % _step + _step) % _step)
            return false;

        // with the help of step sign, we can check borders in linear manner
        int s = Math.Sign(_step);

        // no need if/else to handle both cases - negative and positive step    
        return number * s >= _start * s && number * s < _stop * s;
    }
}


RBF06.. 12

TL; DR

返回的对象range()实际上是一个range对象。该对象实现了迭代器接口,因此您可以按顺序迭代其值,就像生成器,列表或元组一样。

但是,它实现了__contains__接口,该接口实际上是当对象出现在in操作员右侧时调用的接口。该__contains__()方法返回a bool左侧项目是否in在对象中。由于range对象知道其边界和步幅,因此在O(1)中非常容易实现。


归档时间:

查看次数:

175000 次

最近记录:

8 月,2 周 前