Вопрос-Ответ

Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3?

Почему "1000000000000000 в диапазоне (1000000000000001)" так быстро в Python 3?

Насколько я понимаю, range() функция, которая на самом деле является типом объекта в Python 3, генерирует свое содержимое "на лету", подобно генератору.

В таком случае я ожидал, что следующая строка займет чрезмерное количество времени, потому что для определения, находится ли 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() объект под капотом, что делает его таким быстрым?


Ответ Мартинса Питерса был выбран из-за его полноты, но также см. Первый ответ абарнерта для хорошего обсуждения того, что значит range быть полноценной последовательностью в Python 3, и некоторую информацию / предупреждение относительно потенциальной несогласованности в __contains__ оптимизации функций во всех реализациях Python. другой ответ абарнерта содержит более подробные сведения и ссылки для тех, кто интересуется историей оптимизации в Python 3 (и отсутствием оптимизации xrange в Python 2). Ответы от poke и от wim предоставляют соответствующий исходный код C и пояснения для тех, кто заинтересован.

Переведено автоматически
Ответ 1

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

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

Из range() документации по объекту:


Преимущество range типа перед обычным list or tuple заключается в том, что объект range всегда будет занимать одинаковый (небольшой) объем памяти, независимо от размера диапазона, который он представляет (поскольку он хранит только значения start, stop и step, вычисляя отдельные элементы и поддиапазоны по мере необходимости).


Итак, как минимум, ваш range() объект будет делать:

class my_range:
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('my_range object index out of range')

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

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

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


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

Ответ 2

Фундаментальное недоразумение здесь заключается в том, что 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

Разница между a range и a list в том, что a range - это ленивая или динамическая последовательность; она не запоминает все свои значения, она просто запоминает свои start, stop и step, и создает значения по запросу в __getitem__.

(В качестве дополнительного примечания, если вы print(iter(a)) заметите, что range использует тот же listiterator тип, что и list. Как это работает? A listiterator не использует ничего особенного в list за исключением того факта, что он предоставляет реализацию __getitem__ на C, поэтому для 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)?

Ответ 3

Используй исходный код, Люк!

В CPython, range(...).__contains__ (оболочка метода) в конечном итоге делегирует простое вычисление, которое проверяет, может ли значение находиться в диапазоне. Причина скорости здесь в том, что мы используем математические рассуждения о границах, а не прямую итерацию объекта range. Для объяснения используемой логики:


  1. Убедитесь, что число находится между start и stop, и

  2. Убедитесь, что значение шага не "перешагивает" наше число.

Например, 994 находится в range(4, 1000, 2), потому что:


  1. 4 <= 994 < 1000, и

  2. (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);
}

"Суть" идеи упоминается в строках комментариев:

/* positive steps: start <= ob < stop */
/* negative steps: stop < ob <= start */
/* 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)
Ответ 4

Чтобы добавить к ответу Мартиня, это соответствующая часть исходного кода (в C, поскольку объект range написан в машинном коде):

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 объект, он возвращается к итерации до тех пор, пока не найдет значение (или нет).

Вся логика может быть переведена на псевдопитон следующим образом:

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
python performance python-3.x