Задание 24
тема 3 из 4

Словари и подсчёт частот

Словарь хранит пары «ключ — значение» и по ключу сразу находит значение, поэтому им считают, сколько раз встречается каждый символ, слово или номер. Частотный словарь пополняют строкой d[x] = d.get(x, 0) + 1, а самый частый ключ находят через max с key. Так же по ключу накапливают суммы, например объём данных каждого клиента в задании 26.

Реже в заданиях242627На карте навыков

Как считать частоты словарём

Словарь — набор пар «ключ — значение», в котором ключи не повторяются. В 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. 1.d['C'] = 1 добавляет третью пару, d['A'] += 2 меняет значение A на 3+2=53 + 2 = 5.
  2. 2.В словаре три пары, ключ B в нём есть.
  3. 3.Ключа D нет, d.get('D', 0) возвращает 0.

Ответ: 5 3 True 0

Хэш-таблица: почему поиск по ключу быстрый

Словарь Python устроен как хэш-таблица. Хэш-функция превращает ключ в число — хэш, а по хэшу вычисляется номер ячейки внутреннего массива, где лежит значение. Чтобы найти значение, не нужно просматривать все пары: достаточно вычислить хэш ключа и заглянуть в одну ячейку. Поэтому поиск, добавление и изменение по ключу занимают в среднем одно и то же время при любом размере словаря. Поиск в списке, наоборот, просматривает элементы по очереди.

Хэш ключа не должен меняться, иначе значение не найдётся. Поэтому ключом может быть только неизменяемый объект: число, строка, кортеж. Список изменяемый, и ключом он быть не может. Если ключ состоит из двух чисел, например координат клетки, берут кортеж (x, y).

Пример

Сохраните в словаре слово «клетка» по ключу из двух чисел 2 и 3 и прочитайте его.

  1. 1.Кортеж (2, 3) неизменяемый, его можно сделать ключом.
  2. 2.Программа печатает «клетка».
  3. 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. 1.Буква A стоит на местах 1, 3, 5, 7, 9 (счёт с нуля). После неё идут B, C, B, D, B.
  2. 2.Словарь частот: B — 3, C — 1, D — 1.
  3. 3.max(d, key=d.get) даёт B.

Ответ: B, 3 раза

Алфавитно-частотный словарь текста

Алфавитно-частотный словарь текста — список всех его слов в алфавитном порядке, и при каждом слове — сколько раз оно встретилось. Текст делят на слова методом split(), частоты считают частотным словарём, а ключи упорядочивает sorted(d).

Если слова нужны по убыванию частоты, а при равной частоте по алфавиту, пишут sorted(d, key=lambda w: (-d[w], w)): минус меняет порядок частот на убывающий. Ключ сортировки разобран в теме сортировка по ключу.

Пример

Постройте алфавитно-частотный словарь текста «кот ест мясо кот спит кот ест».

  1. 1.Частоты: кот — 3, ест — 2, мясо — 1, спит — 1.
  2. 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. 1.Суммы по клиентам: 101 — 20+90+48=15820 + 90 + 48 = 158, 202 — 110, 303 — 62.
  2. 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.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

1_26.txt

Потренируйте навык

Все задания на этот навык

Решать