Словари, множества и кортежи: поиск за один шаг

Если ты знаешь, почему список нельзя сделать ключом словаря и чем d[k] отличается от d.get(k), листай до «Теперь сам» в конце.

Как думаешь, сколько шагов уйдёт на поиск

Есть миллион пар «логин - число входов». Нужно узнать, сколько раз входил ivanov. Если пары лежат списком, придётся смотреть их подряд - в худшем случае миллион сравнений. Ответь себе до того, как читать дальше: можно ли найти нужную пару, не просматривая остальные, и что для этого нужно знать заранее?

На что это похоже

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

Механизм: номер ячейки из самого ключа

Словарь хранит записи в массиве ячеек. Номер ячейки он вычисляет из ключа особой функцией, которая превращает ключ в число, - её называют хеш-функцией. При поиске он вычисляет тот же номер и смотрит в одну ячейку, а не во все. Иногда двум ключам достаётся одна ячейка, и тогда приходится сделать пару лишних сравнений, - поэтому «один шаг» верен в среднем, а не всегда. Как этого добиваются и где это ломается, разбирает раздел про хеш-таблицы.

Из механизма следуют все свойства сразу:

Правило

Словарь - поиск значения по ключу, множество - проверка «есть ли», оба в среднем за один шаг. Ключи и элементы - только неизменяемые: числа, строки, кортежи из неизменяемых. d[k] на отсутствующем ключе - ошибка KeyError, d.get(k, запас) - нет. Пустой словарь - {}, пустое множество - set().

Разбор: подсчёт частот

Самая частая работа словаря в этом курсе - посчитать, сколько раз встречается каждое значение:

slova = ["кот", "пёс", "кот", "ёж", "кот", "пёс"]
chastoty = {}
for w in slova:
    chastoty[w] = chastoty.get(w, 0) + 1
print(chastoty)
print(chastoty["кот"], chastoty.get("лис", 0), "лис" in chastoty)
for w, k in chastoty.items():
    print(w, k)
try:
    print(chastoty["лис"])
except KeyError as e:
    print("нет ключа", e)

{'кот': 3, 'пёс': 2, 'ёж': 1}
3 0 False
кот 3
пёс 2
ёж 1
нет ключа 'лис'

chastoty.get(w, 0) - «значение или ноль, если слова ещё не было». Без него первая же встреча нового слова упала бы с KeyError. Весь подсчёт - один проход по списку, по одному шагу на слово. items() отдаёт пары «ключ, значение», и for w, k in раскладывает каждую пару по двум именам. Порядок обхода - порядок добавления: так словарь устроен начиная с Python 3.7.

Сравни с наивным способом: slova.count(w) для каждого слова. count проходит весь список, и на n словах получается n проходов по n - квадрат вместо линии.

Разбор: множества и кортежи как ключи

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a & b, a | b, a - b)
print(set([3, 1, 3, 2, 1]) == {1, 2, 3})
kletki = {(0, 0), (0, 1)}
kletki.add((2, 3))
print((0, 1) in kletki, (1, 0) in kletki)
x, y = (2, 3)
print(x + y)
try:
    d = {[1, 2]: "список"}
except TypeError as e:
    print("ошибка:", e)

{3, 4} {1, 2, 3, 4, 5} {1, 2}
True
True False
5
ошибка: unhashable type: 'list'

& - пересечение, | - объединение, - - разность. set(список) выбрасывает повторы. Клетку поля удобно хранить кортежем (строка, столбец): он неизменяем и годится в множество, а (0, 1) и (1, 0) - разные клетки. x, y = (2, 3) раскладывает кортеж по именам - это та же запись, что работала в обмене a, b = b, a: справа там стоял кортеж. Список ключом быть не может: Python отвечает «unhashable», то есть «из этого нельзя вычислить номер ячейки». То же с кортежем, внутри которого лежит список: сам кортеж не меняется, но список в нём может, и номер ячейки из такого ключа Python вычислить откажется.

Что ломается без этого

{} - это пустой словарь, а не множество: s = {} и затем s.add(1) падает. Порядок элементов множества не гарантирован: программа, которая печатает множество и сравнивает вывод со строкой, на другом наборе чисел сломается. Проверка if x in spisok внутри цикла по другому списку незаметно делает алгоритм квадратичным - замена списка на множество снимает это одной строкой. И если ключ составной, его пишут кортежем: строка f"{x},{y}" тоже работает, но её надо собирать на каждом обращении.

Зачем это в работе

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

Теперь сам

Дан список a. Напиши, как за один проход узнать, есть ли в нём два одинаковых числа, и скажи, что напечатает твой код на [4, 1, 7, 1].

vidennye = set()
povtor = False
for x in a:
    if x in vidennye:
        povtor = True
    vidennye.add(x)
print(povtor)