Искать
Вы превысили запрос на
0 знаков

25. Внутреннее устройство и сортировка словаря в Python

Не пройден
0
0

Кратко

- Сортировка словаря в Python имеет свои особенности.

- Начиная с версии Python 3.7, словари стали упорядоченными.

- Внутреннее устройство словарей в Python реализовано с помощью двух массивов.

- Поиск элемента в словаре осуществляется через хэш-функцию и линейный поиск.

- Коллизия при добавлении элемента может привести к потере выигрыша от использования словаря.

- В Python каждый элемент словаря содержит ссылку на объект и ключ.

- Ключ словаря должен быть неизменяемым объектом.

- Минимальный размер словаря в Python равен восьми.

- В версии Python 3.6 добавили второй массив для реализации словаря.

Введение

Ранее мы научились сортировать списки, а в предыдущем уроке перебирать элементы словаря. Сортировка словаря имеет свои особенности, с которыми будем разбираться в этом уроке. Так же глубже разберемся с тем, что такое словарь и как он реализуется в Python (точнее, в интерпретаторе CPython).

Начиная с версии Python 3.7. словари стали упорядоченными. В ранних версиях Python при запуске программы, порядок ключей словаря мог меняться. То есть вы инициализировали следующий словарь:

Пример (python)
numbers = {1: 'One', 2: 'Two', 3: 'Three'} 

Вывод словаря number мог быть как таким:

Пример (python)
{3: 'Three', 1: 'One', 2: 'Two'} 

Так и таким:

Пример (python)
{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. словарь был реализован одним массивом:

Пример (python)
numbers = {1: 'One', 2: 'Two', 3: 'Three'}

[
    [2104099250931030335, 2, 'Two'],
    ['', '', ''],
    ['', '', ''],
    ['', '', ''],
    [-8441781841123548813, 1, 'One'],
    ['', '', ''],
    ['', '', ''],
    [-3252229085628509895, 3, 'Three']
] 

Как видите, наш словарь состоит из трех элементов, поэтому был создан массив из восьми элементов. Каждый элемент хранит хэш, ключ и значение. После версии Python 3.6. был добавлен второй массив.

Пример (python)
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(), который возвращает кортеж из двух элементов. Зная это, можем отсортировать словарь по ключу следующим образом:

Пример (python)
numbers = {1: 'One', 3: 'Three', 2: 'Two'}
numbers = sorted(numbers.items())
dict(numbers) # => {1: 'One', 2: 'Two', 3: 'Three'} 

Помните, что функция sorted() не изменяет объект, переданный ей в параметре, а возвращает новый. Об этом мы говорили в уроке о конкатенации и сортировке списков в Python. Так вот, мы отсортировали словарь, который был сначала преобразован в список кортежей:

Пример (python)
[(1, 'One'), (3, 'Three'), (2, 'Two')] 

Примечание

Я не упоминал функцию dict() в уроке про преобразование типов, настало время это исправить. С помощью ее можно собрать список кортежей из двух элементов в словарь.

Потом обратно собрали в словарь:

Пример (python)
dict(numbers) 

Есть другой способ сортировать словарь по ключам. По сути, это сводится к сортировке списка и использованию встроенного метода sort() для них. Для этого получим список ключей словаря при помощи метода keys() и выведем словарь согласно отсортированным ключам:

Пример (python)
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.

Пример (python)
import operator 

В уроке про сортировку списков параметр key мы использовали, чтобы сортировать строки независимо от регистра. Теперь в параметр key будем передавать второй элемент кортежа, который является значением элемента в словаре.

Пример (python)
# 0 1 0 1 0 1 0 1  
[(1, 'One'), (2, 'Two'), (3, 'Three'), (4, 'Four')] 

Для этого будем использовать itemgetter(), который возвращает n-ый элемент в итерируемом объекте. Полный пример сортировки словаря по значению представлен ниже.

Пример (python)
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(), чтобы лучше понять, что означает передаваемый параметр.

Пример (python)
sorted([(1, 'One', 4), (2, 'Two', 3)], key=operator.itemgetter(2)) # => [(2, 'Two', 3), (1, 'One', 4)] 

В этом уроке мы разобрались, как реализован словарь в Python на уровне интерпретатора и научились сортировать словари по ключу и значению.

В следующем уроке познакомимся с другими методами словарей и функцией len().

Тест

Две секундочки...

Похожие уроки Codebra

@codebra_official
Подписывайся на наш Telegram-канал!
Новости, полезный материал,
программирование и ИБ
Первое знакомство с PythonЗнакомство с Python
Поиск хостов с помощью NmapРазведка и сканирование
Итоги раздела «Структуры данных в Python»Знакомство с Python
Поиск сетевых уязвимостей с помощью Metasploit Framework (MSF)Разведка и сканирование
Обработка исключений (try/except) в PythonЗнакомство с Python
Пользовательские функции в PHPКурс по PHP
Типы данных в PythonЗнакомство с Python
Поиск общих папок с помощью CrackMapExec, SMBMap, smbclientРазведка и сканирование
Обнаружение сетевых служб с помощью NmapРазведка и сканирование
Впервые на сайте Codebra?

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

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

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

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

Закрыть окно