为什么在 Python 3 中 “范围(10000000000000001)” 如此之快?

据我了解, 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 优化背后的历史(以及 Python 2 中缺乏xrange优化)感兴趣的人提供了链接。 pokewim 的答案 感兴趣的人提供了相关的 C 源代码和说明。

答案

Python 3 range()对象不会立即产生数字。它是一个智能序列对象,可按需生成数字。它所包含的只是您的开始,结束和步长值,然后在对对象进行迭代时,每次迭代都会计算出下一个整数。

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

range()对象文档中

与常规listtuple相比, range类型的优势在于,范围对象将始终占用相同(少量)的内存,无论其表示的范围大小如何(因为它仅存储startstopstep值) ,根据需要计算单个项目和子范围)。

因此,至少,您的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 问题

此处的基本误解是认为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

rangelist之间的区别在于, range惰性序列或动态序列。它不会记住所有的值,只记住它的startstopstep ,并根据需要在__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 + 和 PyPy 3.x 版本恰好包含此优化,而且这是一个显而易见的好主意且易于实现,所以 Iron Iron 或 NewKickAssPython 3.x 没有理由不能放弃它。 (实际上,CPython 3.0-3.1 并未包含它。)


如果range实际上是一个生成器,例如my_crappy_rangemy_crappy_range这种方式测试__contains__毫无意义,或者至少它的意义并不明显。如果你已经重复了前 3 倍的值是1还是in发电机?测试1是否应该使其迭代并消耗所有值直到1 (或直到第一个值>= 1 )?

使用消息来源 ,卢克!

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

  1. 检查数字是否在startstop之间,以及
  2. 检查步幅值是否不会 “超过” 我们的数字。

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

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

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

如果您想知道为什么将此优化添加到range.__contains__ ,为什么将其添加到 2.7 中的xrange.__contains__

首先,正如 Ashwini Chaudhary 所发现的那样,明确打开了1766304 版以优化[x]range.__contains__接受了此修补程序并签入了 3.2 版本 ,但没有回迁到 2.7 版本,因为 “xrange 表现得如此之久,以至于我看不到它为什么让我们提交最新的修补程序。” (当时 2.7 快要淘汰了。)

与此同时:

最初, xrange是一个非相当序列的对象。正如3.1 文档所说:

范围对象的行为很少:它们仅支持索引,迭代和len函数。

这不是真的。一个xrange对象实际上支持索引和len自动附带的其他一些功能, *包括__contains__ (通过线性搜索)。但是,没有人认为有必要在那时将它们完整地序列化。

然后,作为实现 “ 抽象基类” PEP 的一部分,重要的是弄清楚应将哪些内置类型标记为实现哪些 ABC,并且xrange / range声称实现了collections.Sequence ,即使它仍然只处理相同的 “非常小行为”。在发布 9213之前,没有人注意到这个问题。针对该问题的补丁不仅将indexcount添加到 3.2 的range ,而且还对经过优化的__contains__ (与index具有相同的数学运算,并直接由count )进行了重新设计。 ** 此更改也适用于 3.2,并且没有回迁到 2.x,因为 “这是一个添加了新方法的错误修正”。 (此时,2.7 已经超过了 rc 状态。)

因此,有两次机会可以将此优化回溯到 2.7,但都被拒绝了。


* 实际上,您甚至可以单独使用索引免费获得迭代,但是在 2.3 xrange对象中获得了自定义迭代器。

** 第一个版本实际上重新实现了它,并弄错了详细信息,例如,它将为您MyIntSubclass(2) in range(5) == False 。但丹尼尔 · 斯图茨巴赫(Daniel Stutzbach)的补丁更新版本恢复了以前的大多数代码,包括对 3.2 之前的range.__contains__的通用_PySequence_IterSearch的回退_PySequence_IterSearch在优化不适用时隐式使用了。

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

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

如您所见,范围对象是一个可以记住其范围的对象,并且可以多次使用(即使在其上进行迭代),而不仅仅是一次生成器。

这都是关于评估的惰性方法range一些额外优化 。直到实际使用时才需要计算范围内的值,或者由于额外的优化甚至不需要进一步计算。

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

sys.maxsize in range(sys.maxsize) 相当快

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

但:

float(sys.maxsize) in range(sys.maxsize) 相当慢

(在这种情况下, range没有优化,因此,如果 python 收到意外的 float 值,则 python 将比较所有数字)

您应该了解实现细节,但不应依赖它,因为将来可能会改变。

TL; DR

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

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

这是 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;
    }
}
  1. 由于优化,将给定的整数与最小和最大范围进行比较非常容易。
  2. 在 Python3 中range()函数之所以如此之快,是因为这里我们对边界使用数学推理,而不是范围对象的直接迭代。
  3. 所以在这里解释逻辑:
    • 检查数字是否在开始和停止之间。
    • 检查步长精度值是否不超过我们的数字。
  4. 例如, 997 在 range(4,1000,3)内是因为:

    4 <= 997 < 1000, and (997 - 4) % 3 == 0.