Словари и подсчёт частот
Словарь хранит пары «ключ — значение» и по ключу сразу находит значение, поэтому им считают, сколько раз встречается каждый символ, слово или номер. Частотный словарь пополняют строкой d[x] = d.get(x, 0) + 1, а самый частый ключ находят через max с key. Так же по ключу накапливают суммы, например объём данных каждого клиента в задании 26.
Как считать частоты словарём
Словарь — набор пар «ключ — значение», в котором ключи не повторяются. В Python пустой словарь — {}.
d[k] = vзаписывает значение по ключу,d[k]читает его,k in dпроверяет, есть ли ключ.- Частота:
d[x] = d.get(x, 0) + 1.d.get(x, 0)даёт 0 для нового ключа. - Сумма по ключу:
d[k] = d.get(k, 0) + v. - Самый частый ключ:
max(d, key=d.get). Ключи по алфавиту:sorted(d). - Ключ — число, строка или кортеж. Список ключом быть не может.
Словарь: ключи и значения
Словарь ставит в соответствие каждому ключу одно значение: d = {'A': 3, 'B': 5} хранит пары A — 3 и B — 5. Запись d['C'] = 1 добавляет новую пару, а для существующего ключа заменяет значение. Чтение d['D'] по ключу, которого нет, останавливает программу с ошибкой KeyError. Поэтому для неизвестного ключа используют d.get('D', 0): метод возвращает второй аргумент, если ключа нет.
len(d) — число пар. Цикл for k in d перебирает ключи, for k, v in d.items() — ключи вместе со значениями.
Пример
d = {'A': 3, 'B': 5}, затем d['C'] = 1 и d['A'] += 2. Что напечатает print(d['A'], len(d), 'B' in d, d.get('D', 0))?
- 1.
d['C'] = 1добавляет третью пару,d['A'] += 2меняет значение A на . - 2.В словаре три пары, ключ B в нём есть.
- 3.Ключа D нет,
d.get('D', 0)возвращает 0.
Ответ: 5 3 True 0
Хэш-таблица: почему поиск по ключу быстрый
Словарь Python устроен как хэш-таблица. Хэш-функция превращает ключ в число — хэш, а по хэшу вычисляется номер ячейки внутреннего массива, где лежит значение. Чтобы найти значение, не нужно просматривать все пары: достаточно вычислить хэш ключа и заглянуть в одну ячейку. Поэтому поиск, добавление и изменение по ключу занимают в среднем одно и то же время при любом размере словаря. Поиск в списке, наоборот, просматривает элементы по очереди.
Хэш ключа не должен меняться, иначе значение не найдётся. Поэтому ключом может быть только неизменяемый объект: число, строка, кортеж. Список изменяемый, и ключом он быть не может. Если ключ состоит из двух чисел, например координат клетки, берут кортеж (x, y).
Пример
Сохраните в словаре слово «клетка» по ключу из двух чисел 2 и 3 и прочитайте его.
- 1.Кортеж
(2, 3)неизменяемый, его можно сделать ключом. - 2.Программа печатает «клетка».
- 3.Строка
d[[2, 3]] = 'клетка'со списком вместо кортежа остановила бы программу с ошибкойTypeError: unhashable type: 'list'.
Ответ: клетка
Частотный словарь
Частотный словарь хранит для каждого значения, сколько раз оно встретилось. Перебирайте данные и для каждого значения x выполняйте d[x] = d.get(x, 0) + 1: новый ключ получает 1, старый увеличивается на 1. Один проход по данным даёт частоты всех значений сразу.
Ключ с наибольшей частотой находит max(d, key=d.get): функция перебирает ключи и сравнивает их значения. Так решают задания 24, в которых нужен символ, который чаще всего стоит после заданной буквы. Обработка строк — в теме символьные строки.
Пример
Строка XABACABADAB. Какой символ чаще всего стоит сразу после буквы A и сколько раз?
- 1.Буква A стоит на местах 1, 3, 5, 7, 9 (счёт с нуля). После неё идут B, C, B, D, B.
- 2.Словарь частот: B — 3, C — 1, D — 1.
- 3.
max(d, key=d.get)даёт B.
Ответ: B, 3 раза
Алфавитно-частотный словарь текста
Алфавитно-частотный словарь текста — список всех его слов в алфавитном порядке, и при каждом слове — сколько раз оно встретилось. Текст делят на слова методом split(), частоты считают частотным словарём, а ключи упорядочивает sorted(d).
Если слова нужны по убыванию частоты, а при равной частоте по алфавиту, пишут sorted(d, key=lambda w: (-d[w], w)): минус меняет порядок частот на убывающий. Ключ сортировки разобран в теме сортировка по ключу.
Пример
Постройте алфавитно-частотный словарь текста «кот ест мясо кот спит кот ест».
- 1.Частоты: кот — 3, ест — 2, мясо — 1, спит — 1.
- 2.По алфавиту: ест, кот, мясо, спит.
Ответ: ест 2, кот 3, мясо 1, спит 1
Сумма по ключу
Словарь накапливает не только количество, но и сумму. Если в каждой записи есть ключ и число (номер клиента и объём данных, артикул и цена), пишут d[k] = d.get(k, 0) + v. После прохода по записям в d[k] лежит сумма чисел ключа k. Так в задании 26 находят клиента, который передал больше всего данных.
Пример
Журнал сервера: клиент 101 передал 20 Кбайт, 202 — 110, 101 — 90, 303 — 62, 101 — 48. Какой клиент передал больше всего данных и сколько?
- 1.Суммы по клиентам: 101 — , 202 — 110, 303 — 62.
- 2.
max(total, key=total.get)даёт 101.
Ответ: клиент 101, 158 Кбайт
Несколько словарей и выбор по нескольким правилам
Если о каждом ключе нужно знать несколько чисел, заведите по словарю на каждое: sold[k] — сколько продано, left[k] — сколько осталось, price[k] — цена. Все словари пополняются за один проход по записям.
Выбор по нескольким правилам («больше всего продано, при равенстве — дороже, при равенстве — меньше остаток») записывают кортежем в key: max(keys, key=lambda k: (sold[k], price[k], -left.get(k, 0))). Кортежи сравниваются по первому числу, при равенстве — по второму и так далее. Минус превращает «меньше» в «больше».
Пример задания
Открытый банк ФИПИ
В магазине продаётся N товаров нескольких артикулов. Товары одного артикула имеют одинаковую цену. Учёт товаров ведётся поштучно, для каждой единицы товара известен её текущий статус (продана или нет). Товары разделены на две категории: дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает среднюю цену (среднее арифметическое) всех товаров в базе данных магазина без учёта их текущего статуса. Остальные товары считаются дешёвыми.
Лидером продаж называется товар с таким артикулом, наибольшее количество единиц которого продано. Лидер продаж выбирается среди дорогих товаров, а если продано одинаковое количество дорогих товаров с разными артикулами, лидером выбирается товар с наибольшей ценой. Если и таких товаров несколько, лидер продаж – тот из них, которого осталось меньше всего.
Найдите суммарную выручку магазина от реализации товара – лидера продаж, а также оставшееся количество товара с этим артикулом.
Входные данные
В первой строке входного файла находится число N – количество товаров в базе данных магазина (натуральное число, не превышающее 10 000). В каждой из следующих N строк находится три числа, разделённых пробелом: артикул товара (натуральное число, не превышающее 100 000), его цена (натуральное число, не превышающее 10 000) и статус (0, если товар уже продан, и 1, если ещё не продан).
Выходные данные
Два числа: сумма выручки от реализации товара – лидера продаж, а также количество товара с этим артикулом, оставшееся в магазине.
Типовой пример организации данных во входном файле
8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0
При таких исходных данных дорогими являются товары стоимостью 100 и 200 рублей. Больше всего было продано товара с артикулом 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ: 200 1.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.