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

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

Почему это? Есть []и {}(и , вероятно , ()и ''тоже) сразу перейти назад на копии какой - нибудь пустой складе литерала , а их явно Названные аналоги ( 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и, кажется, затрагивает похожий сценарий «буквально против глобального»; возможно, это стоит рассмотреть.

Потому []и {}являются буквальным синтаксис . 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()являются отдельными объектами. Их имена должны быть разрешены, стек должен быть задействован для передачи аргументов, фрейм должен быть сохранен для последующего извлечения, и должен быть сделан вызов. Это все занимает больше времени.

Для пустого регистра это означает, что у вас есть по крайней мере a LOAD_NAME(который должен искать в глобальном пространстве имен, а также в __builtin__модуле ), за которым следует a 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:

>>> 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('_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

Потому listчто это функция для преобразования, скажем, строки в список объектов, в то время []как используется для создания списка с нуля. Попробуйте это (может иметь больше смысла для вас):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Пока

y = ["wham bam"]
>>> y
["wham bam"]

Дает вам фактический список, содержащий все, что вы положили в него.

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

Вот разбивка исполнения для каждого из них, 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это не простой человек, который немедленно вызовет функцию, это не может. Вместо этого он захватывает объект из стека, захватывает все аргументы стека и затем переключается в зависимости от типа объекта; это:

• PyCFunction_Type? Нет, это list, listне относится к типуPyCFunction
• PyMethodType? Нет, смотри предыдущий.
• PyFunctionType? Нет, смотри предыдущий.

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

Эта функция снова делает некоторые проверки для определенных типов функций (что я не могу понять почему), а затем, после создания dict для kwargs, если требуется , продолжает вызывать _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, что это еще один парень, который вносит свой вклад здесь.

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

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

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

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

Почему []быстрее чем 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()ищет вызываемый объект и затем вызывает его.

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