собеседования - список вопросов python




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

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


TL; DR

Объект, возвращаемый range() , фактически является объектом range . Этот объект реализует интерфейс итератора, так что вы можете последовательно просматривать его значения, как генератор, но он также реализует интерфейс __contains__ который фактически вызывается, когда объект появляется справа от оператора in . Метод __contains__() возвращает логическое значение того, находится ли элемент в объекте. Поскольку объекты range знают свои границы и шаг, это очень легко реализовать в O (1).


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

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

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

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

но:

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

(в этом случае оптимизация range , поэтому, если python получает неожиданное значение с плавающей точкой, python сравнивает все числа)

Вы должны знать о деталях реализации, но на них не следует полагаться, потому что это может измениться в будущем.


Если вам интересно, почему эта оптимизация была добавлена ​​в 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 xrange , даже если она все еще обрабатывает одно и то же «очень немного поведения ". Никто не заметил эту проблему до выпуска 9213 . Патч для этой проблемы не только добавил index и count к range 3,2, но и переработал оптимизированный __contains__ (который использует ту же математику с index и напрямую используется count ). ** Это изменение также коснулось 3.2 и не было перенесено в 2.x, потому что «это исправление, которое добавляет новые методы». (На данный момент 2.7 уже прошел статус rc.)

Таким образом, было две возможности вернуть эту оптимизацию в 2.7, но оба они были отклонены.

* На самом деле, вы даже получаете итерацию бесплатно только с индексированием, но в 2.3 объекты xrange получили пользовательский итератор.

** Первая версия фактически переопределила его, и неправильно MyIntSubclass(2) in range(5) == False детали - например, это даст вам MyIntSubclass(2) in range(5) == False . Но обновленная версия патча Даниэля Штутцбаха восстановила большую часть предыдущего кода, в том числе откат к общему медленному _PySequence_IterSearch который до _PySequence_IterSearch 3.2 range.__contains__ _PySequence_IterSearch неявно использовался, когда оптимизация не применяется.


Используйте 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 итерационному поиску диапазона, используя _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)

Основное недоразумение заключается в том, что мы думаем, что 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 использует тот же тип list что и 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 )?


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







python-internals