Множества: set, frozenset, операции

set - неупорядоченная коллекция уникальных элементов. Под капотом - hash-таблица, как у dict, но без значений (только ключи). Это даёт O(1) для проверки наличия и идеально подходит для дедупликации и операций над множествами. В этом уроке - операции, frozenset как иммутабельный аналог, и типичные применения.

Создание

# Литерал
fruits = {"apple", "banana", "cherry"}

# Из iterable
unique = set([1, 2, 2, 3, 3, 3])   # {1, 2, 3} - автодедупликация
chars = set("hello")                # {'h', 'e', 'l', 'o'}

# Пустой - ТОЛЬКО через set(), не {}
empty = set()         # OK
empty_dict = {}        # это dict!

# Из comprehension
squares = {x ** 2 for x in range(5)}   # {0, 1, 4, 9, 16}

Базовые операции

s = {1, 2, 3}

# Добавление/удаление
s.add(4)               # {1, 2, 3, 4}
s.update([5, 6])       # {1, 2, 3, 4, 5, 6} - bulk
s.discard(10)          # тихо удалить если есть
s.remove(3)            # удалить, KeyError если нет
last = s.pop()         # удалить произвольный элемент
s.clear()              # очистить

# Проверка
3 in {1, 2, 3}          # True - O(1)
len({1, 2, 3})           # 3

# Итерация (порядок не определён)
for item in {"a", "b", "c"}:
    print(item)

Операции множеств

Главная сила set - математические операции:

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

# Объединение
a | b                    # {1, 2, 3, 4, 5, 6}
a.union(b)               # то же

# Пересечение
a & b                    # {3, 4}
a.intersection(b)

# Разность - в a но не в b
a - b                    # {1, 2}
a.difference(b)

# Симметрическая разность - в одном или другом, но не в обоих
a ^ b                    # {1, 2, 5, 6}
a.symmetric_difference(b)

# Подмножество / надмножество
{1, 2} <= a              # True - {1, 2} подмножество a
{1, 2} < a               # True - строгое подмножество
a >= {1, 2}              # True - a надмножество {1, 2}
a > {1, 2}               # True - строгое надмножество

# Непересекающиеся
{1, 2}.isdisjoint({3, 4})   # True

Inplace-варианты (модифицируют a):

a |= b      # a = a | b
a &= b      # a = a & b
a -= b      # a = a - b
a ^= b      # a = a ^ b

Практические применения

1. Дедупликация

items = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(items))   # [1, 2, 3, 4] - порядок может сбиться

Если порядок важен - используй dict.fromkeys() (см. идиомы в уроке про списки).

2. Быстрая проверка наличия

# Плохо - O(n) для каждого in
allowed_roles = ["admin", "moderator", "editor"]
if user.role in allowed_roles:   # линейный поиск
    ...

# Хорошо - O(1)
allowed_roles = {"admin", "moderator", "editor"}
if user.role in allowed_roles:   # hash lookup
    ...

Для большого списка с частыми проверками - set даёт ускорение.

3. Поиск пересечений / различий

backend_users = {"alice", "bob", "charlie"}
frontend_users = {"bob", "charlie", "dave"}

# Кто в обеих командах
both = backend_users & frontend_users   # {'bob', 'charlie'}

# Кто только в backend
backend_only = backend_users - frontend_users   # {'alice'}

# Кто во всей компании
all_devs = backend_users | frontend_users   # {'alice', 'bob', 'charlie', 'dave'}

4. Поиск разности списков

def added_items(old, new):
    return set(new) - set(old)

def removed_items(old, new):
    return set(old) - set(new)

print(added_items([1, 2, 3], [2, 3, 4]))     # {4}
print(removed_items([1, 2, 3], [2, 3, 4]))   # {1}

frozenset - иммутабельный set

fs = frozenset([1, 2, 3])
fs.add(4)   # AttributeError - immutable

Зачем нужен:

• Hashable - можно использовать как ключ dict или элемент другого set
• Гарантия неизменности при передаче в функции

# frozenset как ключ
groups = {
    frozenset(["admin", "user"]): "moderators",
    frozenset(["admin"]): "admins-only",
}

# Set из set нельзя, из frozenset можно
s_of_sets = {frozenset([1, 2]), frozenset([3, 4])}

Что может быть элементом set

Только hashable объекты, как ключи dict:

• Числа, строки, bytes
• tuple из hashable
• frozenset
• Большинство пользовательских классов

Mutable нельзя:

{[1, 2]}     # TypeError - list unhashable
{{1, 2}}    # TypeError - set unhashable
{(1, [2])}   # TypeError - tuple с mutable

Performance

Set значительно эффективнее list для проверок наличия и операций над множествами.

Set vs list - когда что

JSON не поддерживает set - надо конвертировать в list при сериализации.

Comprehensions

# Set comprehension
{x ** 2 for x in range(10) if x % 2 == 0}   # {0, 4, 16, 36, 64}

# Уникальные слова (case-insensitive)
text = "The quick brown fox jumps over the lazy dog"
unique_words = {word.lower() for word in text.split()}
print(len(unique_words))   # 8 - 'the' встречается дважды, посчитано один раз

Распространённые ошибки

1. {} как пустой set

empty_set = {}   # это dict!
empty_set = set()   # вот это правильно

2. Полагаться на порядок

s = {3, 1, 4, 1, 5, 9, 2, 6}
print(list(s))   # порядок НЕ гарантирован - может быть любым

Set неупорядоченный. Если нужен порядок - используй list или dict.

3. Set из непривычных значений

s = {None, 0, False, ""}
print(len(s))   # 2 - None и {0/False/""}

# Потому что 0 == False == 0.0 и hash одинаковый
{0, False, 0.0}   # {0} или {False} - первый сохранён

Hashable + equality определяют идентичность в set.

4. Удаление элементов во время итерации

s = {1, 2, 3, 4}
for x in s:
    if x > 2:
        s.remove(x)   # RuntimeError - set changed size during iteration

Используй копию:

for x in set(s):   # копия
    if x > 2:
        s.remove(x)

Множества и теория

Set - реализация математического множества. Поддерживает все классические операции:

• Объединение A ∪ B
• Пересечение A ∩ B
• Разность A \ B
• Симметрическая разность A △ B
• Подмножество A ⊆ B

Это особенно полезно для:

• Set-based алгоритмов
• Comparative analysis (что было/что стало)
• Permissions (роли пользователя как set)
• Tag filtering (товары с тегами в общем множестве)

Сравнение с Go и PHP

В Go встроенного set нет - используется map[T]struct{} или map[T]bool:

seen := make(map[int]struct{})
seen[1] = struct{}{}
_, ok := seen[1]   // проверка наличия

В PHP set реализуется через массив с ключами и array_unique() для дедупликации. Прямой set появился в SPL (SplObjectStorage) но мало используется.

Python set встроенный и идиоматичный - сразу доступен, удобный синтаксис операций.

Мини-задание

1. Дедупликация и операции:

team_a = ["alice", "bob", "charlie", "alice"]
team_b = ["bob", "dave", "alice"]

set_a = set(team_a)
set_b = set(team_b)

print(f"В обеих: {set_a & set_b}")
print(f"Только в A: {set_a - set_b}")
print(f"Только в B: {set_b - set_a}")
print(f"Все уникальные: {set_a | set_b}")

2. Быстрая проверка через set:

import time

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

start = time.perf_counter()
for _ in range(1000):
    99999 in big_list   # O(n) каждый раз
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(1000):
    99999 in big_set    # O(1) каждый раз
set_time = time.perf_counter() - start

print(f"list: {list_time:.4f}s")
print(f"set:  {set_time:.4f}s")

3. Frozenset как ключ:

permissions = {
    frozenset(["read"]): "viewer",
    frozenset(["read", "write"]): "editor",
    frozenset(["read", "write", "admin"]): "admin",
}

user_perms = frozenset(["read", "write"])
print(permissions.get(user_perms))   # editor

Что дальше

Освоили множества. В следующем уроке - collections module: специализированные коллекции стандартной библиотеки: Counter для подсчётов, deque для очередей, OrderedDict для legacy, ChainMap и defaultdict.