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

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

они вставки приказал^[1]. Начиная с Python 3.6, для реализации CPython Python, словари запомните порядок вставленных элементов. это считается деталью реализации в Python 3.6; вы должны использовать OrderedDict Если вы хотите заказать вставку, это гарантированный через другие реализации Python (и другое упорядоченное поведение^[1]).

начиная с Python 3.7, это больше не деталь реализации и вместо этого становится функцией языка. из сообщения python-dev от GvR:

сделать так. "Диктатор держит порядок вставки" - это постановление. Спасибо!

это просто означает, что вы можете на это положиться. Другой реализации 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 в зависимости от размера дикт) 2/3 * dk_sizes полный сохраняется. Пустое пространство изменилось с типа PyDictKeyEntry до intX_t.

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

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

---

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

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

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 "ordered" предполагает дальнейшее поведение, которое dict объект не дает. OrderedDicts являются обратимыми, обеспечивают чувствительные к порядку методы и, в основном, обеспечивают тесты на равенство порядка (==,!=). dicts в настоящее время не предлагают ни одного из этих поведений/методов.}

---

_{[2]: новые словарные реализации работают лучше память мудрого путем быть конструированным более компактно; это главное преимущество здесь. Скорость мудрая, разница не так радикальна, есть места, где новый дикт может ввести небольшие регрессии (key-lookups, например) в то время как в других (итерация и изменение размера приходят на ум) повышение производительности должно быть подарок.}

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