Упорядочиваются ли словари в Python 3.6+?
Они вставка заказана[1]. Начиная с Python 3.6, для реализации Python на CPython словари запоминают порядок вставленных элементов. Это считается деталью реализации в Python 3.6; вам нужно использовать OrderedDict если вы хотите вставок упорядоченности что-х гарантированной через другие реализации Python (и другое упорядоченное поведение [1] ).
Начиная с Python 3.7, это больше не является деталью реализации, а становится функцией языка. Из сообщения python-dev от GvR:
Сделай так. "Dict сохраняет порядок вставки" - это правило. Спасибо!
Это просто означает, что вы можете на него положиться. Другие реализации Python также должны предлагать словарь с порядком вставки, если они хотят соответствовать реализации Python 3.7.
Почему реализация словаря Python 3.6 работает лучше[2], чем предыдущая, при сохранении порядка элементов?
По сути, путем сохранения двух массивов.
-
Первый массив, dk_entries, содержит записи (типа PyDictKeyEntry) словаря в том порядке, в котором они были вставлены. Сохранение порядка достигается за счет того, что это массив только для добавления, где новые элементы всегда вставляются в конец (порядок вставки).
-
Второй, dk_indices, содержит индексы для массива dk_entries (то есть значения, указывающие позицию соответствующей записи в dk_entries). Этот массив действует как хеш-таблица. Когда ключ хешируется, он приводит к одному из индексов, хранящихся в dk_indices, и соответствующая запись извлекается путем индексации dk_entries. Поскольку сохраняются только индексы, тип этого массива зависит от общего размера словаря (в пределах от типа int8_t(1 байт) до int32_t<5452906>344 >int64_t (4/8 байт) на 32/64 битовых сборках)
В предыдущей реализации необходимо было выделить разреженный массив типа PyDictKeyEntry и размера dk_size; к сожалению, это также привело к большому количеству пустого пространства, поскольку этому массиву не разрешалось быть более чем 2/3 * dk_size заполненным по соображениям производительности. (и пустое пространство все еще имело размер PyDictKeyEntry!).
Теперь это не так, поскольку сохраняются только требуемые записи (те, которые были вставлены) и разреженный массив типа intX_t (X в зависимости от размера словаря) <54529049344833> s полный сохраняется. Пустое пространство изменено с типа PyDictKeyEntry на intX_t.
Поэтому очевидно, что создание разреженного массива типа PyDictKeyEntry требует гораздо больше памяти, чем разреженный массив для хранения ints.
Вы можете просмотреть полный диалог на сайте Python-Dev относительно этой функции, если интересно, его стоит прочитать.
В первоначальном предложении Раймонда Хеттингера можно увидеть визуализацию используемых структур данных, которая отражает суть идеи.
Например, словарь:
d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
в настоящее время хранится как [keyhash, key, value]:
entries = [['--', '--', '--'],
[-8522787127447073495, 'barry', 'green'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[-9092791511155847987, 'timmy', 'red'],
['--', '--', '--'],
[-6480567542315338377, 'guido', 'blue']]
Вместо этого данные должны быть организованы следующим образом:
indices = [None, 1, None, None, None, 0, None, 2]
entries = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]
Как вы теперь можете визуально видеть, в исходном предложении много места по существу пусто, чтобы уменьшить коллизии и ускорить поиск. Благодаря новому подходу вы уменьшаете требуемый объем памяти, перемещая разреженность туда, где это действительно необходимо, в индексах.
[1]: Я говорю "заказ на вставку", а не "заказ", поскольку при существовании OrderedDict "заказ" предполагает дальнейшее поведение, которое объект `dict` *не обеспечивает*. OrderedDicts являются обратимыми, предоставляют методы, чувствительные к порядку, и, в основном, предоставляют чувствительные к порядку проверки равенства (`==`, `!=`). В настоящее время `dict`ы не предлагают ни одного из этих поведений/методов.
[2]: Новые реализации словарей работают лучше **в отношении памяти**, будучи более компактными; это главное преимущество здесь. Что касается скорости, то разница не столь существенна, есть места, где новый словарь может привести к небольшим регрессиям (поиск по ключу, например), в то время как в других (на ум приходят итерации и изменение размера) повышение производительности должно присутствовать.
В целом, производительность словаря, особенно в реальных ситуациях, улучшается благодаря введенной компактности.
См. эту ветку в списке рассылки Python-Dev: mail.python.org/pipermail/python-dev/2016-September/146327.html, если вы ее еще не видели; это в основном обсуждение этих тем.
Информация здесь от Рэймона Хеттингера, включая рецепт исходного кода для нового dict. Интересно, что он говорит: «В то время, когда это было представлено, настроение было против заказа диктов, поэтому этот [оригинальный] рецепт намеренно заполняет удаленные значения последней записью в списке».
Если теперь предполагается, что kwargs должны быть упорядочены (что является хорошей идеей), а kwargs - это dict, а не OrderedDict, то, я думаю, можно предположить, что ключи dict останутся упорядоченными в будущей версии Python, несмотря на то, что документация говорит об обратном.
@DmitriySintsov Нет, не делай такого предположения. Это была проблема, поднятая во время написания PEP, который определяет функцию сохранения порядка
**kwargs, и поэтому используемая формулировка является дипломатической:**kwargsв подписи функции теперь гарантированно будет порядок вставки- сохранение отображение. Они использовали термин mapping, чтобы не заставлять какие-либо другие реализации упорядочивать dict (и использоватьOrderedDictвнутри) и как способ показать, что это не должно зависеть от дело в том, чтоdictне упорядочен.Хорошее видео объяснение от Рэймонда Хеттингера
@wazoox, порядок и сложность хэш-карты не изменились. Это изменение делает хэш-карту меньше за счет того, что тратится меньше места, а сэкономленное пространство (обычно?) больше, чем занимает вспомогательный массив. Быстрее, меньше, по заказу — вы можете выбрать все 3.
Любой способ автоматически преобразовать
OrderedDictв обычныеdictв Python 3.7, или нужно переключаться вручную, проверяя, какая версия Python работает?@martineau Возможно, стоит отдельного вопроса, но я не знаю. Я думаю, что выигрыш в производительности от переключения будет незначительным. Кроме того, вам может понадобиться
OrderedDict, даже в Python 3.7 coderhelper.com/questions/50872498/…Крис: Хорошие моменты в связанном ответе. Я думаю, что существует большое количество вариантов использования
OrderedDict, в которых не используются эти «расширенные» функции — поэтому я и спросил — но достаточно просто проверить, какая версия Python используется, и выбрать, какую из них вы хотите, когда они могут использоваться взаимозаменяемо.