Почему "1000000000000000 в диапазоне (1000000000000001)" так быстро в Python 3?
Насколько я понимаю, что range() Функция, которая на самом деле является типом объекта в Python 3, генерирует свое содержимое на лету, подобно генератору.
В этом случае я ожидал, что следующая строка займет неоправданное количество времени, потому что для определения того, находится ли 1 квадриллион в этом диапазоне, должны быть сгенерированы квадриллионные значения:
1000000000000000 in range(1000000000000001)
Более того: кажется, что независимо от того, сколько нулей я добавляю, вычисление более или менее занимает одинаковое количество времени (в основном, мгновенное).
Я также пробовал такие вещи, но расчет все еще почти мгновенный:
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
Если я попытаюсь реализовать свою собственную функцию диапазона, результат не так хорош!!
def my_crappy_range(N):
i = 0
while i < N:
yield i
i += 1
return
Что range() объект делает под капотом, что делает это так быстро?
Ответ Martijn Pieters был выбран для его полноты, но также см . Первый ответ abarnert для хорошего обсуждения того, что это значит для range быть полноценной последовательностью в Python 3, и некоторая информация / предупреждение относительно возможного несоответствия для __contains__ оптимизация функций в реализациях Python. Другой ответ abarnert входит в некоторые более подробные и предоставляет ссылки для тех, кто интересуется историей, стоящей за оптимизацией в Python 3 (и отсутствием оптимизации xrange в Python 2). Ответы poke и wim предоставляют соответствующий исходный код на C и объяснения для тех, кто заинтересован.
13 ответов
Питон 3 range() объект не производит числа сразу; это умный объект последовательности, который производит числа по требованию. Все, что он содержит, это ваши значения start, stop и step, а затем, когда вы выполняете итерацию по объекту, каждое целое число вычисляется следующим целым числом.
Объект также реализует object.__contains__ крюк, и вычисляет, является ли ваш номер частью его диапазона. Расчет - это операция O(1) с постоянным временем. Нет необходимости сканировать все возможные целые числа в диапазоне.
От range() документация по объекту:
Преимущество
rangeнаберите по обычномуlistили жеtupleявляется то, что объект диапазона всегда будет занимать один и тот же (небольшой) объем памяти, независимо от размера диапазона, который он представляет (так как он хранит только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 = stop, start
else:
lo, hi = start, stop
self.length = ((hi - lo - 1) // abs(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, в которой реализован тест на содержание.
Основное недоразумение заключается в том, что мы думаем, что 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))
[]
Какие range на самом деле, это последовательность, как список. Вы даже можете проверить это:
>>> 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
Разница между range и list это range ленивая или динамическая последовательность; он не помнит все свои значения, он просто помнит его start, stop, а также stepи создает значения по требованию __getitem__,
(Как примечание, если вы print(iter(a))вы заметите, что range использует то же самое listiterator введите как list, Как это работает? listiterator не использует ничего особенного в list за исключением того факта, что он обеспечивает реализацию C __getitem__так что работает нормально range тоже.)
Теперь нет ничего, что говорит о том, что Sequence.__contains__ должно быть постоянным временем - на самом деле, для очевидных примеров таких последовательностей, как listэто не так. Но нет ничего, что говорит, что это не может быть. И это легче реализовать range.__contains__ просто математически проверить ((val - start) % step, но с некоторой дополнительной сложностью, чтобы справиться с отрицательными шагами), чем сгенерировать и протестировать все значения, так почему бы не сделать это лучше?
Но в языке, похоже, нет ничего, что гарантировало бы это. Как указывает Ашвини Чаудхари, если вы дадите ему нецелое значение, вместо того, чтобы конвертировать в целое число и выполнять математический тест, он вернется к итерации всех значений и сравнивает их одно за другим. И только потому, что версии CPython 3.2+ и PyPy 3.x содержат эту оптимизацию, и это очевидная хорошая идея и ее легко реализовать, нет никаких причин, по которой IronPython или NewKickAssPython 3.x не могли ее исключить. (И фактически CPython 3.0-3.1 не включал его.)
Если range на самом деле был генератор, как my_crappy_rangeтогда не было бы смысла проверять __contains__ таким образом, или, по крайней мере, то, как это имеет смысл, не будет очевидным. Если вы уже повторили первые 3 значения, это 1 еще in генератор? Должно ли тестирование на 1 заставить его повторяться и потреблять все значения до 1 (или до первого значения >= 1)?
Используйте источник, Люк!
В CPython range(...).__contains__ (обертка метода) в конечном итоге делегирует простой расчет, который проверяет, может ли значение находиться в диапазоне. Причина скорости здесь в том, что мы используем математическое обоснование границ, а не прямую итерацию объекта диапазона. Для объяснения используемой логики:
- Проверьте, что число между
startа такжеstop, а также - Убедитесь, что значение шага не "перешагивает" наш номер.
Например, 994 в range(4, 1000, 2) так как:
4 <= 994 < 1000, а также(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);
}
"Мясо" идеи упоминается в строке:
/* 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)
Чтобы добавить к ответу 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 объекты (что является int в Python 3), он будет использовать 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
Если вам интересно, почему эта оптимизация была добавлена в range.__contains__ и почему он не был добавлен в xrange.__contains__ в 2.7:
Во-первых, как обнаружил Эшвини Чаудхари, проблема 1766304 была открыта явно для оптимизации [x]range.__contains__, Патч для этого был принят и проверен на 3.2, но не перенесен в 2.7, потому что "xrange вел себя так долго, что я не вижу, что он покупает, чтобы зафиксировать патч так поздно". (2.7 было почти в тот момент.)
В то же время:
Первоначально, xrange был не совсем последовательным объектом. Как сказано в документах 3.1:
Объекты Range имеют очень небольшое поведение: они поддерживают только индексирование, итерацию и
lenфункция.
Это было не совсем так; xrange Объект на самом деле поддерживает несколько других вещей, которые приходят автоматически с индексацией и len * в том числе __contains__ (через линейный поиск). Но никто не думал, что в то время стоило делать их полными последовательностями.
Затем, в рамках реализации PEP абстрактных базовых классов, было важно выяснить, какие встроенные типы следует пометить как реализующие ABC, и xrange / range заявлено о реализации collections.Sequence, хотя он все еще обрабатывал только то же самое "очень маленькое поведение". Никто не заметил эту проблему до выпуска 9213. Патч для этой проблемы не только добавлен index а также count до 3,2 range, он также переработал оптимизированный __contains__ (который разделяет ту же математику с index и используется непосредственно count). ** Это изменение также коснулось 3.2 и не было перенесено в 2.x, потому что "это исправление, которое добавляет новые методы". (На данный момент 2.7 уже прошел статус rc.)
Таким образом, было две возможности вернуть эту оптимизацию в 2.7, но оба они были отклонены.
* На самом деле, вы даже получаете итерацию бесплатно с len и индексация, но в 2.3 xrange объекты получили пользовательский итератор. Который они тогда потеряли в 3.x, который использует тот же listiterator введите как list ,
** Первая версия фактически реализовала его, и неправильно поняла детали - например, это дало бы вам MyIntSubclass(2) in range(5) == False , Но обновленная версия патча Даниэля Штутцбаха восстановила большую часть предыдущего кода, включая откат к общей медленной _PySequence_IterSearch что до 3.2 range.__contains__ был неявно используется, когда оптимизация не применяется.
Другие ответы уже объяснили это хорошо, но я хотел бы предложить еще один эксперимент, иллюстрирующий природу объектов диапазона:
>>> 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) довольно быстро
благодаря оптимизации - легко сравнить данное целое число только с минимальным и максимальным диапазоном.
но:
float(sys.maxsize) in range(sys.maxsize) довольно медленно
(в этом случае нет оптимизации в range, так как получит неожиданный float, python будет сравнивать все числа)
TL;DR
Объект, возвращаемый range() на самом деле range объект. Этот объект реализует интерфейс итератора, так что вы можете последовательно перебирать его значения, как генератор, но он также реализует __contains__ интерфейс, который на самом деле то, что вызывается, когда объект появляется в правой части in оператор. __contains__() Метод возвращает bool того, находится ли элемент в объекте. поскольку range объекты знают свои границы и шаг, это очень легко реализовать в O(1).
- Благодаря оптимизации очень легко сравнивать заданные целые числа только с минимальным и максимальным диапазоном.
- Причина того, что функция range() настолько быстрая в Python3, заключается в том, что здесь мы используем математическое обоснование границ, а не прямую итерацию объекта диапазона.
- Итак, для объяснения логики здесь:
- Проверьте, находится ли число между началом и остановкой.
- Проверьте, не превышает ли значение точности шага наше число.
Например, 997 находится в диапазоне (4, 1000, 3), потому что:
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
Пытаться x-1 in (i for i in range(x)) для больших x values, который использует понимание генератора, чтобы избежать вызова range.__contains__ оптимизация.
Вот аналогичная реализация в C#, Вы можете увидеть, как Contains сделано за O(1) время.
public struct Range
{
private readonly int _start;
private readonly int _stop;
private readonly int _step;
//other methods/properties omitted
public bool Contains(int number)
{
// precheck: if the number isnt in valid point, return false
// for example, if start is 5 and step is 10, then its impossible that 163 be in range at any interval
if ((_start % _step + _step) % _step != (number % _step + _step) % _step)
return false;
// v is vector: 1 means positive step, -1 means negative step
// this value makes final checking formula straightforward.
int v = Math.Abs(_step) / _step;
// since we have vector, no need to write if/else to handle both cases: negative and positive step
return number * v >= _start * v && number * v < _stop * v;
}
}
TL; DR; range - это арифметический ряд, поэтому он может очень легко вычислить, есть ли объект там. Он мог бы даже получить его индекс, если бы он был списком, как очень быстро.
__contains__метод сравнивает непосредственно с началом и концом диапазона