# Глава 15. Словари Рассмотрим тип `dict` (dictionary, словарь) для работы с отображенями ключ-значение. Важно, что `dict` незримо присутствует абсолютно в любом python-коде: он прочно вшит в низкоуровневое представление данных. Все объекты, будь то целые числа, функции или кортежи, имеют id, тип и другие атрибуты. А это не что иное, как пары ключ-значение внутри словаря! Неудивительно, что класс `dict` разрабатывался с упором на эффективность. ## Создание словарей Класс `dict` — это коллекция для хранения пар: уникальных ключей, к которым привязаны значения. Примеры таких пар: трек-номер посылки и адрес доставки, id пользователя и его телефон. Ключом словаря может выступать любой [хешируемый объект.](/courses/python/chapters/python_chapter_0140#block-hash) Сам словарь является изменяемой коллекцией с возможностью удаления и добавления элементов. Как и множество, словарь реализован на базе [хеш-таблицы.](https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0) Поэтому [алгоритмическая сложность](https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C) поиска, добавления и удаления элементов в `dict` оценивается как амортизированная константа O(1). Значением словаря, привязанным к ключу, может быть абсолютно любой объект: список, множество, `None`. Можно создавать структуры с большой вложенностью: словари, содержащие другие словари, содержащие списки. Инициализируется словарь `dict` двумя способами: через литерал `{}` и конструктор `dict()`. Мы уже [обсудили,](/courses/python/chapters/python_chapter_0140/#block-create-set) что посредством фигурных скобок инициализируются не только словари, но и множества. Элементы множества перечисляются в скобках через запятую. А при заведении словаря перечисляются пары `key: value`. ```python {.example_for_playground} # Ключ словаря - id пользователя. Значение - логин пользователя. users = {90278: "pasha", 136743: "slumbering.eoraptor"} print(type(users)) print(len(users)) ``` ``` <class 'dict'> 2 ``` В данном примере через литерал `{}` был создан словарь из двух элементов. А вот как выглядит вариант создания словаря с тем же содержимым через конструктор `dict()`: ```python users = dict([ (90278, "tanya"), (136743, "slumbering.eoraptor") ]) ``` Конструктор `dict()` ожидает аргумент, по которому можно итерироваться для формирования пар ключ-значение. В примере мы использовали список кортежей. С тем же успехом мы могли передать и список списков или кортеж кортежей. Иными словами, итерабельный объект, содержащий итерабельные объекты. Перечислите через пробел ключи словаря `d` в любом порядке. В случае ошибки напишите `error`. {.task_text} ```python {.example_for_playground} lst = ["or", "to", "an"] d = dict(lst) ``` ```consoleoutput {.task_source #python_chapter_0150_task_0003} ``` Конструктор `dict()` итерируется по списку `lst` для составления пар: ключей и значений нового словаря. По строкам можно итерироваться точно так же, как и по спискам. Поэтому первая буква строки превращается в ключ, а вторая в значение словаря. В итоге `d` содержит три записи: `{'o': 'r', 't': 'o', 'a': 'n'}`. Ключами являются буквы `o`, `t`, `a`. {.task_hint} ```python {.task_answer} ota ``` Если ключи словаря — строки, то возможны два варианта инициализации. Первый — интуитивный: обернуть строки в кавычки. ```python {.example_for_playground} # Ключ словаря - код товара. Значение - количество единиц товара в магазине. products = dict([ ("T3234FX", 12), ("T048Y11", 0), ("QW23302", 9) ]) print(products) ``` ``` {'T3234FX': 12, 'T048Y11': 0, 'QW23302': 9} ``` Второй способ — избавиться от кавычек и работать с парами ключ-значение как с [именованными аргументами](/courses/python/chapters/python_chapter_0060#block-pos-named-args) функции `dict()`: ```python {.example_for_playground} products = dict( T3234FX=12, T048Y11=0, QW23302=9 ) print(products) ``` ``` {'T3234FX': 12, 'T048Y11': 0, 'QW23302': 9} ``` Этот способ сработает, только если ключ-строка удовлетворяет всем требованиям к именованию переменной в питоне (например, не начинается с цифры, не содержит тире и спецсимволы). ## Операции над словарями Синтаксис квадратных скобок `[]`, в которых указывается ключ, используется для: - поиска значения в словаре по ключу, - записи и перезаписи значения по ключу. В этом примере мы заводим словарь `cities`, в котором хранятся названия городов и их координаты (широта и долгота). Заполняем словарь данными о двух городах, а затем извлекаем значение по ключу. Встроенная функция `len()` нужна, чтобы определить размер словаря (количество пар ключ-значение). ```python {.example_for_playground} # Заводим пустой словарь cities = {} # Добавляем в словарь значения cities["Tokyo"] = (35.6817, 139.7539) cities["Cairo"] = (30.0505, 31.2464) # Ищем значения по ключу cairo_coordinates = cities["Cairo"] print(f"Cairo is located here: {cairo_coordinates}") n = len(cities) print(f"We have {n} cities") ``` ``` Cairo is located here: (30.0505, 31.2464) We have 2 cities ``` Оператор `in` используется для проверки, содержится ли в словаре интересующий ключ. ```python {.example_for_playground} cities = {"Tokyo": (35.6817, 139.7539), "Cairo": (30.0505, 31.2464)} print("Tokyo" in cities) print("Palermo" in cities) print(cities["Tokyo"]) print(cities["Palermo"]) ``` ``` True False (35.6817, 139.7539) Traceback (most recent call last): File "/home/ail/test.py", line 7, in <module> print(cities["Palermo"]) ~~~~~~^^^^^^^^^^^ KeyError: 'Palermo' ``` Для существующего ключа `"Tokyo"` оператор `in` вернул `True`, и посредством `[]` было получено его значение. Для не существующего ключа `"Palermo"` `in` вернул `False`, а обращение по этому ключу привело к исключению `KeyError`. Подчеркнем, что квадратные скобки позволяют не только прочитать значение, но и модифицировать существующее или сохранить новое: ```python {.example_for_playground} # Заводим словрь, содержащий авторов и их книги authors = {"Luciano Ramalho": "Fluent Python"} # Изменяем название книги authors["Luciano Ramalho"] = "Fluent Python. Clear, concise, and Effective programming" # Добавляем нового автора authors["Jason Brownlee"] = "Python Asyncio Jump-Start" print(authors) ``` ``` {'Luciano Ramalho': 'Fluent Python. Clear, concise, and Effective programming', 'Jason Brownlee': 'Python Asyncio Jump-Start'} ``` В этом примере мы изменили значение по ключу `"Luciano Ramalho"` и добавили новое по ключу `"Jason Brownlee"`. Что выведет этот код? В случае ошибки напишите `error`. {.task_text} ```python {.example_for_playground} f = lambda x: x % 10 d = dict() for val in [15, 20, 30, 31]: k = f(val) d[k] = val print(len(d)) ``` ```consoleoutput {.task_source #python_chapter_0150_task_0005} ``` Мы объявили лямбда-функцию `f`, которая принимает число `x` и с помощью оператора `%` возвращает остаток от деления `x` на 10. Затем в цикле мы применяем эту лямбду к числам. Отаток от деления этих чисел на 10 становится ключом в словаре `d`. Мы получили остаток от деления 15 на 10. Это 5. По ключу 5 записали значение 15. Остаток от деления чисел 20 и 30 совпадает и равен нулю. Поэтому вначале по ключу 0 мы записали значение 20, а затем перезаписали его значением 30. Остаток от деления 31 на 10 равен 1. Таким образом, в словаре `d` накопилось 3 элемента. {.task_hint} ```python {.task_answer} 3 ``` Как считаете, что не так с этим кодом? ```python {.example_for_playground} d = {3: "triangle", 4: "square", 6: "hexagon"} x = d[3:4] ``` На строке 2 произведена попытка обращения к элементам словаря через [срез,](/courses/python/chapters/python_chapter_0100##block-slices) а не по ключу. Так как для типов `dict` и `set` операция получения среза бессмысленна, генерируется исключение: ``` Traceback (most recent call last): File "example.py", line 2, in <module> x = d[3:4] ~^^^^^ TypeError: unhashable type: 'slice' ``` Напишите функцию `to_dict(items)`, которая в качестве аргумента принимает некоторый итерабельный объект (например, список или кортеж). Функция должна создать на базе него словарь и вернуть его. Ключ словаря — элемент `items`, а значение — индекс этого элемента в последовательности `items` (индексация с нуля). {.task_text} Если элемент встречается в последовательности несколько раз, нужно сохранить индекс **последнего** вхождения. {.task_text} Если в `items` попадутся не хешируемые объекты, в словарь их добавлять не надо. {.task_text} Например, для входного списка `["first", 2, "third", {4, 44}, "first"]` функция должна вернуть словарь `{'first': 4, 2: 1, 'third': 2}`. {.task_text} ```python {.task_source #python_chapter_0150_task_0010} import typing def to_dict(items): # Your code here ``` Создайте пустой словарь. Проитерируйтесь по `items` и заполните словарь хэшируемыми элементами `items` и их индексами. Для проверки, является ли объект `item` хешируемым, используйте функцию `isinstance(item, typing.Hashable)`. Она объявлена в модуле `typing`. {.task_hint} ```python {.task_answer} import typing def to_dict(items): d = {} for i, item in enumerate(items): if isinstance(item, typing.Hashable): d[item] = i return d ``` Удалить из словаря значение можно с помощью оператора `del`: ```python {.example_for_playground} d = {3: "triangle", 4: "square", 6: "hexagon"} del d[4] print(d) del d[4] ``` ``` {3: 'triangle', 6: 'hexagon'} Traceback (most recent call last): File "/home/ail/test.py", line 6, in <module> del d[4] ~^^^ KeyError: 4 ``` Обратите внимание: при попытке удаления элемента по уже не существующему ключу оператор `del` генерирует исключение `KeyError`. Выведите на экран значение 1024 из вложенного объекта `obj`.{.task_text} ```python {.task_source #python_chapter_0150_task_0020} obj = [ "sort", 45, (16, 17), { 1: 3, "k2": None, "k6": { "val": 1024 } } ] ``` Выражение для доступа к нужному значению: `obj[3]["k6"]["val"]` {.task_hint} ```python {.task_answer} obj = [ "sort", 45, (16, 17), { 1: 3, "k2": None, "k6": { "val": 1024 } } ] print(obj[3]["k6"]["val"]) ``` Обойти в цикле словарь можно двумя способами. Первый: перебрать ключи и по ним получить значения: ```python for k in d: print(k, d[k]) ``` Второй способ: вызвать метод `items()` для итерации по парам ключ-значение: ```python for k, v in d.items(): print(k, v) ``` Подытожим основные действия над словарями: {#block-basic-ops} - `len(d)` — определение размера словаря. - `k in d`, `k not in d` — проверка, содержится или нет в словаре нужный ключ. - `d[k]` — обращение к значению в словаре по ключу. Используется для получения, изменения или добавления значения. - `del d[k]` — удаление пары ключ-значение из словаря. - `d.items()` — метод для итерации по парам ключ-значение. Создайте функцию `calc_visits(users)`, аргумент которой — список id пользователей, посетивших страницу некоего сайта. Причем id могут повторяться. Необходимо посчитать количество посещений для каждого из пользователей: функция должна вернуть словарь, ключ в котором — это id пользователя, а значение — количество посещений. {.task_text} Например, список [6, 6, 4, 6] трактуется следующим образом: пользователь с id 6 посетил страницу 3 раза, пользователь с id 4 посетил страницу 1 раз.{.task_text} ```python {.task_source #python_chapter_0150_task_0030} ``` Для проверки ключа на вхождение в словарь используйте оператор `in`, для изменения существующего значения по ключу — `[]`. {.task_hint} ```python {.task_answer} def calc_visits(users): visits = {} for user in users: if user not in visits: visits[user] = 0 visits[user] += 1 return visits ``` Но на этом популярные операции над типом `dict` не заканчиваются. Также широко применимы методы: {#block-methods} - `d.copy()` — метод возвращает копию словаря. Например, `d2 = d1.copy()` означает, что изменения, вносимые в словарь `d2`, никак не повлияют на оригинальный словарь `d1`. Если же использовать обычное присваивание `d2 = d1`, то переменная `d2` будет смотреть на тот же самый объект в памяти, что `d1`. И все изменения `d2` отразятся на `d1`! - `d.clear()` — метод для удаления из словаря всех элементов. - `d.pop(k, default_val)` — метод для удаления и возврата значения по ключу. Если аргумент `default_val` не задан, а ключ отсутствует в словаре, генерирует исключение `KeyError`. - `d.get(k, default_val)` — метод для получения значения по ключу. В отличие от `d[k]`, если ключ не найден, не генерирует исключение, а возвращает `default_val`. Этот аргумент опционален и по умолчанию равен `None`: `d.get(k)` для несуществующего ключа вернет `None`. - `d.update(items)` — метод для обновления содержимого словаря объектами `items`. `items` может быть другим словарем, итерабельным объектом с парами ключ-значение или перечислением именованных аргументов. - `d.setdefault(k, default_val)` — получить значение `k`, если этот ключ содержится в словаре. Если не содержится, добавить и вернуть значение `default_val` по этому ключу. `default_val` — опциональный аргумент, по умолчанию `None`. Удалите из словаря значение 5.5. Используйте для этого один из **методов** `dict`, а не оператор `del`.{.task_text} ```python {.task_source #python_chapter_0150_task_0040} temperatures = {"min": 5.5, "max": 28.0, "avg": 14.1} ``` Воспользуйтесь методом `pop()`. {.task_hint} ```python {.task_answer} temperatures = {"min": 5.5, "max": 28.0, "avg": 14.1} temperatures.pop("min") ``` Используем метод `get()` для создания частотного словаря. Частотный словарь — это набор слов в тексте вместе с информацией об их частотности. ```python {.example_for_playground} def lexicon(text): # Берем текст и строим по нему частотный словарь d = {} for word in text.lower().split(): d[word] = d.get(word, 0) + 1 return d lex = lexicon("A hash table uses a hash function to compute an index") for k, v in lex.items(): print(f"'{k}' occurs {v} times in text") print(f"\nThere are {len(lex)} unique words in text") # Удаляем артикли del lex["a"] del lex["an"] print(f"There are {len(lex)} unique words in text excluding articles") ``` ``` 'a' occurs 2 times in text 'hash' occurs 2 times in text 'table' occurs 1 times in text 'uses' occurs 1 times in text 'function' occurs 1 times in text 'to' occurs 1 times in text 'compute' occurs 1 times in text 'an' occurs 1 times in text 'index' occurs 1 times in text There are 9 unique words in text There are 7 unique words in text excluding articles ``` Создайте функцию `merge_max(d1, d2)`, принимающую два словаря, ключи и значения в которых — целые числа. Функция должна сформировать из них и вернуть новый словарь. Причем если ключ присутствует в обоих словарях, в новый словарь требуется поместить по этому ключу максимальное значение. {.task_text} ```python {.task_source #python_chapter_0150_task_0050} ``` Для определения максимального из двух значений воспользуйтесь встроенной функцией `max(a, b)`. {.task_hint} ```python {.task_answer} def merge_max(d1, d2): merged = {} for k, v in d1.items(): merged[k] = v for k, v in d2.items(): if k in merged: merged[k] = max(merged[k], v) else: merged[k] = v return merged ``` ## Является ли dict упорядоченной коллекцией Начиная с версии питона 3.7 ключи в `dict` гарантированно отсортированы в порядке добавления. До версии 3.7 словарь не был отсортированной коллекцией, и для работы с упорядоченным словарем использовался класс `OrderedDict` из модуля `collections`. Потерял ли `OrderedDict` с тех пор свою актуальность? Не совсем: в нем доступен набор методов, которых нет во встроенном типе `dict`. Подробнее мы рассмотрим `OrderedDict` и другие классы из `collections` в следующих главах. Несмотря на то, что словари в современном питоне — это упорядоченные коллекции, при сравнении двух словарей оператор `==` вернет `True` вне зависимости от последовательности пар ключ-значение: главное, чтобы они совпадали: ```python {.example_for_playground} d1 = {1: 1, 2: 2, 3: 3} d2 = {2: 2, 3: 3, 1: 1} print(d1 == d2) ``` ``` True ``` ## Резюмируем - Тип `dict` (словарь) — это гетерогенная коллекция пар: уникальных ключей, к которым привязаны значения. - `dict` создается с помощью конструктора `dict()` либо литерала `{}`. - Начиная с версии питона 3.7 ключи в `dict` упорядочены в порядке добавления. - Для того чтобы объект мог выступать ключом в `dict`, он должен быть хешируемым. - Тип `dict` реализован на базе хеш-таблицы. Поэтому алгоритмическая сложность поиска, добавления и удаления элементов у него амортизированное O(1).