28. Внутреннее устройство и сортировка словаря в Python
Оглавление урока
Введение
В уроке 6.5. мы научились сортировать списки. Сортировка словаря имеет свои особенности, с которыми будем разбираться в этом уроке. Так же глубже разберемся с тем, что такое словарь и как он реализуется в Python (точнее, в интерпретаторе CPython).
Начиная с версии Python 3.7. словари стали упорядоченными. В ранних версиях Python при запуске программы, порядок ключей словаря мог меняться. То есть вы инициализировали следующий словарь:
numbers = {1: 'One', 2: 'Two', 3: 'Three'}
Вывод словаря number мог быть как таким:
{3: 'Three', 1: 'One', 2: 'Two'}
Так и таким:
{3: 'Three', 2: 'Two', 1: 'One'}
Чтобы это понять, погрузимся во внутреннее устройство словарей в Python.
Внутреннее устройство словарей в Python
Этот материал представлен для ознакомления. Он может показаться сложным, поэтому можете его пропустить и вернуться к нему позднее. Если вам интересно, почему после версии Python 3.6. словарь реализован с помощью двух массивов и как это повлияло на сохранение порядка вставки элементов, то продолжайте чтение или перейдите сразу к сортировке словарей в Python.
Предположим, у нас есть массив, в котором хранятся объекты одного размера. Тогда зная индекс и размер одного объекта, мы легко можем получить доступ к нужному объекту.
Но что делать, если индексом является объект нецелочисленного типа, например, строка? В таком случае нам придется просматривать каждый элемент массива, чтобы найти нужный, другими словами, произвести линейный поиск.
Линейный поиск может быть значительно ускорен, для чего потребуется ограничить область поиска. Это достигается путем взятия остатка от деления хэша. Хэш-функция - это функция, принимающая данные любой длины, преобразующая их по определенному алгоритму и возвращающая строку фиксированной длины. Поле, по которому будет осуществляться дальнейший поиск, называется ключом.
Существует вероятность, что кэши совпадут. В таком случае объект будет размещен под следующим индексом, если он свободен. Если следующий индекс занят, то будет проверен последующий и так до тех пор, пока не найдется свободный.
При поиске необходимого элемента под одним хэшем окажется несколько элементов, из которых будет найден нужный при помощи линейного поиска. То есть, чем больше элементов будут иметь одинаковые хэши, тем меньше выигрыш от использования словаря.
После заполнения массива на две трети, создаётся новый массив размером в два раза больше предыдущего и в него переносятся элементы по одному.
При удалении элемента, он помечается DKIX_DUMMY, чтобы не было путаницы: этот элемент был удален или это пустая ячейка.
В Python каждый элемент словаря содержит ссылку на хранимый объект и ключ. Ключ необходимо хранить для разрешения коллизий, которые возникают при совпадении хэша у элементов. Итак, а что произойдет, если ключ словаря был изменён? Ничего, потому что ключ словаря изменить нельзя, так как ключом может быть только неизменяемый объект.
В Python минимальный размер словаря равен восьми. Исходя из вышесказанного, первое расширение словаря будет осуществлено при добавлении 6 элемента. Таким образом, в массиве всегда много пустых ячеек. Чтобы это исправить, в версии Python 3.6. добавили второй массив для реализации словаря.
До версии Python 3.6. словарь был реализован одним массивом:
numbers = {1: 'One', 2: 'Two', 3: 'Three'}
[
[2104099250931030335, 2, 'Two'],
['', '', ''],
['', '', ''],
['', '', ''],
[-8441781841123548813, 1, 'One'],
['', '', ''],
['', '', ''],
[-3252229085628509895, 3, 'Three']
]
Как видите, наш словарь состоит из трех элементов, поэтому был создан массив из восьми элементов. Каждый элемент хранит хэш, ключ и значение. После версии Python 3.6. был добавлен второй массив.
numbers = {1: 'One', 2: 'Two', 3: 'Three'}
# индексы
[1, None, None, None, 0, None, None, 2]
# записи
[
[-8441781841123548813, 1, 'One'],
[2104099250931030335, 2, 'Two'],
[-3252229085628509895, 3, 'Three']
]
В первом массиве хранятся только индексы соответствующих записей, а во втором сами записи. Таким образом, на хранение двух массивов стало уходить меньше памяти, а порядок элементов стал неизменным.
Сортировка словаря в Python
Сортировать словари в Python можно как по ключу, так и по значению. В уроке 7.4. вы познакомились с методом словаря items(), который возвращает кортеж из двух элементов. Зная это, можем отсортировать словарь по ключу следующим образом:
numbers = {1: 'One', 3: 'Three', 2: 'Two'}
numbers = sorted(numbers.items())
dict(numbers) # => {1: 'One', 2: 'Two', 3: 'Three'}
Помните, что функция sorted() не изменяет объект, переданный ей в параметре, а возвращает новый. Об этом мы говорили в уроке 6.5. Так вот, мы отсортировали словарь, который был сначала преобразован в список кортежей:
[(1, 'One'), (3, 'Three'), (2, 'Two')]
Потом обратно собрали в словарь:
dict(numbers)
Есть другой способ сортировать словарь по ключам. По сути, это сводится к сортировке списка и использованию встроенного метода sort() для них. Для этого получим список ключей словаря при помощи метода keys() и выведем словарь согласно отсортированным ключам:
numbers = {1: 'One', 2: 'Two', 4: 'Four', 3: 'Three'}
list_keys = list(numbers.keys())
list_keys.sort()
for i in list_keys:
print(i, ':', numbers[i])
Сортировка словаря в Python по значению немного сложнее. Осложняет еще и то, что мы не знакомились с лямбда (lambda) выражениями. Поэтому будем использовать встроенный модуль operator, который необходимо подключить при помощи ключевого слова import.
В уроке 6.5. параметр key мы использовали, чтобы сортировать строки независимо от регистра. Теперь в параметр key будем передавать второй элемент кортежа, который является значением элемента в словаре.
# 0 1 0 1 0 1 0 1
[(1, 'One'), (2, 'Two'), (3, 'Three'), (4, 'Four')]
Для этого будем использовать itemgetter(), который возвращает n-ый элемент в итерируемом объекте. Полный пример сортировки словаря по значению представлен ниже.
import operator
numbers = {1: 'One', 2: 'Two', 3: 'Three', 4: 'Four'}
numbers = sorted(numbers.items(), key=operator.itemgetter(1))
dict(numbers) # => {4: 'Four', 1: 'One', 3: 'Three', 2: 'Two'}
Для примера, отсортируем список кортежей из трех элементов при помощи itemgetter(), чтобы лучше понять, что означает передаваемый параметр.
sorted([(1, 'One', 4), (2, 'Two', 3)], key=operator.itemgetter(2)) # => [(2, 'Two', 3), (1, 'One', 4)]
В этом уроке мы разобрались, как реализован словарь в Python на уровне интерпретатора и научились сортировать словари по ключу и значению.