Вопрос: Почему «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). ответы совать а также по wim предоставить соответствующий исходный код C и объяснения для заинтересованных лиц.


1321


источник


Ответы:


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

Объект также реализует 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 который реализовал тест на локализацию.


1308



Основное недоразумение здесь состоит в том, что 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)?


541



Использовать источник , Люк!

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

  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);
}

«Мясо» идеи упоминается в линия :

/* 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)

277



Чтобы добавить к ответу Мартинна, это важная часть источник (в 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

104



Если вам интересно Зачем эта оптимизация была добавлена ​​к range.__contains__, и почему это не было добавлен xrange.__contains__в 2.7:

Во-первых, как обнаружил Ашвини Чодхари, выпуск 1766304 было открыто открыто для оптимизации [x]range.__contains__, Патч для этого был принято и зарегистрировано за 3.2 , но не обратился к 2.7, потому что «xrange так долго вел себя так долго, что я не вижу, что он покупает для фиксации патча в последнее время». (2,7 почти не было в этом пункте.)

В то же время:

Первоначально, xrangeбыл объектом не совсем последовательной. В виде 3.1 документа сказать:

Объекты диапазона имеют очень малое поведение: они поддерживают только индексирование, итерацию и 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__было неявно использовано, когда оптимизация не применяется.


80



The other answers explained it well already, but I'd like to offer another experiment illustrating the nature of range objects:

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

As you can see, a range object is an object that remembers its range and can be used many times (even while iterating over it), not just a one-time generator.


34



It's all about lazy approach to the evaluation, and some extra optimalization of range. Values in ranges don't need to be computed until real use, or even futher due to extra optimalization.

By the way your integer is not such big, consider sys.maxsize

sys.maxsize in range(sys.maxsize) is pretty fast

due to optimization - it's easy to compare given integer just with min and max of range.

but:

float(sys.maxsize) in range(sys.maxsize) is pretty slow.

(in this case there is no optimization in range, so since receive unexpected float, python will compare all numbers)


2