主页 / 问题 / 1205809
Accepted
Danis
Asked:2021-11-17 17:17:57 +0000 UTC2021-11-17 17:17:57 +0000 UTC

为什么“10000000000000000 在范围内（1000000000000001）”这么快？

  • 772

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

在这种情况下，我预计下一行会花费不合理的长时间，因为必须生成千万亿的值来确定 1 千万亿是否在该范围内：

1000000000000000 in range(1000000000000001)

此外，似乎无论我添加多少个零，计算或多或少都会花费相同的时间（大部分是即时的）。

我也尝试过这样的事情，但计算仍然几乎是瞬时的：

1000000000000000000000 in range(0,1000000000000000000001,10) # С шагом в десять

如果我尝试实现自己的功能range，结果就不那么好了！！

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

对象的引擎盖下发生了什么range()，为什么偏移量如此之快？

@RicksupportsMonica翻译的问题为什么1000000000000000 in range(1000000000000001)在 python 3 中如此之快

python

2 个回答

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

    该对象还实现object.__contains__并计算您的数字是否在其范围内。计算是（几乎）恒定时间操作*。无需查看范围内所有可能的整数。

    来自对象的文档range

    该类型range相对于普通列表或元组的优点是范围对象将始终占用相同（小）量的内存，而不管它所代表的范围大小（因为它只存储 的值start，stop并且step，根据需要计算单个元素和子范围）。

    您的对象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

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

    我还简化了实现__contains__，只关注整数测试；如果您给一个真实对象一个range非整数值（包括子类int），则会开始慢速扫描以查看是否存在匹配项，就像您在所有包含值的列表上使用包含测试一样。这样做是为了继续支持其他数字类型，它们仅支持整数相等测试，但不应该也支持整数算术。请参阅实现包含测试的原始Python 问题。

    *几乎恒定的时间，因为 Python 整数不受限制，所以数学运算也随着时间增长N，这使得这个运算O(log N)。因为这一切都是在优化的 C 代码中完成的，并且 Python 将整数值存储在 30 位块中，所以在注意到此处涉及的整数大小对性能产生任何影响之前，您将耗尽内存。

    关于成员@MartijnPieters的答案翻译

    • 20
  2. Best Answer

    一个小小的补充（突然变大了！）

    它实际上__contains__看起来像这样

    def __contains__(self, num):
    if type(num) is int or type(num) is bool:
        быстрый поиск
    else:
        полный перебор

    这使得可以使用__eq__所需对象的覆盖运算符

    class MyClass:
    def __eq__(self, other):
        return other == 111

print(MyClass() in range(1000)) # True

    因此，将花费更多时间来执行以下计算。

    'x' in range(1000000000)          # несмотря на то, что 'x' там быть не может в принципе
999999999.0 in range(1000000000)  # несмотря на то, что 999999999.0 = 999999999

    但是这个表达式将立即被评估

    False in range(1, 1000000000)     # несмотря на то, что False is not 0

    而且又慢了

    class MyInt(int): pass

MyInt(-1) in range(1000000000)    # несмотря на то, что MyInt не переопределяет сравнение

    嗯，值得一提的是，__getitem__它还有效地实现了切片

    >>> range(11, 1000, 3)[5::10]
range(26, 1001, 30)

    因此，你可以毫不犹豫地做

    range(len(a))[::-1]

    代替

    range(len(a) - 1, -1, -1)

    它不疼。

    • 16

相关问题