python - structures - Почему[] быстрее, чем list()?




python structures (4)

Почему [] быстрее, чем list() ?

Основная причина в том, что Python обрабатывает list() точно так же, как пользовательскую функцию, что означает, что вы можете перехватить ее, добавив псевдоним в list и сделать что-то другое (например, использовать свой собственный подклассный список или, возможно, деку).

Он сразу создает новый экземпляр встроенного списка с помощью [] .

Мое объяснение стремится дать вам интуицию для этого.

объяснение

[] широко известен как буквальный синтаксис.

В грамматике это называется «отображением списка». Из документов :

Отображение списка - это, возможно, пустая серия выражений, заключенная в квадратные скобки:

list_display ::=  "[" [starred_list | comprehension] "]"

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

Короче говоря, это означает, что создается встроенный объект list типов.

Обойти это невозможно - это означает, что Python может сделать это так быстро, как может.

С другой стороны, list() может быть перехвачен при создании встроенного list с помощью встроенного конструктора списка.

Например, скажем, мы хотим, чтобы наши списки создавались с шумом:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Затем мы можем перехватить list имен в глобальной области видимости на уровне модуля, а затем, когда мы создаем list , мы фактически создаем наш подтипированный список:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Точно так же мы могли бы удалить его из глобального пространства имен

del list

и поместите его во встроенное пространство имен:

import builtins
builtins.list = List

И сейчас:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

И обратите внимание, что отображение списка создает список безоговорочно:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Мы, вероятно, делаем это только временно, поэтому давайте отменим наши изменения - сначала удалим новый объект List из встроенных команд:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

О нет, мы потеряли след оригинала.

Не волнуйтесь, мы все еще можем получить list - это тип литерала списка:

>>> builtins.list = type([])
>>> list()
[]

Так...

Почему [] быстрее, чем list() ?

Как мы уже видели - мы можем переписать list - но мы не можем перехватить создание литерального типа. Когда мы используем list мы должны выполнить поиск, чтобы увидеть, есть ли что-нибудь там.

Затем мы должны позвонить тому, что мы вызываем. Из грамматики:

Вызов вызывает вызываемый объект (например, функцию) с возможно пустой серией аргументов:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Мы видим, что он делает то же самое для любого имени, а не только для списка:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Для [] нет вызова функции на уровне байт-кода Python:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Это просто идет прямо к построению списка без каких-либо поисков или вызовов на уровне байт-кода.

Заключение

Мы продемонстрировали, что list может быть перехвачен с помощью пользовательского кода с использованием правил области видимости, и что list() ищет вызываемый объект и затем вызывает его.

Принимая во внимание, что [] является отображением списка, или литералом, и таким образом избегает поиска имени и вызова функции.

Недавно я сравнил скорости обработки [] и list() и с удивлением обнаружил, что [] работает более чем в три раза быстрее, чем list() . Я запустил один и тот же тест с {} и dict() и результаты были практически идентичны: [] и {} оба заняли около 0,128 сек / миллион циклов, в то время как list() и dict() примерно 0,428 сек / миллион циклов каждый.

Почему это? Do [] и {} (а также, вероятно, () и '' ) немедленно передают копии некоторого пустого стандартного литерала, в то время как их явно названные аналоги ( list() , dict() , tuple() , str() ) полностью пойти о создании объекта, есть ли у них на самом деле элементы?

Я понятия не имею, как эти два метода отличаются, но я хотел бы узнать. Я не смог найти ответ в документации или на SO, и поиск пустых скобок оказался более проблематичным, чем я ожидал.

Я получил результаты синхронизации, вызвав timeit.timeit("[]") и timeit.timeit("list()") , а также timeit.timeit("{}") и timeit.timeit("dict()") , сравнить списки и словари соответственно. Я использую Python 2.7.9.

Недавно я обнаружил, « Почему, если True медленнее, чем если 1? », Который сравнивает производительность if True с if 1 и, кажется, затрагивает похожий сценарий «буквально против глобального»; возможно, это стоит рассмотреть.


Ответы здесь замечательные, по сути и полностью охватывают этот вопрос. Я опущу еще один шаг вниз от байт-кода для интересующихся. Я использую самый последний репозиторий CPython; более старые версии ведут себя аналогично в этом отношении, но возможны небольшие изменения.

Вот BUILD_LIST выполнения для каждого из них, BUILD_LIST для [] и CALL_FUNCTION для list() .

Инструкция BUILD_LIST :

Вы должны просто посмотреть ужас:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Ужасно запутанный, я знаю. Вот как это просто:

  • Создайте новый список с помощью PyList_New (это в основном выделяет память для нового объекта списка), oparg сигнализирует о количестве аргументов в стеке. Прямо к сути.
  • Убедитесь, что ничего не пошло не так с if (list==NULL) .
  • Добавьте любые аргументы (в нашем случае это не выполняется), расположенные в стеке, с помощью PyList_SET_ITEM (макрос).

Не удивительно, что это быстро! Это специально для создания новых списков, ничего больше :-)

Инструкция CALL_FUNCTION :

Вот первое, что вы видите, когда смотрите на код, обрабатывающий CALL_FUNCTION :

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Выглядит довольно безобидно, верно? Ну, к сожалению, нет, call_function не простой человек, который немедленно вызовет функцию, не может. Вместо этого он захватывает объект из стека, захватывает все аргументы стека и затем переключается в зависимости от типа объекта; это:

Мы вызываем тип list , аргумент, переданный в call_function - PyList_Type . CPython теперь должен вызывать универсальную функцию для обработки любых вызываемых объектов с именем _PyObject_FastCallKeywords , или больше вызовов функций.

Эта функция снова делает некоторые проверки для определенных типов функций (что я не могу понять почему), а затем, после создания dict для kwargs, если требуется , продолжает вызывать _PyObject_FastCallDict .

_PyObject_FastCallDict наконец-то нас куда-то _PyObject_FastCallDict ! После выполнения еще большего количества проверок он захватывает слот tp_call из type переданного нами type , то есть захватывает type.tp_call . Затем он приступает к созданию кортежа из аргументов, переданных с помощью _PyStack_AsTuple и, наконец, наконец-то можно сделать вызов !

tp_call , который соответствует type.__call__ вступает во владение и, наконец, создает объект списка. Он вызывает списки __new__ который соответствует PyType_GenericNew и выделяет для него память с помощью PyType_GenericAlloc : на самом деле это та часть, где он, наконец, догоняет PyList_New . Все предыдущие необходимы для обработки объектов в общем виде.

В конце type_call вызывает list.__init__ и инициализирует список любыми доступными аргументами, а затем мы возвращаемся тем же путем, которым пришли. :-)

Наконец, LOAD_NAME имя LOAD_NAME , это еще один парень, который вносит свой вклад.

Легко видеть, что при работе с нашим вводом Python, как правило, должен перепрыгивать через обручи, чтобы на самом деле найти подходящую функцию C для выполнения этой работы. Он не имеет права немедленно вызывать его, потому что он динамический, кто-то может замаскировать list ( и это делают многие люди ), и нужно выбрать другой путь.

Вот где list() сильно проигрывает: исследующий Python должен выяснить, какого черта он должен делать.

С другой стороны, буквальный синтаксис означает ровно одну вещь; это не может быть изменено и всегда ведет себя заранее определенным образом.

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


Потому что [] и {} являются буквальным синтаксисом . Python может создавать байт-код только для создания списка или словаря объектов:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list() и dict() являются отдельными объектами. Их имена должны быть разрешены, стек должен быть задействован для передачи аргументов, фрейм должен быть сохранен для последующего извлечения, и должен быть сделан вызов. Это все занимает больше времени.

Для пустого регистра это означает, что у вас есть как минимум LOAD_NAME (который должен искать в глобальном пространстве имен, а также в модуле __builtin__ ), за которым следует CALL_FUNCTION , который должен сохранить текущий кадр:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

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

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

Несовпадение времени, вероятно, является столкновением хэша словаря. Вычтите это время из времени для вызова этих объектов и сравните результат со временем для использования литералов:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Таким образом, необходимость вызова объекта занимает дополнительные 1.00 - 0.31 - 0.30 == 0.39 секунды на 10 миллионов вызовов.

Вы можете избежать затрат на глобальный поиск, timeit глобальные имена псевдонимам (используя настройку timeit , все, что вы привязываете к имени, является локальным):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

но вы никогда не сможете преодолеть эту стоимость CALL_FUNCTION .


list() требует глобального поиска и вызова функции, но [] компилируется в одну инструкцию. Увидеть:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None




literals