Python的“range()”中的“in”运算符是否已优化?[复制]

巨蟒3 range() 对象不会立即生成数字;它是 smart sequence object 产生数字 . 它只包含开始值、停止值和步长值,然后在迭代对象时,每次迭代都会计算下一个整数。

object.__contains__ hook ,和 计算 ^* . 不需要扫描范围内所有可能的整数。

range() object documentation

的优势 range list tuple 范围对象总是占用相同(少量)的内存,而不管它代表的范围大小(因为它只存储 start , stop step 值,根据需要计算单个项和子范围)。

所以至少,你的 对象可以:

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

这还缺了几件事那真的 支架(如 .index() 或 .count() 方法、散列、相等性测试或切片),但应该给您一个想法。

我还简化了 __contains__ 范围() int ),则会启动一个慢速扫描以查看是否存在匹配项,就像对包含的所有值的列表使用包含测试一样。这样做是为了继续支持其他数值类型,这些类型恰好支持整数的相等性测试,但不希望也支持整数算术。看原稿 Python issue 实施了遏制试验。

* 接近

最根本的误解是 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))
[]

什么 范围 实际上,是一个序列,就像一个列表。你甚至可以测试一下:

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

两者之间的区别 范围 还有一个 list 那是a吗 范围 是一个 懒惰的 或 序列;它不记得它的所有值,它只记得它的 start , stop step ,并在上按需创建值 __getitem__ .

print(iter(a)) ,你会注意到的 范围 使用相同的 listiterator 类型as 列表 列表迭代器 列表 除了它提供了 __获取项目__ ,所以它对 范围 也是。)

Sequence.__contains__ 必须是常数时间事实上,对于像 列表 不是的。但是没有什么能说明这一点 不能 range.__contains__ (val - start) % step ,但在处理负步骤时会有一些额外的复杂性)而不是实际生成和测试所有的值,那么为什么呢 不应该

但语言中似乎没有 保证 没有 包括在内。)

实际上是个发电机,就像 my_crappy_range ,那么测试就没有意义了 __contains__ 这种方式,或者至少它的合理方式不会很明显。如果已经迭代了前3个值,则为 1 仍然 in 发电机?应该测试 使它迭代并使用 1 (或达到第一个值 >= 1 )?

source ,卢克!

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

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)

为了补充Martijns的答案,这是 the source (在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 对象(即 int range_contains_long 函数来确定结果。这个函数主要检查 ob 在指定的范围内(虽然在C中它看起来有点复杂)。

如果不是 内景 对象,则返回到迭代,直到找到值(或不找到)。

整个逻辑可以这样翻译成pseudo 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__ ,以及原因 不是的 添加到 xrange.__contains__ 在2.7中:

首先,正如Ashwini Chaudhary发现的, issue 1766304 [x]range.__contains__ accepted and checked in for 3.2

同时:

原来, xrange 是一个不完全序列的对象。作为 the 3.1 docs 说:

Range对象的行为非常少:它们只支持索引、迭代和 len 功能。

润智 对象实际上支持其他一些自动生成索引和 , 包括 __contains__ (通过线性搜索)。但当时没人认为这是值得的。

Abstract Base Classes PEP,重要的是要弄清楚哪些内置类型应该标记为实现哪些abc,以及 润智 range collections.Sequence ,尽管它仍然只处理相同的“非常小的行为”。没人注意到这个问题直到 issue 9213 . 该问题的修补程序不仅增加了 index 和 count 范围 ,它也重新工作优化 __包含__ (与 指数 ,并由直接使用 计数 ^** This change

所以,有两次机会将这个优化后传到2.7,但是都被拒绝了。

_{*事实上,你甚至可以通过索引免费获得迭代,但是 in 2.3 润智 对象具有自定义迭代器。}

_{**第一个版本实际上重新实现了它,并且得到了错误的细节,例如,它会给你带来 MyIntSubclass(2) in range(5) == False . 但是danielstutzbach的补丁更新版本恢复了以前的大部分代码,包括通用的,缓慢的回退 _PySequence_IterSearch 3.2之前 范围。包含__}

其他答案已经很好地解释了这一点,但我想提供另一个实验来说明靶场物体的性质:

>>> 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对象是一个记住其范围并可以多次使用的对象(即使是在迭代它时),而不仅仅是一次性生成器。

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

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

sys.maxsize in range(sys.maxsize)

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

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

(在这种情况下,在

您应该了解实现细节,但不应依赖于它,因为这可能在将来发生变化。

太长,读不下去了

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

也 实现 __contains__ 接口,当对象出现在 in 操作员。这个 __contains__() 方法返回 bool 是否在 在里面 范围 对象知道它们的界限和步幅,这很容易在O(1)中实现。

2. 原因是 范围() 函数在Python3中是如此之快,在这里我们使用数学推理来确定边界,而不是直接迭代range对象。
3. • 检查数字是否在开始和停止之间。
   • 检查步进精度值是否超出我们的数字。

4. 997在范围内(41000,3) 因为:

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

尝试 x-1 in (i for i in range(x)) 大的 x 值,它使用生成器理解来避免调用 range.__contains__ 优化。

TLDR;