Словарь как таблица частот

Тогда мы считали частоты массивом счётчиков и честно оговорили ограничение: он годится, только пока значения невелики. Для чисел до миллиарда таблицу не построить, а для слов — тем более.

Средство, которое снимает это ограничение, называется словарём. Он хранит пары «ключ — значение» и умеет мгновенно находить значение по ключу.

counts = {}                 # пустой словарь

counts["cat"] = 3           # положили пару
counts["dog"] = 1

print(counts["cat"])        # 3
print(len(counts))          # 2 — сколько пар
print("cat" in counts)      # True — есть ли такой ключ

Ключом может быть число, строка — что угодно неизменяемое. Значением — что угодно вообще.

Главное отличие от массива счётчиков: словарь хранит только те ключи, которые вы в него положили. Миллиард возможных значений не занимает миллиард ячеек — занимают место лишь встреченные.

И ещё: обращение к отсутствующему ключу — ошибка. counts["fish"] остановит программу с KeyError. Про это — следующий блок.

Приём, ради которого словарь и вводится:

counts = {}

for x in a:
    counts[x] = counts.get(x, 0) + 1

Три слова про get. Метод возвращает значение по ключу, а если ключа нет — то, что указано вторым аргументом. Без него пришлось бы писать длиннее:

for x in a:
    if x in counts:
        counts[x] += 1
    else:
        counts[x] = 1

Оба варианта верны, но первый короче и читается сразу. Просто counts[x] += 1 без подготовки работать не будет: чтобы прибавить единицу, надо сначала что-то прочитать, а ключа ещё нет.

Один проход — и известны частоты всех значений. Дальше словарь отвечает почти на всё:

counts = {}
counts["a"] += 1

Что случится при выполнении второй строки?

Обход словаря даёт ключи:

for key in counts:
    print(key, counts[key])

В каком порядке? В том, в каком ключи добавлялись. Словарь в Python помнит порядок вставки — и это не мелочь, а рабочий инструмент: задача «первое по появлению» решается обходом словаря без всякой сортировки.

А вот «по возрастанию значения» — уже другое. Для этого ключи надо отсортировать явно:

for key in sorted(counts):
    print(key, counts[key])

Эти два ответа различаются, и путать их — самая частая ошибка темы. Условие всегда говорит, какой порядок нужен: «первое по порядку» — обход как есть, «наименьшее» или «по возрастанию» — сортировка.

И отдельно: «первое значение, встречающееся один раз» — это первое в списке, а не в словаре. Тут надо пройти список ещё раз, спрашивая частоты у словаря:

for x in a:
    if counts[x] == 1:
        print(x)
        break

Ключ не обязан быть самим элементом. Часто в него кладут вычисленный признак, и тогда словарь группирует данные.

Задача: сколько среди чисел таких, у которых одинаковая сумма цифр?

counts = {}
for x in a:
    key = digit_sum(x)          # признак, а не само число
    counts[key] = counts.get(key, 0) + 1

Тот же приём решает задачу про анаграммы: слова, отличающиеся только порядком букв, дают одинаковый признак, если буквы расставить по алфавиту.

key = "".join(sorted(word))     # "listen" и "silent" дают "eilnst"

Осталось сложить слова с одинаковым признаком в один словарь — и количество групп станет количеством ключей.

Правило: если задача звучит как «сгруппировать по чему-то» или «сколько разных чего-то», подумайте, что взять ключом. Часто это и есть всё решение.

В список из 10 чисел записаны значения 5, 5, 7, 5, 7, 9, 9, 9, 9, 5.

Сколько пар окажется в словаре частот? Введите целое число.

Обращение к отсутствующему ключу. counts[x] += 1 без подготовки или чтение частоты значения, которого не было. Признак: KeyError. Лечение — get с значением по умолчанию.

Перепутанный порядок. Обошли словарь там, где нужен порядок из списка, — и получили не первое по появлению, а первое по добавлению ключа. Или наоборот, забыли sorted, когда просили «наименьшее». Программа не падает, ответ просто не тот.

Сортировка вместо словаря. Задачи вроде «сколько различных» решаются словарём за один проход. Сортировка тоже сработает, но она дороже и в задачах с ограничением по времени может не пройти.

Как проверять себя

• все элементы одинаковые — в словаре одна пара;
• все элементы разные — пар столько же, сколько элементов;
• искомого значения нет — не падает ли программа;
• два значения с равной частотой — правильный ли выбирается по условию.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

В задачах со звёздочкой словарь работает не как таблица частот, а как память о просмотренном: пары с заданной суммой ищутся одним проходом, если для каждого числа спрашивать, сколько подходящих встретилось раньше.

Задача: «дан список чисел; выведите наименьшее значение, которое встречается ровно один раз, или NONE, если такого нет».

Ученик написал:

n = int(input())
a = list(map(int, input().split()))

counts = {}
for x in a:
    counts[x] = counts.get(x, 0) + 1

answer = "NONE"
for key in counts:
    if counts[key] == 1:
        answer = key
        break

print(answer)

На многих тестах программа отвечает верно, но не на всех. Найдите вход, на котором она ошибается, объясните причину и предложите два способа исправить.