为什么“10**15在范围内（10**15 1）”在Python 3中如此之快？

Question

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

在这种情况下，我预计下一行将花费大量时间，因为为了确定1万亿（10**15）是否在范围内，必须生成1万亿值：

1_000_000_000_000_000 in range(1_000_000_000_000_001)

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

我也尝试过类似的方法，但计算仍然几乎是即时的：

# count by tens
10**21 in range(0, 10**21+1, 10)

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

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

range（）对象在引擎盖下做什么使它如此快速？

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

Answer 1

匿名用户

使用来源，卢克！

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

1. 检查该数字是否介于开始和停止之间，以及
2. 检查步幅值是否没有“步过”我们的数字。

例如，< code>994在< code >范围(4，1000，2)内，因为:

< li > <代码> 4

完整的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);
}

评论行中提到了这个想法的“实质”：

/* positive steps: start <= ob < stop */
/* negative steps: stop < ob <= start */
/* result = ((int(ob) - start) % step) == 0 */ 

最后，请查看代码段底部的range_contains函数。如果精确类型检查失败，则我们不使用所描述的聪明算法，而是使用＜code＞_PySequence_IterSearch

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

Answer 2

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

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

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

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

范围和列表之间的区别在于范围是惰性或动态序列；它不会记住它的所有值，它只记住它的＜code＞开始，＜code＞停止，和＜code＞步骤，并根据需要在＜code＞上创建值。

（作为补充说明，如果您打印（iter（a）），您会注意到范围使用与列表相同的listiteratortype。这是如何工作的？listiterator不使用任何关于list，除了它提供了__getitem__的C实现之外，因此它也适用于范围

现在，没有什么说Sequence。__contains__必须是恒定时间——事实上，对于像list这样明显的序列示例，它不是。但是没有什么说它不可能是。实现范围更容易。__contains__只是用数学方法检查它（（val-start）%step，但是有一些额外的复杂性来处理负步骤），而不是实际生成和测试所有的值，那么为什么它不应该用更好的方法来做呢？

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

如果＜code＞range1是否仍然是生成器中的？对1的测试是否会导致它迭代并消耗1之前的所有值（或之前的第一个值）

Answer 3

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

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

从< code>range()对象文档中:

与常规的< code>list或< code>tuple相比，< code>range类型的优势在于，range对象将始终占用相同(少量)的内存，而不管它表示的范围大小(因为它只存储< code>start 、< code>stop和< code>step值，根据需要计算单个项目和子范围)。

因此，您的 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

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

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

*几乎恒定的时间，因为Python整数是无界的，因此数学运算也会随着N的增长而随时间增长，因此这是一个O（log N）运算。由于它都是在优化的C代码中执行的，并且Python将整数值存储在30位的块中，因此在看到由于此处涉及的整数大小而造成的任何性能影响之前，您已经耗尽了内存。