Set: тот же hash table, без values; big-O для set операций

set — это dict без values. Те же hash, open addressing, perturbation probe (формула (5*i + 1 + perturb) & mask, разобранная в M02-03), та же load factor 2/3. Различие — payload: вместо (hash, key, value) triples хранятся только (hash, key) pairs. Plus набор операций: | (union), & (intersection), - (difference), ^ (symmetric_difference) — со своими big-O оценками.

После этого урока вы должны знать big-O для каждой set-операции и уметь рассуждать, когда set лучше list или dict.

PySetObject struct

Полная декомпозиция (см. Include/cpython/setobject.h):

typedef struct {
    PyObject_HEAD
    Py_ssize_t fill;            // число занятых + dummy slots
    Py_ssize_t used;             // число живых entries
    Py_ssize_t mask;             // size - 1, для AND-mod
    setentry *table;             // массив (hash, key) pairs
    setentry smalltable[PySet_MINSIZE];  // встроенная маленькая table (8 slots)
    // ...
} PySetObject;

typedef struct {
    PyObject *key;               // элемент set'а (или dummy/empty sentinel)
    Py_hash_t hash;              // кэшированный hash
} setentry;

Сравнение с dict:

Set не имеет compact layout (PEP 468 применили только к dict): один sparse массив setentry размера ~3·N (load factor ≤ 2/3). Insertion order не сохраняется — итерация идёт в hash order (рандомизирован через PYTHONHASHSEED для str). Это намеренно: концептуально set — unordered collection.

import sys
print(sys.getsizeof(set()))                  # ~216 байт (smalltable 8 slots уже встроена)
print(sys.getsizeof({1, 2, 3}))              # ~216 байт (3 entries в smalltable)
print(sys.getsizeof(set(range(100))))        # ~8 KB (после resize'ов)

Set имеет встроенную smalltable размера PySet_MINSIZE = 8 — для маленьких сетов (до ~5 элементов с load factor 2/3) не нужна отдельная malloc’нутая table. См. Objects/setobject.c, set_lookkey() — аналог lookdict().

frozenset — immutable set

frozenset — это immutable вариант set: после создания нельзя добавлять/удалять элементы. Из-за immutability frozenset hashable — может быть ключом в dict или элементом другого set:

fs = frozenset({1, 2, 3})
d = {fs: 'value'}                  # OK - frozenset hashable
s = {1, 2, 3}
d = {s: 'value'}                   # TypeError: unhashable type: 'set'

# Frozenset of frozensets - OK:
nested = frozenset({frozenset({1, 2}), frozenset({3, 4})})
print(len(nested))                 # 2

Algorithm frozenset_hash (см. Objects/setobject.c) — XOR-сумма hash’ей элементов с BIT_ROTATE (порядок-независимая комбинация). Это означает: hash(frozenset({1, 2})) == hash(frozenset({2, 1})) — set равен по содержимому, не по порядку, и hash должен это отражать.

Use case: множество constants как dict key, deduplicated tags, immutable lookup table.

Big-O для set операций

Ключевые наблюдения:

• s & t (intersection) — O(min): CPython всегда iterate меньший set и проверяет membership в большем. Это умная оптимизация — при len(s)=10, len(t)=10**6, intersection стоит O(10), а не O(10⁶).
• s.issubset(t) — O(len(s)): проверяет каждый элемент s на membership в t. Если s намного меньше t — fast.
• Все set arithmetic O(n) — линейно по размеру операнда; никаких O(n²) если hash uniform.

small = set(range(10))
large = set(range(1_000_000))

# Хороший пример: O(min) - проходит только 10 элементов
print(small & large)              # O(10), даже если large 1M

# Плохой пример: обходит 1M элементов
print(large - small)              # O(1M)

Когда set лучше list

1. Membership-проверки в горячем цикле. Каноничный case, описан в M02-01:

# anti-pattern O(n*m):
for query in queries:                    # m запросов
    if query in big_list:                # O(n) per check
        ...
# = O(n * m) = 10⁶ * 10³ = 10⁹ ops

# Правильно O(n + m):
big_set = set(big_list)                  # O(n) one-time
for query in queries:
    if query in big_set:                 # O(1) per check
        ...
# = O(n + m) = 10⁶ + 10³ ≈ 10⁶ ops

2. Удаление дубликатов. Преобразование set(lst) за O(n) убирает дубликаты. Если нужно сохранить order — list(dict.fromkeys(lst)) (use dict’s insertion order):

lst = [1, 2, 2, 3, 1, 4]
print(list(set(lst)))                # [1, 2, 3, 4] - порядок не гарантирован
print(list(dict.fromkeys(lst)))      # [1, 2, 3, 4] - insertion order (3.7+)

3. Set arithmetic. Для задач типа «найти общих друзей», «теги, отсутствующие в фильтре», «xor двух коллекций» — set даёт естественный API + правильный big-O:

my_tags = {'python', 'data', 'rust'}
filter_tags = {'python', 'go'}
print(my_tags & filter_tags)         # {'python'} - intersection
print(my_tags - filter_tags)         # {'data', 'rust'} - difference
print(my_tags ^ filter_tags)         # {'data', 'rust', 'go'} - symmetric

Без set вы бы писали nested for-loops с list — медленно и не идиоматично.

Hash flood и protection

Всё, что описано в M02-03 для dict (hash randomization, perturbation probe для anti-clustering), applies to set. PYTHONHASHSEED randomizes hash для str/bytes — adversarial input не может составить N тысяч strings, коллидирующих в одну bucket. Без рандомизации worst-case x in s — O(n).

Custom __hash__ с константным значением (return 0) — degrade’ит set до O(n) per add/remove/contains, как и dict. Контракт: hash должен распределять uniformly.

Cross-course context

Cross-course → ClickHouse: 06/01 vectorized-execution — SELECT DISTINCT col в ClickHouse использует hash-set internally (один раз построил, потом O(1) per check) — та же идея preprocess-then-lookup, что и set(big_list) в Python. Vectorization: ClickHouse считает hash батчами по 65 536 строк за раз через SIMD, что даёт практический throughput ~100M строк/с на core; Python set — один элемент за раз через __hash__.

Ключевые выводы

1. set = dict без values — те же hash, open addressing, perturbation probe (M02-03). Per-slot payload 16 байт (hash, key) (vs 24 для dict).
2. Не имеет compact layout (PEP 468 — только для dict): один sparse массив setentry. Insertion order не preserved — итерация в hash order.
3. Big-O: O(1) avg для add/remove/contains; O(min) для intersection (умный choice меньшей стороны); O(n) для union/diff/symmetric.
4. frozenset immutable → hashable — может быть ключом в dict или элементом другого set. Algorithm frozenset_hash — XOR-сумма с rotate (order-independent).
5. Когда set лучше list: membership в горячем цикле, удаление дубликатов, set arithmetic (intersection/union/diff). Каноничный preprocess: s = set(lst) за O(n), потом O(1) per query.

В уроке M02-06 разберём mutability vs immutability не как философию, а как memory layout strategy: cache locality, sharing-safety, NumPy/Arrow параллели.