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




вопросы на (7)

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


Answers

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

Объект также реализует object.__contains__ hook и вычисляет, является ли ваш номер частью его диапазона. Вычисление представляет собой операцию постоянного времени 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__ чтобы сосредоточиться только на целых тестах; если вы даете объекту real range() нецелое значение (включая подклассы int ), запускается медленное сканирование, чтобы увидеть, есть ли совпадение, точно так же, как если бы вы использовали тест сдерживания против списка всех содержащихся значений , Это было сделано для продолжения поддержки других числовых типов, которые, как оказалось, поддерживали тестирование равенства с помощью целых чисел, но не ожидали поддержки целочисленной арифметики. См. Исходную проблему Python, которая реализовала тест сдерживания.


Чтобы добавить к ответу 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 - это генератор. Это не. На самом деле это не какой-то итератор.

Вы можете сказать это довольно легко:

>>> 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 )?


Это касается ленивого подхода к оценке и некоторой дополнительной оптимизации range . Значения в диапазонах не обязательно должны вычисляться до реального использования или даже после дополнительной оптимизации.

Кстати, ваше целое число не такое большое, рассмотрите sys.maxsize

sys.maxsize in range(sys.maxsize) довольно быстро

благодаря оптимизации - легко сравнивать заданное целое число с минимальным и максимальным диапазоном.

но:

float(sys.maxsize) in range(sys.maxsize) довольно медленный .

(в этом случае нет оптимизации в range , поэтому, поскольку вы получаете неожиданный float, python будет сравнивать все числа)


Используйте source , Люк!

В CPython 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)

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

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

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


Эмулятор, включенный в вашу (старую) версию Eclipse, очень медленный.

Последние эмуляторы работают быстрее, чем они используются в 2010 году. Обновите SDK / IDE.

Лично я использую настоящий телефон для выполнения своих тестов. Это быстрее, и тесты более реалистичны. Но если вы хотите протестировать свое приложение на множестве разных версий Android и не хотите покупать несколько телефонов, вам придется использовать эмулятор время от времени.





python performance python-3.x range python-internals