据我所知,range()函数实际上是Python 3中的一种对象类型,它动态生成其内容,类似于生成器。

在这种情况下,我预计下一行将花费大量时间,因为为了确定1万亿是否在该范围内,必须生成1万亿值:

1_000_000_000_000_000 in range(1_000_000_000_000_001)

此外:似乎无论我加上多少个零,计算或多或少都需要相同的时间(基本上是瞬时的)。

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

# count by tens
1_000_000_000_000_000_000_000 in range(0,1_000_000_000_000_000_000_001,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的优化不足)。poke和wim的答案为感兴趣的人提供了相关的C源代码和解释。


当前回答

TL;博士

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

但它也实现了__contains__接口,当对象出现在in运算符的右侧时,实际上会调用该接口。__contains__()方法返回一个bool,表示in左侧的项是否在对象中。因为范围对象知道它们的边界和步幅,所以这很容易在O(1)中实现。

其他回答

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

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

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

为了补充Martijn的答案,这是源代码的相关部分(在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

TL;博士

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

但它也实现了__contains__接口,当对象出现在in运算符的右侧时,实际上会调用该接口。__contains__()方法返回一个bool,表示in左侧的项是否在对象中。因为范围对象知道它们的边界和步幅,所以这很容易在O(1)中实现。

对于较大的x值,请尝试x-1 in(i代表i in range(x)),这使用生成器理解来避免调用范围__包含优化。

由于优化,很容易将给定的整数与最小和最大范围进行比较。在Python3中,range()函数速度如此之快的原因是这里我们对边界使用数学推理,而不是直接迭代range对象。因此,为了解释这里的逻辑:

检查数字是否在开始和停止之间。检查步长精度值是否超过我们的数字。

举个例子,997在范围(4、1000、3)内,因为:4<=997<1000,以及(997-4)%3==0。