Заказаны ли словари в Python 3.6+?

Словари упорядочены в Python 3.6 (по крайней мере, в рамках реализации CPython) в отличие от предыдущих воплощений. Это кажется существенным изменением, но это только короткий параграф в документации. Он описывается как подробности реализации CPython, а не как языковая функция, но также подразумевает, что это может стать стандартом в будущем.

Как новая реализация словаря работает лучше, чем старая, сохраняя порядок элементов?

Вот текст из документации:

dict() теперь использует "компактное" представление, впервые разработанное PyPy. Использование памяти новым dict() на 20-25% меньше по сравнению с Python 3.5. PEP 468 (сохранение порядка **kwargs в функции.) Реализуется этим. Сохраняющий порядок аспект этой новой реализации считается деталью реализации, и на него не следует полагаться (это может измениться в будущем, но желательно иметь эту новую реализацию dict в языке в течение нескольких выпусков, прежде чем изменять спецификацию языка. предписывать семантику сохранения порядка для всех текущих и будущих реализаций Python, что также помогает сохранить обратную совместимость со старыми версиями языка, где все еще действует случайный порядок итераций, например, Python 3.5). (Предоставлено INADA Naoki в выпуске 27350. Идея, изначально предложенная Раймондом Хеттингером.)

Обновление декабря 2017 года: dictСохранение порядка вставки гарантировано для Python 3.7

Источник

6 ответов

Решение

Заказаны ли словари в 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.

Как работает Питон 3.6 реализация словаря работает лучше [2], чем старая, сохраняя порядок элементов?

По сути, сохраняя два массива.

  • Первый массив, dk_entries, содержит записи ( типа PyDictKeyEntry) для словаря в том порядке, в котором они были вставлены. Порядок сохранения достигается за счет того, что он является массивом только для добавления, где новые элементы всегда вставляются в конце (порядок вставки).

  • Второй, dk_indices, держит индексы для dk_entries массив (то есть значения, которые указывают положение соответствующей записи в dk_entries). Этот массив действует как хеш-таблица. Когда ключ хешируется, это приводит к одному из индексов, хранящихся в dk_indices и соответствующая запись извлекается путем индексации dk_entries, Поскольку сохраняются только индексы, тип этого массива зависит от общего размера словаря (в зависимости от типа int8_t (1 байт) в int32_t / int64_t (4 / 8 байт) на 32 / 64 немного строит)

В предыдущей реализации разреженный массив типа PyDictKeyEntry и размер dk_size должен был быть выделен; к сожалению, это также привело к большому количеству пустого пространства, так как этому массиву было запрещено превышать 2/3 * dk_size полный по причинам производительности. (и пустое пространство все еще было PyDictKeyEntry размер!).

Сейчас это не так, поскольку сохраняются только необходимые записи (те, которые были вставлены) и редкий массив типа intX_t (X в зависимости от размера dict) 2/3 * dk_size S полный хранится. Пустое пространство изменено с типа PyDictKeyEntry в intX_t,

Итак, очевидно, создание разреженного массива типа PyDictKeyEntry гораздо больше памяти, чем разреженный массив для хранения int s.

Вы можете увидеть полный разговор о Python-Dev относительно этой функции, если вам интересно, это хорошее чтение.

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

Например, словарь:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

в настоящее время хранится как:

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]: новые реализации словаря работают лучше с памятью, будучи спроектированы более компактно; это главное преимущество здесь. С точки зрения скорости, разница не столь существенна, есть места, где новый дикт может привести к небольшим регрессиям ( например, поиск по ключевым словам), в то время как в других (на ум приходят итерации и изменение размеров) должно наблюдаться повышение производительности.

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

Источник

Ниже приводится ответ на первый вопрос:

Должен ли я использовать dict или же OrderedDict в Python 3.6?

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

Сохраняющий порядок аспект этой новой реализации считается деталью реализации и на него не следует полагаться

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

Сделайте свой код будущим:)

Здесь есть спор об этом.

РЕДАКТИРОВАТЬ: Python 3.7 будет держать это как функцию увидеть

Источник

Обновление: Гвидо ван Россум объявил в списке рассылки, что на Python 3.7 dicts во всех реализациях Python должны сохранять порядок вставки.

Источник

Я хотел добавить к обсуждению выше, но не имею репутации, чтобы комментировать.

Python 3.8 еще не совсем выпущен, но он даже будет включать в себя reversed() функция на словарях (убрав еще одно отличие от OrderedDict,

Dict и dictviews теперь итерируемы в обратном порядке вставки, используя reversed(). (Предоставлено Rémi Lapeyre в bpo-33462.) Посмотрите, что нового в Python 3.8

Я не вижу упоминания об операторе равенства или других особенностях OrderedDict поэтому они все еще не совсем одинаковы.

Источник

Чтобы полностью ответить на этот вопрос в 2020 году, позвольте мне процитировать несколько утверждений из официальных документов Python:

Изменено в версии 3.7: Порядок словаря гарантированно соответствует порядку вставки. Такое поведение было деталью реализации CPython из 3.6.

Изменено в версии 3.7: Порядок словаря гарантированно соответствует порядку вставки.

Изменено в версии 3.8: Словари теперь обратимы.

Словари и просмотр словарей обратимы.

Заявление о OrderedDict против Dict:

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

Источник

Изменено в версии 3.7 : порядок словаря гарантированно соответствует порядку вставки. Такое поведение было деталью реализации CPython из версии 3.6.

Источник
Другие вопросы по тегам