В 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
Здесь все еще отсутствуют некоторые вещи, которые поддерживает настоящий range
(например, методы .index
или .count
, хеширование, проверка равенства или срезы), но они должны дать вам представление.
Я также упростил реализацию __contains__
, чтобы сосредоточиться только на целочисленных тестах; если вы даете реальному объекту range
нецелочисленное значение (включая подклассы int
), запускается медленное
сканирование, чтобы увидеть, есть ли совпадение, так же, как если бы вы использовали тест на сдерживание для списка всех содержащихся значений. Это было сделано для продолжения поддержки других числовых типов, которые просто поддерживают проверку равенства с целыми числами, но не должны также поддерживать целочисленную арифметику. См. Исходную проблему Python, в которой реализован тест на сдерживание.
*Почти постоянное время, потому что целые числа Python не ограничены, и поэтому математические операции также растут со временем по мере роста N
, что делает эту операцию O(log N)
. Поскольку все это выполняется в оптимизированном коде C, а Python сохраняет целочисленные значения в 30-битных фрагментах, вам не хватит памяти, прежде чем вы заметите какое-либо влияние на производительность из-за размера задействованных здесь целых чисел.
перевод ответа о участника @MartijnPieters