set — это дёшево упрощённый dict

Если вы поняли, как устроен Python dict (модуль 8 и предыдущие уроки этого модуля), set вы поймёте за минуту. Set — это dict без values: только ключи, без привязанных значений.

# логически:
s = {1, 2, 3}   # set
# эквивалентно (по структуре):
d = {1: None, 2: None, 3: None}.keys()

Внутри Python set имеет почти ту же реализацию, что dict: массив слотов, hash-функция, probing с perturbation, resize по threshold. Различия минимальны:

1. Каждый слот хранит только (hash, key) — без value. Это экономит ~33% памяти.
2. Threshold load factor чуть другой — Python set использует 5/8 = 0.625 вместо 2/3 для dict. Чуть агрессивнее ресайзит.
3. Compact representation set имеет, но без сохранения порядка вставки — set неупорядочен.

Все остальные характеристики идентичны:

• O(1) average для add, remove, in.
• Resize при достижении threshold.
• Кеширование хеша в каждом слоте.
• Probing формула j = (5*j + 1 + perturb) & mask.

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

s = set()
s.add(1)
s.add(2)
s.add(1)        # дубль игнорируется
print(s)        # {1, 2}
print(len(s))   # 2

# проверка наличия — O(1)
print(1 in s)   # True
print(99 in s)  # False

# удаление
s.remove(1)     # KeyError если нет
s.discard(99)   # без ошибки
s.pop()         # любой элемент (но не «первый» — порядок неопределён)

# создание из iterable
s = set([1, 2, 3, 1, 2])  # {1, 2, 3} — дубли отсеиваются

# литерал — фигурные скобки, но НЕ пустые
empty = set()         # пустой set
empty = {}            # это пустой dict! ловушка

Множественные операции: union, intersection, difference

Главная сила set — операции над множествами. Они реализованы эффективно и работают с разной сложностью.

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

# объединение — все элементы
print(a | b)               # {1, 2, 3, 4, 5, 6, 7, 8}
print(a.union(b))          # то же самое

# пересечение — общие
print(a & b)               # {4, 5}
print(a.intersection(b))   # то же

# разность — в a, но не в b
print(a - b)               # {1, 2, 3}
print(a.difference(b))     # то же

# симметрическая разность — в одном или другом, но не в обоих
print(a ^ b)               # {1, 2, 3, 6, 7, 8}

Сложность множественных операций

Сложность зависит от размеров двух множеств. Обозначим n = len(a), m = len(b).

Особенно интересна intersection: O(min(n, m)). Python оптимально выбирает: всегда перебирает меньшее множество, проверяя каждый элемент в большем за O(1).

small = {1, 2, 3}
big = set(range(1_000_000))

# Python переберёт 3 элемента small, не миллион big
result = small & big   # очень быстро

Этот трюк не работает с list:

# list & list — несуществующая операция, пришлось бы:
result = [x for x in small_list if x in big_list]   # O(n*m), катастрофически медленно

frozenset — immutable set

frozenset — это set, который нельзя менять после создания. Это даёт два важных свойства:

1. frozenset hashable — можно класть в dict-ключ и в другой set.
2. Зафиксированный хеш — считается один раз при создании.

fs = frozenset([1, 2, 3])
# fs.add(4)   # AttributeError — нет .add()

print(hash(fs))     # OK, есть hash
d = {fs: "value"}   # OK, можно как ключ

# обычный set нельзя
s = set([1, 2, 3])
# hash(s)    # TypeError: unhashable type: 'set'
# d = {s: "value"}   # TypeError

Где используется в DE:

# словарь по «множеству признаков»
permissions = {
    frozenset({"read"}): "viewer",
    frozenset({"read", "write"}): "editor",
    frozenset({"read", "write", "delete"}): "admin",
}

user_perms = frozenset({"write", "read"})   # порядок не важен — set
print(permissions[user_perms])  # "editor"

Без frozenset пришлось бы превращать множество в отсортированный tuple — больше кода, медленнее.

Эксперимент: set vs list для дедупа

Дедупликация — главный use-case set:

import time

# подготовим 10М записей с 70% дублей
data = list(range(3_000_000)) * 4  # дублируем 4 раза
import random
random.shuffle(data)

# через set
start = time.perf_counter()
unique_set = set(data)
t_set = time.perf_counter() - start

# через list (наивный)
start = time.perf_counter()
seen = []
unique_list = []
for x in data:
    if x not in seen:    # O(n) проверка!
        seen.append(x)
        unique_list.append(x)
# этот вариант на 12М элементах не дождётесь — O(n^2)

# через dict.fromkeys (сохраняет порядок)
start = time.perf_counter()
unique_ordered = list(dict.fromkeys(data))
t_dict = time.perf_counter() - start

print(f"set:       {t_set*1000:.0f} ms, {len(unique_set)} unique")
print(f"dict-keys: {t_dict*1000:.0f} ms, {len(unique_ordered)} unique")

Результаты:

• set: ~150-200 ms на 12М записей
• dict.fromkeys: ~250-300 ms (плюс сохраняет порядок)
• list+in: не дождётесь (квадратичная сложность)

Правило: для дедупа всегда используйте set или dict.fromkeys (если нужен порядок). Никогда list+in.

Set-операции в DE

Кейс 1: «Кого нет у нас»

source_ids = {1, 5, 7, 12, 99, ...}     # ID в source системе
existing_ids = {1, 7, 12, 100, ...}      # ID, которые у нас уже есть

# кого нужно загрузить
to_import = source_ids - existing_ids   # O(n) — одна операция

# кого нужно удалить (есть у нас, но удалили в source)
to_delete = existing_ids - source_ids

Без set это было бы вложенный цикл по двум коллекциям.

Кейс 2: «Пользователи, активные сразу в двух фичах»

feature_a_users = set(feature_a_events_user_ids)
feature_b_users = set(feature_b_events_user_ids)

both = feature_a_users & feature_b_users  # O(min(|A|, |B|))
print(f"Cross-feature users: {len(both)}")

Кейс 3: «Дедуп составных ключей»

events = [
    {"user_id": 1, "event": "click", "ts": "2025-01-01"},
    {"user_id": 1, "event": "click", "ts": "2025-01-01"},   # дубль по полю-кортежу
    ...
]

seen = set()
unique = []
for e in events:
    key = (e["user_id"], e["event"], e["ts"])   # tuple — hashable
    if key not in seen:
        seen.add(key)
        unique.append(e)

Память: set vs dict

Set экономит память по сравнению с dict — не хранит values:

import sys

# dict с 1M ключей
d = {i: None for i in range(1_000_000)}
print(f"dict:  {sys.getsizeof(d) / 1024 / 1024:.1f} MB")
# ~36 MB

# set с теми же ключами
s = set(range(1_000_000))
print(f"set:   {sys.getsizeof(s) / 1024 / 1024:.1f} MB")
# ~32 MB

Разница не очень большая — Python хранит values как указатели, и None это один shared singleton. Реальные dict[int, "long string value"] могут быть в разы больше.

Попробуй сам

import time
import sys

# 1. Сравните скорость set vs list для in
n = 1_000_000
lst = list(range(n))
st = set(range(n))

queries = list(range(0, n, 1000))

start = time.perf_counter()
for q in queries:
    q in lst
t_lst = time.perf_counter() - start

start = time.perf_counter()
for q in queries:
    q in st
t_st = time.perf_counter() - start

print(f"{len(queries)} queries:")
print(f"  list: {t_lst*1000:.0f} ms")
print(f"  set:  {t_st*1000:.3f} ms")
print(f"  ratio: {t_lst/t_st:.0f}x")

# 2. Set operations on large sets
a = set(range(0, 10_000_000, 2))   # 5M even
b = set(range(0, 10_000_000, 3))   # 3.3M div by 3

start = time.perf_counter()
both = a & b
print(f"\nintersection: {(time.perf_counter()-start)*1000:.0f} ms, {len(both)} elements")

start = time.perf_counter()
all_ = a | b
print(f"union:        {(time.perf_counter()-start)*1000:.0f} ms, {len(all_)} elements")

start = time.perf_counter()
only_a = a - b
print(f"difference:   {(time.perf_counter()-start)*1000:.0f} ms, {len(only_a)} elements")

# 3. frozenset как ключ
permissions = {
    frozenset({"read"}): "viewer",
    frozenset({"read", "write"}): "editor",
    frozenset({"read", "write", "delete"}): "admin",
}
user_set = frozenset({"write", "read"})
print(f"\nuser role: {permissions[user_set]}")

# 4. Дедуп списка словарей по составному ключу
events = [
    {"user_id": 1, "event": "click"},
    {"user_id": 2, "event": "view"},
    {"user_id": 1, "event": "click"},   # дубль
    {"user_id": 1, "event": "purchase"},
]

seen = set()
unique = []
for e in events:
    key = (e["user_id"], e["event"])
    if key not in seen:
        seen.add(key)
        unique.append(e)
print(f"\nUnique events: {unique}")

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