首页 文章

为什么Python 3中的“1000000000000000在范围内（1000000000000001）”如此之快？

提问于
浏览 次
1509

据我所知， 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's first answer，以便对 range 在Python 3中成为一个完整的序列意味着什么，以及关于Python实现中 __contains__ 函数优化的潜在不一致性的一些信息/警告 . abarnert's other answer详细介绍了一些内容，并为那些对Python 3中优化背后的历史感兴趣的人提供了链接（并且缺乏Python 2中 xrange 的优化） . 答案by poke和by wim为感兴趣的人提供相关的C源代码和解释 .

python performance python-3.x range python-internals

7 回答

  • 1506

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

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

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

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

    但：

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

    （在这种情况下 range 没有优化，所以既然收到意外的浮点数，python会比较所有数字）

    回复于
  • 10

    这里的根本误解在于认为 range 是一个发电机 . 它's not. In fact, it'不是任何一种迭代器 .

    你可以很容易地说出来：

    >>> 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 ， stop 和 step ，并在 __getitem__ 上按需创建值 .

    （作为附注，如果你 print(iter(a)) ，你会注意到 range 使用与 list 相同的 listiterator 类型 . 这是如何工作的？ 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 ？如果对 1 进行测试会导致它迭代并消耗所有值 1 （或者高达第一个值 >= 1 ）？

    回复于
  • 39

    使用source，卢克！

    在CPython中， range(...).__contains__ （方法包装器）最终将委托给一个简单的计算，该计算检查该值是否可能在该范围内 . 这里速度的原因是我们正在使用 mathematical reasoning about the bounds, rather than a direct iteration of the range object . 解释使用的逻辑：

    • 检查数字是否在 start 和 stop 之间，并且

    • 检查步幅值是否为"step over"我们的数字 .

    例如， 994 在 range(4, 1000, 2) 中，因为：

    • 4 <= 994 < 1000 ，和

    • (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);
}

    the line中提到了"meat"的想法：

    /* 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)
    回复于
  • 114

    要添加到Martijn的答案，这是the source的相关部分（在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 对象（在Python 3中为 int ），它将使用 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
    回复于
  • 624

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

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

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

    回复于
  • 305

    如果您想知道为什么将此优化添加到 range.__contains__ ，以及为什么它未添加到2.7中的 xrange.__contains__ ：

    首先，正如Ashwini Chaudhary发现的那样，issue 1766304被明确地开放以优化 [x]range.__contains__ . 这个补丁是accepted and checked in for 3.2，但没有向后移植到2.7，因为"xrange has behaved like this for such a long time that I don't see what it buys us to commit the patch this late."（当时2.7差不多了 . ）

    与此同时：

    最初， xrange 是一个不太完整的序列对象 . 正如the 3.1 docs所说：

    Range对象的行为很少：它们只支持索引，迭代和len函数 .

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

    然后，作为实施Abstract Base Classes PEP的一部分，重要的是要弄清楚应该将哪些内置类型标记为实现哪些ABC，并且 xrange / range 声称实现 collections.Sequence ，即使它仍然只处理相同的"very little behavior" . 在issue 9213之前，没有人注意到这个问题 . 该问题的补丁不仅将 index 和 count 添加到3.2的 range ，它还重新优化了 __contains__ （与 index 共享相同的数学运算，并由 count 直接使用） . ** This change进入3.2为好吧，并没有向后移植到2.x，因为"it's a bugfix that adds new methods" . （此时，2.7已经超过了rc状态 . ）

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

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

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

    回复于
  • 86

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

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

    来自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 = 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 issue遏制测试 .

    回复于

相关问题