Множества и уникальность

Словарь из прошлого занятия отвечал на вопрос «сколько раз». Но часто нужно другое — просто «встречалось или нет». Для этого есть множество.

values = set()          # пустое множество

values.add(5)
values.add(3)
values.add(5)           # уже есть — ничего не изменится

print(len(values))      # 2
print(5 in values)      # True

Список можно превратить в множество одним действием, и повторы исчезнут сами:

a = [3, 8, 3, 1, 8]
print(len(set(a)))      # 3 — сколько различных
print(sorted(set(a)))   # [1, 3, 8]

Пустое множество записывается как set(), а не {} — фигурные скобки без содержимого означают пустой словарь. Это единственная неловкость в записи, дальше всё просто.

Множество похоже на словарь, у которого есть ключи и нет значений. Так оно, по сути, и устроено.

Три вещи, которых ученик обычно ждёт от множества по привычке к спискам, — и не находит.

Нет порядка. Элементы хранятся так, как удобно самому Python. Печатать множество напрямую бессмысленно: порядок может оказаться каким угодно. Если нужен определённый — сортируйте: sorted(values).

Нет повторов. Добавить одно и то же дважды не выйдет, второй раз ничего не произойдёт. Это ровно то, за что множество и берут, — но если вопрос «сколько раз», нужен словарь.

Нет номеров. values[0] — ошибка. У элементов нет позиций, и «третий элемент множества» — бессмысленное словосочетание.

Выбирать структуру по задаче — это и есть навык занятия. Множество не «лучше» списка, оно про другое.

a = [4, 4, 2, 4, 2]
print(len(set(a)))

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

Запись x in a для списка выглядит коротко, но внутри это проход по всем элементам. Один раз — незаметно. А вот так — уже нет:

for x in queries:            # сто тысяч запросов
    if x in a:               # проход по ста тысячам элементов
        ...

Десять миллиардов действий — решение не пройдёт. Замена одной строки всё меняет:

values = set(a)              # один раз
for x in queries:
    if x in values:          # мгновенно, независимо от размера
        ...

Проверка в множестве не зависит от количества элементов: и в сотне, и в миллионе она занимает одно и то же время. Причина — то же устройство, что у словаря.

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

Два множества можно сравнивать и соединять — привычными знаками.

first = {1, 2, 3}
second = {3, 4}

print(first | second)     # {1, 2, 3, 4} — объединение
print(first & second)     # {3} — пересечение
print(first - second)     # {1, 2} — разность
print(first ^ second)     # {1, 2, 4} — ровно в одном

Каждая из них заменяет цикл с проверками — и работает быстрее написанного вручную.

Операции можно соединять: first & second & third даёт значения, встречающиеся во всех трёх.

В первом списке значения 1, 2, 2, 3. Во втором — 3, 4, 4.

Сколько элементов окажется в объединении множеств? Введите целое число.

Печать множества напрямую. print(values) выведет фигурные скобки и элементы в непредсказуемом порядке. Для ответа нужны sorted и print(*result).

Потеря повторов там, где они нужны. Превратили список в множество — и «сколько раз встретилось» уже не спросить. Если нужны частоты, множества мало.

Порядок в цикле. В задачах вида «есть ли пара с суммой $x$» число добавляют в множество после проверки. Иначе элемент найдёт сам себя и ответ окажется неверным при $x$, равном удвоенному значению.

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

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

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

Часть задач решается одной операцией над множествами — это нормально: смысл в том, чтобы узнать нужную операцию, а не написать её вручную.

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

Задача: «даны список чисел и число $x$; есть ли в списке два элемента с разными номерами, сумма которых равна $x$?»

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

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

seen = set()
answer = "NO"

for value in a:
    seen.add(value)
    if x - value in seen:
        answer = "YES"
        break

print(answer)

На большинстве тестов ответ верный, но на входе из одного числа 5 и $x = 10$ программа отвечает YES, хотя пары нет. Объясните, почему так вышло, и исправьте.