Почему "1000000000000000 in range(1000000000000001)" так быстро работает?

Question

Насколько я понимаю, функция 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(), зачёт чего от такой быстрый?

_{перевод вопроса why is 1000000000000000 in range(1000000000000001) so fast in python 3 от участника @RicksupportsMonica}

Answer 1

В Python 3 объект range() не производит числа сразу. Это интеллектуальный объект последовательности, который производит числа по запросу. Все, что он содержит - это значения начала, остановки и шага, а затем, когда вы перебираете объект, на каждой итерации вычисляется следующее целое число.

Объект также реализует object.__contains__ hook и вычисляет, является ли ваш номер частью его диапазона. Вычисление - это операция (почти) с постоянным временем*. Нет необходимости просматривать все возможные целые числа в диапазоне.

Из документации по объекту 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

Здесь все еще отсутствуют некоторые вещи, которые поддерживает настоящий range (например, методы .index или .count, хеширование, проверка равенства или срезы), но они должны дать вам представление.

Я также упростил реализацию __contains__, чтобы сосредоточиться только на целочисленных тестах; если вы даете реальному объекту range нецелочисленное значение (включая подклассы int), запускается медленное сканирование, чтобы увидеть, есть ли совпадение, так же, как если бы вы использовали тест на сдерживание для списка всех содержащихся значений. Это было сделано для продолжения поддержки других числовых типов, которые просто поддерживают проверку равенства с целыми числами, но не должны также поддерживать целочисленную арифметику. См. Исходную проблему Python, в которой реализован тест на сдерживание.

*Почти постоянное время, потому что целые числа Python не ограничены, и поэтому математические операции также растут со временем по мере роста N, что делает эту операцию O(log N). Поскольку все это выполняется в оптимизированном коде C, а Python сохраняет целочисленные значения в 30-битных фрагментах, вам не хватит памяти, прежде чем вы заметите какое-либо влияние на производительность из-за размера задействованных здесь целых чисел.

_{перевод ответа о участника @MartijnPieters}

Answer 2

Небольшое дополнение (внезапно большое!)

На самом деле __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)

это не больно.

БЛОГ НА HUSL

Почему "1000000000000000 in range(1000000000000001)" так быстро работает?

Ответы (2 шт):