Are dictionaries ordered in Python 3.6+?

Упорядочены ли словари в Python 3.6+?

Порядок вставки словарей установлен в Python 3.6. Это описано как деталь реализации CPython, а не как языковая функция. В документации говорится:

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

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

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

Переведено автоматически

Ответ 1

Упорядочены ли словари в 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 byte) до int32_t/int64_t (4/8 bytes) при 32/64 битовых сборках)

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

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

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

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

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

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

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

в настоящее время хранится как [keyhash, ключ, значение]:

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

Ответ 2

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

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

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

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

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

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

Об этом здесь ведутся дебаты.

РЕДАКТИРОВАТЬ: Python 3.7 сохранит это как функцию см.

Ответ 3

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

Ответ 4

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

Python 3.8 включает в себя reversed() функцию для словарей (удаляя другое отличие от OrderedDict.

Dict и dictviews теперь можно повторять в обратном порядке вставки с помощью reversed(). (Внесено Реми Лапейром в bpo-33462.) Посмотрите, что нового в python 3.8

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