0 знаков
25. Внутреннее устройство и сортировка словаря в Python
Кратко- Сортировка словаря в Python имеет свои особенности.
- Начиная с версии Python 3.7, словари стали упорядоченными.
- Внутреннее устройство словарей в Python реализовано с помощью двух массивов.
- Поиск элемента в словаре осуществляется через хэш-функцию и линейный поиск.
- Коллизия при добавлении элемента может привести к потере выигрыша от использования словаря.
- В Python каждый элемент словаря содержит ссылку на объект и ключ.
- Ключ словаря должен быть неизменяемым объектом.
- Минимальный размер словаря в Python равен восьми.
- В версии Python 3.6 добавили второй массив для реализации словаря.
Введение
Ранее мы научились сортировать списки, а в предыдущем уроке перебирать элементы словаря. Сортировка словаря имеет свои особенности, с которыми будем разбираться в этом уроке. Так же глубже разберемся с тем, что такое словарь и как он реализуется в 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.
Предположим, у нас есть массив, в котором хранятся объекты одного размера. Тогда зная индекс и размер одного объекта, мы легко можем получить доступ к нужному объекту.
Для доступа необходимо авторизоваться на сайте Codebra.
Но что делать, если индексом является объект нецелочисленного типа, например, строка? В таком случае нам придется просматривать каждый элемент массива, чтобы найти нужный, другими словами, произвести линейный поиск.
Линейный поиск может быть значительно ускорен, для чего потребуется ограничить область поиска. Это достигается путем взятия остатка от деления хэша. Хэш-функция - это функция, принимающая данные любой длины, преобразующая их по определенному алгоритму и возвращающая строку фиксированной длины. Поле, по которому будет осуществляться дальнейший поиск, называется ключом.
Для доступа необходимо авторизоваться на сайте Codebra.
Существует вероятность, что хэши совпадут. В таком случае объект будет размещен под следующим индексом, если он свободен. Если следующий индекс занят, то будет проверен последующий и так до тех пор, пока не найдется свободный.
Для доступа необходимо авторизоваться на сайте Codebra.
При поиске необходимого элемента под одним хэшем окажется несколько элементов, из которых будет найден нужный при помощи линейного поиска. То есть, чем больше элементов будут иметь одинаковые хэши, тем меньше выигрыш от использования словаря.
После заполнения массива на две трети, создаётся новый массив размером в два раза больше предыдущего и в него переносятся элементы по одному.
При удалении элемента, он помечается 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 можно как по ключу, так и по значению. В предыдущем уроке вы познакомились с методом словаря items()
, который возвращает кортеж из двух элементов. Зная это, можем отсортировать словарь по ключу следующим образом:
numbers = {1: 'One', 3: 'Three', 2: 'Two'}
numbers = sorted(numbers.items())
dict(numbers) # => {1: 'One', 2: 'Two', 3: 'Three'}
Помните, что функция sorted()
не изменяет объект, переданный ей в параметре, а возвращает новый. Об этом мы говорили в уроке о конкатенации и сортировке списков в Python. Так вот, мы отсортировали словарь, который был сначала преобразован в список кортежей:
[(1, 'One'), (3, 'Three'), (2, 'Two')]
ПримечаниеЯ не упоминал функцию
dict()
в уроке про преобразование типов, настало время это исправить. С помощью ее можно собрать список кортежей из двух элементов в словарь.
Потом обратно собрали в словарь:
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
.
import operator
В уроке про сортировку списков параметр 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 на уровне интерпретатора и научились сортировать словари по ключу и значению.
В следующем уроке познакомимся с другими методами словарей и функцией len()
.
Тест
Похожие уроки Codebra
Подписывайся на наш Telegram-канал!
Новости, полезный материал,
программирование и ИБ
Подписывайся на наш Telegram-канал!
Новости, полезный материал,
программирование и ИБ