Множества
в Python

Категория

Структуры данных

Уровень

Базовый → средний

Связанные темы

Хеширование, словари, уникальность

Зачем это знать

Убирать повторы и быстро проверять принадлежность

§1Зачем нужно множество

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

value in big_list    Python сравнивает элементы по очереди
value in big_set     Python сразу вычисляет, где значение должно лежать

Множество — это, по сути, словарь без значений: та же хеш-таблица из главы 4.2, только хранятся одни ключи. Отсюда и оба его свойства: элементы уникальны, потому что ключи уникальны, и поиск мгновенный, потому что идёт по хешу.

§2Что хранит set

Множество (set) — изменяемая коллекция уникальных хешируемых элементов без порядка и индексов.

§3Создание множества

languages = {"Python", "Go", "Java"}
letters = set("hello")

print(sorted(languages))
print(sorted(letters))

['Go', 'Java', 'Python']
['e', 'h', 'l', 'o']

В слове hello две буквы l, но в множестве осталась одна. Вывод здесь обёрнут в sorted() намеренно — почему, объясняет §7.

§4Повторы исчезают

numbers = {1, 2, 2, 3, 1}

print(numbers)
print(len(numbers))

{1, 2, 3}
3

Добавление уже существующего элемента не создаёт второй экземпляр и не вызывает ошибку — операция просто ничего не делает. Это отличает add() от append() у списка.

§5Пустое множество

Фигурные скобки заняты словарём, поэтому пустое множество создают только функцией.

empty_set = set()
empty_dict = {}

print(type(empty_set))
print(type(empty_dict))

<class 'set'>
<class 'dict'>

Причина историческая: словарь появился в языке раньше и занял литерал {}. Ошибка коварна тем, что не проявляется сразу — {}.add(x) упадёт лишь на первой попытке добавить элемент.

§6Индексов нет

values = {10, 20, 30}
print(values[0])

TypeError: 'set' object is not subscriptable

Это не недоработка, а следствие устройства: элементы лежат в хеш-таблице по своим хешам, и «первого» среди них не существует. Нужен порядок — берите список.

§7Порядок не гарантирован

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

В отличие от словаря, который с Python 3.7 сохраняет порядок добавления, множество такой гарантии не даёт вовсе.

§8Перебор множества

Перебирать множество можно — цикл посетит каждый элемент ровно один раз.

roles = {"reader", "editor", "admin"}

for role in sorted(roles):
    print(role)

admin
editor
reader

Без sorted() результат тоже будет полным, но его порядок непредсказуем.

§9Проверка наличия

Это главная операция множества и причина его выбирать.

allowed = {"jpg", "png", "webp"}

print("png" in allowed)
print("exe" not in allowed)

True
True

Сравните с проверкой через or из главы 5.5: ext == "jpg" or ext == "png" or ext == "webp". Множество короче, а добавление нового формата — это правка одной строки.

§10Насколько это быстрее

Разница между in для списка и для множества не косметическая. В списке Python сравнивает элементы по очереди, в множестве — сразу вычисляет, где значение должно лежать.

import timeit

big_list = list(range(100_000))
big_set = set(big_list)

print(timeit.timeit(lambda: 99_999 in big_list, number=200))
print(timeit.timeit(lambda: 99_999 in big_set, number=200))

0.0819...
0.0000064...

Разница здесь — четыре порядка, и она растёт вместе с размером данных.

Отсюда практический приём: если по списку приходится часто проверять принадлежность, один раз преобразуйте его в множество — known = set(items) — и проверяйте уже по нему.

§11Элемент должен быть хешируемым

Требование то же, что к ключам словаря в главе 4.2, и по той же причине.

values = {[1, 2]}

TypeError: unhashable type: 'list'

Обратите внимание на последнюю строку: множество внутри множества невозможно, потому что set изменяем. Для этого случая существует frozenset — глава 4.9.

§12Равные значения разных типов

Уникальность определяется равенством, а не типом. Значения, равные друг другу, считаются одним элементом.

print({1, 1.0, True})

{1}

В Python 1 == 1.0 == True, а значит для множества это одно и то же значение. Остаётся тот экземпляр, который добавили первым. То же правило действует для ключей словаря, и на практике оно всплывает при смешивании целых и дробных чисел или bool с числами.

§13Удаление повторов

Самое частое применение множества в одну строку.

tags = ["python", "api", "python", "sql"]

print(sorted(set(tags)))

['api', 'python', 'sql']

Способ подходит, когда порядок не важен: обратное преобразование list(set(tags)) исходный порядок не восстанавливает.

§14Уникальность с порядком

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

tags = ["python", "api", "python", "sql"]

print(list(dict.fromkeys(tags)))

['python', 'api', 'sql']

dict.fromkeys() из главы 4.3 создаёт словарь, где ключи — элементы списка, а значения не нужны. Приём стоит запомнить: он решает задачу, которую множество решить не может.

§15Практика: уже обработанные

Второе классическое применение — запоминать, что уже встречалось.

task_ids = [101, 103, 101, 108, 103]
processed = set()

for task_id in task_ids:
    if task_id in processed:
        continue
    print("обработка", task_id)
    processed.add(task_id)

обработка 101
обработка 103
обработка 108

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

§16Когда set, когда list

Предпоследняя строка — про сравнение наборов: пересечение, объединение и разность. Это уже операции множеств, им посвящена глава 4.7.

§17Частые ошибки

§18Проверьте себя

§19Шпаргалка

Итог главы

Множество — это словарь без значений: та же хеш-таблица, поэтому элементы уникальны, а проверка принадлежности не зависит от размера коллекции. У множества нет индексов и нет гарантированного порядка, и для воспроизводимого вывода нужен sorted(). Элементы должны быть хешируемыми, а равные значения разных типов считаются одним элементом. Если вместе с уникальностью нужен порядок первого появления, множество не подходит — подходит dict.fromkeys().