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


2 Answers

Основное недоразумение здесь заключается в том, что 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__ тестировать __contains__ таким образом, или, по крайней мере, так, как это имеет смысл, не будет очевидным. Если вы уже повторили первые 3 значения, еще 1 in генераторе? Если тестирование на 1 заставляет его итерировать и потреблять все значения до 1 (или до первого значения >= 1 )?

Question

Я понимаю, что функция 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 и объяснения для тех, кто заинтересован.




Чтобы добавить к ответу 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



Другие ответы объяснили это хорошо уже, но я хотел бы предложить еще один эксперимент, иллюстрирующий характер объектов диапазона:

>>> 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]

Как вы можете видеть, объект диапазона - это объект, который помнит свой диапазон и может использоваться много раз (даже при итерации по нему), а не только одноразовый генератор.




Related