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

470

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

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

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

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

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

python python-3.x dictionary python-internals python-3.6 Chris_Rands
источник

2

Смотрите эту ветку в списке рассылки Python-Dev: mail.python.org/pipermail/python-dev/2016-September/146327.html, если вы его еще не видели; это в основном дискуссия вокруг этих предметов.

mgc

1

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

Дмитрий Синцов

4

@DmitriySintsov Нет, не делайте этого предположения. Эта проблема была поднята во время написания PEP, которая определяет функцию сохранения порядка **kwargsи, как таковая, используемая формулировка является дипломатической: **kwargsв сигнатуре функции теперь гарантированно отображается отображение, сохраняющее порядок вставки . Они использовали термин mapping , чтобы не заставлять никакие другие реализации делать упорядоченный dict (и использовать OrderedDictвнутренне) и как способ показать, что это не должно зависеть от того факта, что dictis не упорядочен.

Димитрис Фасаракис Хиллиард

7

Хорошее видео объяснение от Рэймонда Хеттингера

Алекс

1

@wazoox, порядок и сложность хэш-карты не изменились. Это изменение делает хэш-карту меньше, тратя меньше места, а сэкономленное пространство (обычно?) Больше, чем занимает вспомогательный массив. Быстрее, меньше, заказано - вы можете выбрать все 3.

Джон Ла Рой

513

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

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

Димитрис Фасаракис Хиллиард
источник

15

Итак, что происходит, когда элемент удален? это entriesизменяется список? или пустое место сохраняется? или это время от времени сжимается?

njzk2

18

@ njzk2 Когда элемент удаляется, соответствующий индекс заменяется DKIX_DUMMYзначением, -2а запись в entryмассиве заменяется наNULL , когда при вставке новые значения добавляются в массив записей, пока не удалось различить, но довольно точно, когда индексы заполняются за 2/3порог, выполняется изменение размера. Это может привести к сокращению вместо роста, если DUMMYсуществует много записей.

Димитрис Фасаракис Хиллиард

3

@Chris_Rands Нет, единственная реальная регрессия, которую я видел, находится на трекере в сообщении Виктора . Кроме этой микробенчмарки, я не видел никаких других проблем / сообщений, указывающих на серьезную разницу в скорости при реальной рабочей нагрузке. Есть места, где новый dict может вводить небольшие регрессии (например, поиск ключей), в то время как в других (на ум приходит итерация и изменение размера) будет иметь место повышение производительности.

Димитрис Фасаракис Хиллиард

3

Исправление в части изменения размера : словари не меняют размер при удалении элементов, они пересчитывают при повторной вставке. Таким образом, если с помощью dict создается d = {i:i for i in range(100)}и .popвсе элементы без вставки, размер не изменится. Когда вы добавляете к нему снова, d[1] = 1соответствующий размер вычисляется и размер дикта изменяется.

Димитрис Фасаракис Хиллиард

6

@Chris_Rands Я уверен, что он останется. Дело в том, что причина, по которой я изменил свой ответ, чтобы удалить общие утверждения о « dictупорядоченности», dictне упорядочены в том смысле, в каком OrderedDictони. Примечательной проблемой является равенство. dicts имеют порядок, нечувствительный ==, OrderedDicts имеют порядок, чувствительный. Дампы OrderedDictи переходы dictsна сравнение, чувствительные к порядку, могут привести к серьезным сбоям в старом коде. Я предполагаю, что единственное, что может измениться в OrderedDicts, это его реализация.

Димитрис Фасаракис Хиллиард

67

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

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

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

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

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

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

Там есть дебаты о том, что здесь .

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

Maresh
источник

1

Похоже, что если они не имели в виду, что это реальная функция, а только детали реализации, то они не должны даже включать это в документацию.

xji

3

Я не уверен насчет вашей правки. поскольку гарантия распространяется только на Python 3.7, я предполагаю, что рекомендации для Python 3.6 не изменились, то есть диктанты упорядочены в CPython, но не рассчитывают на это

Chris_Rands

25

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

fjsj
источник

2

Теперь, когда порядок ключей является официальным стандартом, какова цель OrderedDict? Или это сейчас избыточно?

Джонни Вафли

2

Я предполагаю, что OrderedDict не будет избыточным, потому что у него есть move_to_endметод, и его равенство чувствительно к порядку: docs.python.org/3/library/… . Смотрите примечание к ответу Джима Фасаракиса Хиллиарда.

FJSJ

@JonnyWaffles см. Ответ Джима и эти вопросы и ответы stackoverflow.com/questions/50872498/…

Chris_Rands

3

Если вы хотите, чтобы ваш код выполнялся одинаково на 2.7 и 3.6 / 3.7 +, вам нужно использовать OrderedDict

лодочный кодер

3

Скорее всего, скоро будет "UnorderedDict" для людей, которые любят поспорить со своими соображениями по соображениям безопасности; p

ZF007

9

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

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

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

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

rkengler
источник

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

Ответы: