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

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

Похожие уроки и записи блога

Первое знакомство с PythonЗнакомство с Python
Обработка исключений (try/except) в PythonЗнакомство с Python
Работа с файлами в Python Знакомство с Python
Типы данных в PythonЗнакомство с Python
Основы функций в PythonЗнакомство с Python
Погружение в PythonЗнакомство с Python
Методы словарей и функция len() в PythonЗнакомство с Python
Методы и особенности множеств в PythonЗнакомство с Python
Свойство background для работы с фономЦвета и фон
<
×
>
Раздел «Знакомство с Python»
1. УРОК: Первое знакомство с Python
2. ТЕСТ: Небольшой первый тест по Python
3. УРОК: Переменные и комментарии в Python
4. ТЕСТ: Тест по основным понятиям и работе с сайтом
5. УРОК: Погружение в Python
6. ТЕСТ: Второй вводный тест по Python
7. УРОК: Типы данных в Python
8. УРОК: Форматирование строк в Python
9. УРОК: Условная инструкция if-elif-else в Python
10. УРОК: Преобразование и проверка типов в Python
11. УРОК: Вызов методов цепочкой в Python
12. УРОК: Первое знакомство с циклами в Python
13. ТЕСТ: Тест по циклам Python
14. УРОК: Генерируем случайные числа на Python
15. ТЕСТ: Тест по модулю random Python
16. УРОК: Структуры данных в Python
17. ТЕСТ: Тест по структурам Python
18. УРОК: Списки в Python
19. ТЕСТ: Тест по спискам Python
20. УРОК: Изменение списка на месте в Python
21. УРОК: Дополнительно про списки в Python
22. УРОК: Конкатенация и сортировка списков в Python
23. ТЕСТ: Заключительный тест по спискам в Python
24. УРОК: Словари в Python
25. ТЕСТ: Тест по словарям Python
26. УРОК: Словари и списки: еще глубже
27. УРОК: Перебор элементов словаря в Python
УРОК 28. Внутреннее устройство и сортировка словаря в Python
Вы здесь
29. УРОК: Методы словарей и функция len() в Python
30. ТЕСТ: Заключительный тест по словарям
31. УРОК: Множества в Python
32. УРОК: Методы и особенности множеств в Python
33. УРОК: Отношения между множествами и операции над ними
34. ТЕСТ: Тест по методам множеств в Python
35. ТЕСТ: Тест по операциям над множествами в Python
36. УРОК: Кортежи в Python
37. УРОК: Более подробно о кортежах в Python
38. ТЕСТ: Тест по кортежам в Python
39. УРОК: Контроль хода выполнения программы в Python
40. УРОК: Цикл while в Python
41. УРОК: Операторы break, continue и pass в Python
42. УРОК: Циклы for/else и while/else в Python
43. УРОК: Обработка исключений (try/except) в Python
44. ТЕСТ: Тест по циклам и управляющим конструкциям
45. ТЕСТ: Тест по обработке исключений
46. УРОК: Работа с файлами в Python
47. УРОК: Оператор with/as для работы с файлами в Python
48. ТЕСТ: Тест по работе с файлами в Python
49. УРОК: Итераторы в Python
50. УРОК: List/dict/set comprehensions (включения) в Python
51. ТЕСТ: Тест по включениям в Python
52. УРОК: Основы функций в Python
53. ТЕСТ: Тест по основам функций в Python
54. УРОК: Область видимости в Python
55. ТЕСТ: Тест по области видимости в Python
56. УРОК: Замыкания и оператор nonlocal в Python
57. ТЕСТ: Тест по замыканиям и nonlocal в Python
58. УРОК: Аргументы и параметры функций, операторы * и ** в Python
59. ТЕСТ: Тест по аргументам и параметрам функций в Python
60. ТЕСТ: Тест по операторам * и ** в Python
61. УРОК: Что дальше?
Впервые на сайте Codebra?

Извините за это всплывающее окно, меня они тоже раздражают.

Образовательный ресурс codebra.ru полностью посвящен программированию. Все курсы и уроки находятся на главной странице. Ради интереса можете посмотреть на содержимое курсов по Python, HTML и CSS, JavaScript, C++ и другие, размещенные на главной странице.

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

Удачи в обучении!

Закрыть окно