为什么Python 3中的“10000000000000in range（10000000000001）”这么快？

Question

我的理解是，实际上是an object type in Python 3的range()函数会动态生成其内容，类似于生成器。

在这种情况下，我希望下面这一行占用的时间过多，因为为了确定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源代码和解释。

Answer 1

使用source，卢克！

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

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

这个想法的“肉”在the line中提到：

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

Answer 2

这里的基本误解在于认为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的区别在于a range是一个惰性的或动态的序列；它不记得它的所有值，它只记得它的start、stop和step，并根据需要在__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+和pypy3.x版本碰巧包含了这种优化，而且这显然是一个好主意，而且很容易做到，所以IronPython或newkickasspython3.x没有理由不考虑它。（事实上，CPython 3.0-3.1并不包括它。）

---

如果range实际上是一个生成器，就像my_crappy_range，那么这样测试__contains__是没有意义的，或者至少它的意义是不明显的。如果您已经迭代了前3个值，那么1仍然是in生成器吗？对1的测试是否应该导致它迭代并使用1（或最大到第一个值>= 1）的所有值？

Answer 3

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

该对象还实现^{} hook，如果您的数字是其范围的一部分，将计算。计算是一个O（1）常数时间运算。不需要扫描范围内所有可能的整数。

从^{} object documentation：

The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).

所以至少，您的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 issue。