Посмотреть все уроки курса
Выбрать другой урок из курса
Поиск по сайту
Теория урока

7.5. Внутреннее устройство и сортировка словаря в 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 на уровне интерпретатора и научились сортировать словари по ключу и значению.

<
×
>
Раздел «Знакомство с Python»
Урок 1.1. Первое знакомство с Python
Тест 1.2. Небольшой первый тест
Урок 1.3. Переменные и комментарии в Python
Тест 1.4. Тест по основным понятиям и работе с сайтом
Урок 2.1. Погружение в Python
Тест 2.2. Второй вводный тест по Python
Урок 2.3. Типы данных в Python
Урок 2.4. Форматирование строк в Python
Урок 2.5. Условная инструкция if-elif-else в Python
Урок 2.6. Преобразование и проверка типов в Python
Урок 2.7. Вызов методов цепочкой в Python
Урок 3.1. Первое знакомство с циклами в Python
Тест 3.2. Тест по циклам Python
Урок 4.1. Генерируем случайные числа на Python
Тест 4.2. Тест по модулю random Python
Урок 5.1. Структуры данных в Python
Тест 5.2. Тест по структурам Python
Урок 6.1. Списки в Python
Тест 6.2. Тест по спискам Python
Урок 6.3. Изменение списка на месте в Python
Урок 6.4. Дополнительно про списки в Python
Урок 6.5. Конкатенация и сортировка списков в Python
Тест 6.6. Заключительный тест по спискам в Python
Урок 7.1. Словари в Python
Тест 7.2. Тест по словарям Python
Урок 7.3. Словари и списки: еще глубже
Урок 7.4. Перебор элементов словаря в Python
Урок 7.5. Внутреннее устройство и сортировка словаря в Python
Вы здесь
Урок 7.6. Методы словарей и функция len() в Python
Тест 7.7. Заключительный тест по словарям
Урок 8.1. Множества в Python
Урок 8.2. Методы и особенности множеств в Python
Урок 8.3. Отношения между множествами и операции над ними
Тест 8.4. Тест по методам множеств в Python
Тест 8.5. Тест по операциям над множествами в Python
Урок 9.1. Кортежи в Python
Урок 9.2. Более подробно о кортежах в Python
Тест 9.3. Тест по кортежам в Python
Урок 10.1. Контроль хода выполнения программы в Python
Урок 10.2. Цикл while в Python
Урок 10.3. Операторы break, continue и pass в Python
Урок 10.4. Циклы for/else и while/else в Python
Урок 10.5. Обработка исключений (try/except) в Python
Тест 10.6. Тест по циклам и управляющим конструкциям
Тест 10.7. Тест по обработке исключений
Урок 10.8. Что дальше?