До Python 3.5 (включительно) порядок словарей не гарантируется.Сначала в словарь вставляется пара ключ-значение A, а в словарь вставляется пара ключ-значение B, но при печати списка ключей словаре, вы обнаружите, что B может стоять перед A .
Но начиная с Python 3.6 словари стали упорядоченными. Сначала вы вставляете пару ключ-значение A, затем вставляете пару ключ-значение B, затем, когда вы печатаете список ключей, вы обнаружите, что B находится после A.
Мало того, начиная с Python 3.6, следующие три операции обхода стали более эффективными, чем до Python 3.5:
for key in 字典
for value in 字典.values()
for key, value in 字典.items()
Начиная с Python 3.6 размер памяти, занимаемой словарем, в зависимости от количества пар ключ-значение в словаре составляет всего 30%~95% от исходного.
Какие оптимизации сделал Python 3.6 для словарей? Чтобы проиллюстрировать эту проблему, нам нужно поговорить об основных принципах словарей до Python 3.5 (включительно).
Когда мы инициализируем пустой словарь, нижний слой CPYthon инициализирует двумерный массив с 8 строками и 3 столбцами, как показано на следующей диаграмме:
my_dict = {}
'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---]]
'''
Теперь давайте добавим часть данных в словарь:
my_dict['name'] = 'kingname'
'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指针, 指向kingname的指针],
[---, ---, ---],
[---, ---, ---]]
'''
Вот объяснение, почему после добавления пары ключ-значение память становится такой:
Сначала мы вызываем Pythonhashфункция, расчетnameЭта строка находится вТекущее времяХэш-значение:
>>> hash('name')
1278649844881305901
В частности, я подчеркиваю здесь «текущую среду выполнения», потому что она поставляется с Python.hashфункция, и мы традиционно думаем о хэш-функции не то же самое. Это идет с PythonhashМожно только гарантировать, что значение, вычисленное функцией, останется неизменным при каждом выполнении, но когда вы закроете и снова откроете Python, его значение может измениться, как показано на следующем рисунке:
Предположим, что в некоторой среде выполненияhash('name')значение1278649844881305901.现在我们要把这个数对8取余数：
>>> 1278649844881305901 % 8
5
Остаток равен 5, затем поместите его в только что инициализированный двумерный массив, строку с индексом 5. так какnameиkingnameявляются двумя строками, поэтому базовый язык C будет использовать две строковые переменные для хранения этих двух значений, а затем получит соответствующие им указатели. Итак, в этой строке нашего двумерного массива с индексом 5 первое значение равноnameХэш-значение , второе значение равноnameАдрес памяти, где находится эта строка (указатель — адрес памяти), а третье значение —kingnameАдрес памяти, где находится эта строка.
Теперь давайте вставим два ключевых значения:
my_dict['age'] = 26
my_dict['salary'] = 999999
'''
此时的内存示意图
[[-4234469173262486640, 指向salary的指针, 指向999999的指针],
[1545085610920597121, 执行age的指针, 指向26的指针],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指针, 指向kingname的指针],
[---, ---, ---],
[---, ---, ---]]
'''
Так как же словарь считывает данные? Сначала предположим, что мы хотим прочитатьageсоответствующее значение.
В этот момент Python сначала вычисляет в текущей среде выполнения,ageКаково соответствующее значение хэша:
>>> hash('age')
1545085610920597121
Теперь этот хеш занимает остаток от 8:
>>> 1545085610920597121 % 8
1
Остальная часть 1, затем в двухмерном массиве строка с подплеску 1 - это необходимая пара клавиш. Напрямую возвращает значение в памяти, соответствующую третьему указателю в этой строке, котораяageсоответствующее значение26.
Когда вы хотите перебрать ключи словаря, нижний слой Python будет проходить по этому двумерному массиву.Если в текущей строке есть данные, он вернет значение в памяти, соответствующее указателю Key. Если в текущей строке нет данных, пропустите ее. Таким образом, он всегда будет перебирать каждую строку всего двузначного массива.
Каждая строка состоит из трех столбцов, и каждый столбец занимает 8 байтов памяти, поэтому каждая строка занимает 24 байта памяти.
Поскольку оставшаяся часть значения Hash может быть большой или маленькой, ключи словаря не сохраняются в порядке вставки.
Обратите внимание, что здесь я опустил два момента, которые не очень относятся к этой статье:
- OpenAddressed, когда два разных ключа, после хэша позже, 8 снова берут остаток, остаток может быть таким же. Приказ Python не перезаписывать существующие значения ранее будет использоваться
开放寻址Технология находит новое место для хранения этой новой пары ключ-значение.- Когда количество пар ключ-значение в словаре превышает 2/3 текущей длины массива, массив будет расширен, 8 строк станут 16 строками, а 16 строк станут 32 строками. После изменения длины исходная позиция остатка также изменится.В это время данные в исходной позиции необходимо переместить, что приведет к снижению эффективности вставки.
После Python 3.6 базовая структура данных словарей изменилась, и теперь, когда вы инициализируете пустой словарь, под капотом это выглядит так:
my_dict = {}
'''
此时的内存示意图
indices = [None, None, None, None, None, None, None, None]
entries = []
'''
Когда вы инициализируете словарь, только Python генерирует одномерный массив длины 8. Затем генерируется пустой двумерный массив.
Теперь добавим в словарь пару ключ-значение:
my_dict['name'] = 'kingname'
'''
此时的内存示意图
indices = [None, 0, None, None, None, None, None, None]
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针]]
'''
Почему память становится такой? Давайте рассмотрим это шаг за шагом:
В текущей операцииnameЭта строка имеет значение HASH-5954193068542476671, это значение принимает остаток от 8 и равно 1:
>>> hash('name')
-5954193068542476671
>>> hash('name') % 8
1
Итак, ставимindicesВ этом одномерном массиве позиция, в которой нижний индекс равен 1, изменяется на 0.
Что здесь означает 0? 0 - двузначный массивentriesиндекс чего-либо. в настоящее времяentriesВ нем есть только одна строка, что являются тремя данными пары ключ, которые мы только что добавили:nameЗначение хеша, указывает наnameуказатели и указатели наkinganmeуказатель. такindicesЗаполненное число 0 — это индекс строки данных пары ключ-значение, которую мы только что вставили в двузначный массив.
Хорошо, теперь давайте вставим еще две части данных:
my_dict['address'] = 'xxx'
my_dict['salary'] = 999999
'''
此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针],
[9043074951938101872, 指向address的指针，指向xxx的指针],
[7324055671294268046, 指向salary的指针, 指向999999的指针]
]
'''
А что, если я хочу прочитать данные? если бы я читалsalaryЗначение, затем сначала вычислитьsalaryХэш-значение и остаток от этого значения до 8:
>>> hash('salary')
7324055671294268046
>>> hash('salary') % 8
6
тогда я буду читатьindicesИндекс 6 для этого значения. Это значение равно 2.
Затем прочитайте данные в строке с нижним индексом 2 в записях, что является данными, соответствующими зарплате.
Новый способ, когда я хочу вставить новые данные, я всегда просто иду кentriesДобавьте данные после , чтобы можно было гарантировать порядок вставки. Когда мы хотим пройтись по ключам и значениям словаря, проходим напрямуюentriesТо есть каждая строка внутри — это полезные данные, возможности пропустить нет, а количество проходов уменьшено.
Старый способ, когда в двумерном массиве 8 строк, даже если корректных данных всего 3 строки, но они занимают место в памяти или 8 * 24 = 192 байта. Но используйте новые способы, если только три строки действительных данных, тоentriesВсего 3 строки, а занятое место 3 * 24 = 72 байта, иindicesПоскольку это всего лишь одномерный массив, он занимает всего 8 байт, поэтому всего он занимает 80 байт. Использование памяти составляет всего 41% от оригинала.
Ссылаться на:[Python-Dev] More compact dictionaries with faster iteration