Почему создание python dict из списка кортежей в 3 раза медленнее, чем из kwargs - PullRequest
0 голосов
/ 03 сентября 2018

Существует несколько способов создания словаря в Python, например:

keyvals = [('foo', 1), ('bar', 'bar'), ('baz', 100)]

dict(keyvals)

и

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

dict(**dkwargs)

Когда вы тестируете эти

In [0]: %timeit dict(keyvals)
667 ns ± 38 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [1]: %timeit dict(**dkwargs)
225 ns ± 7.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

вы видите, что первый метод почти в 3 раза медленнее, чем второй. Почему это?

Ответы [ 3 ]

0 голосов
/ 03 сентября 2018

dkwargs - это уже словарь, поэтому вы в основном делаете его копию. Вот почему это намного быстрее.

0 голосов
/ 03 сентября 2018

Краткий ответ (TL; DR)

Это потому, что в первом тесте реализация CPython dict создаст новый dict из списка, но во втором копируется только словарь. Копирование занимает меньше времени, чем разбор списка.

Дополнительная информация

Рассмотрим этот код:

import dis
dis.dis("dict([('foo', 1), ('bar', 'bar'), ('baz', 100)])", depth=10)
print("------------")
dis.dis("dict({'foo': 1, 'bar': 'bar', 'baz': 100})", depth=10)

Где

Модуль dis поддерживает анализ байт-кода CPython с помощью разбирать его.

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

  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (('foo', 1))
              4 LOAD_CONST               1 (('bar', 'bar'))
              6 LOAD_CONST               2 (('baz', 100))
              8 BUILD_LIST               3
             10 CALL_FUNCTION            1
             12 RETURN_VALUE
------------
  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (1)
              4 LOAD_CONST               1 ('bar')
              6 LOAD_CONST               2 (100)
              8 LOAD_CONST               3 (('foo', 'bar', 'baz'))
             10 BUILD_CONST_KEY_MAP      3
             12 CALL_FUNCTION            1
             14 RETURN_VALUE

Из вывода вы можете увидеть:

  1. Оба вызова должны загрузить имя dict, которое будет вызываться.
  2. После этого первый метод загружает список в память (BUILD_LIST), тогда как второй создает словарь (BUILD_CONST_KEY_MAP) (см. здесь )
  3. По этой причине, когда вызывается функция dict (шаг CALL_FUNCTION (см. здесь )), во втором случае она значительно короче, поскольку словарь уже создан, поэтому он просто делает копию вместо того, чтобы перебирать список для создания хеш-таблицы.

Примечание : с помощью байт-кода вы не можете окончательно решить, что CALL_FUNCTION делает это, так как его реализация написана на C, и только читая его, вы действительно можете это знать (см. Ответ Martijn Pieters для точного объяснения того, как эта часть работает). Тем не менее, это помогает увидеть, как объект словаря уже создан за пределами dict() (пошагово, а не синтаксически в примере), в то время как со списком это не так.

Редактировать

Чтобы было ясно, когда вы говорите

Существует несколько способов создания словаря в python

Это правда, что, делая:

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

Вы создаете словарь в том смысле, что интерпретатор преобразует выражение в объект словаря, хранящийся в памяти, и указывает на него переменную dkwargs. Однако, выполнив: dict(**kwargs) или, если вы предпочитаете dict(kwargs), вы на самом деле не создаете словарь , а просто копируете уже существующий объект (и важно подчеркнуть копирование ):

>>> dict(dkwargs) is dkwargs
False

dict(kwargs) заставляет Python создать новый объект; однако это не означает, что он должен перестроить объект. На самом деле, эта операция бесполезна, потому что на практике это равные объекты (хотя и не один и тот же).

>>> id(dkwargs)
2787648914560
>>> new_dict = dict(dkwargs)
>>> id(new_dict)
2787652299584
>>> new_dict == dkwargs
True
>>> id(dkwargs) is id(new_dict)
False

Где id:

Возвращает «идентичность» объекта. Это целое число, которое гарантированно будет уникальным и постоянным для этого объекта в течение его жизни [...]

Сведения о реализации CPython : Это адрес объекта в памяти.

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

0 голосов
/ 03 сентября 2018

dict(**kwargs) передается в готовом словаре, поэтому Python может просто скопировать уже существующую внутреннюю структуру.

Список кортежей, с другой стороны, требует итерации, проверки, хеширования и размещения результатов в новой пустой таблице. Это не так быстро.

Словарь Python реализован в виде хеш-таблицы и динамически увеличивается по мере добавления ключей с течением времени; они начинаются с малого, и по мере необходимости создается новая, более крупная хеш-таблица, данные (ключи, значения и хэши) копируются. Это все невидимо в коде Python, но изменение размера требует времени. Но когда вы используете dict(**kwargs) (или dict(other_dict) CPython (реализация Python по умолчанию, которую вы использовали для тестирования), вы можете использовать ярлык: начинать с достаточно большой хеш-таблицы сразу . тот же трюк с последовательностью кортежей, потому что вы не можете знать заранее, не будет ли в последовательности повторяющихся ключей.

Для получения дополнительной информации см. Исходный код C типа dict, в частности, dict_update_common реализация (которая вызывается из dict_init()); это вызывает либо PyDict_MergeFromSeq2() для случая последовательности кортежей, либо PyDict_Merge(), когда передаются аргументы ключевого слова.

Функция PyDict_MergeFromSeq2() выполняет итерацию последовательности, проверяет каждый результат на наличие двух элементов, а затем, по сути, вызывает .__setitem__(key, value) в словаре. Это может потребовать изменения размера словаря в какой-то момент!

Функция PyDict_Merge() (через dict_merge()) специально определяет, был ли передан обычный словарь, затем выполняет быстрый путь , который изменяет размеры внутренних структур один раз , а затем копирует хэши и структуру из исходного словаря напрямую, используя insertdict() вызовы (следуйте по пути override == 1, поскольку override был установлен в 1, когда целевой словарь пуст, что всегда имеет место для dict(**kwargs)). Простое изменение размера и непосредственное использование внутренних данных намного быстрее, гораздо меньше работы!

Все это детали реализации, специфичные для CPython. Другие реализации Python, такие как Jython, IronPython и PyPy, могут самостоятельно принимать решения о том, как работают внутренние компоненты типа dict, и будут демонстрировать различные различия в производительности для одних и тех же операций.

...