Чек-лист «как сделать dict медленным»

В этом уроке соберём все ошибки, которые превращают O(1) dict в кошмар. Если в вашем коде есть один из этих паттернов, найдите и почините — обычно это даёт 10-100× ускорение бесплатно.

Анти-паттерн 1: mutable как ключ — TypeError

Ключ dict должен быть hashable, а значит immutable. Попытка использовать list, dict или set как ключ приводит к ошибке:

d = {}
try:
    d[[1, 2, 3]] = "value"
except TypeError as e:
    print(e)   # unhashable type: 'list'

try:
    d[{"a": 1}] = "value"
except TypeError as e:
    print(e)   # unhashable type: 'dict'

Решения:

# вместо list — tuple
d[(1, 2, 3)] = "value"     # OK

# вместо set — frozenset
d[frozenset({"a", "b"})] = "value"  # OK

# вместо dict — tuple отсортированных items
d[tuple(sorted({"a": 1, "b": 2}.items()))] = "value"

Это не оптимизация, это корректность. Mutable ключи неhashable намеренно: если бы их можно было использовать, их мутация после вставки сломала бы dict.

Анти-паттерн 2: огромные ключи (длинные строки/байты)

Хеш строки — O(длины). Чем длиннее ключ, тем дольше каждая операция:

import time

# короткие ключи
d = {}
start = time.perf_counter()
for i in range(100_000):
    d[f"k{i}"] = i
t_short = time.perf_counter() - start

# длинные ключи
d = {}
start = time.perf_counter()
for i in range(100_000):
    d["a" * 1000 + str(i)] = i
t_long = time.perf_counter() - start

print(f"short keys: {t_short*1000:.0f} ms")
print(f"long keys:  {t_long*1000:.0f} ms")
print(f"ratio: {t_long/t_short:.1f}x")

На M-class CPU:

• short keys (~5 байт): ~25 ms
• long keys (1004 байт): ~150 ms
• Ratio ~6×

Хеш строки a*1000 стоит ~700 ns против ~10 ns для короткой. На 100К вставок это +70 ms.

Решения:

1. Используйте int-ключи там, где возможно. Особенно если ключ — это UUID, конвертируйте в int (UUID.int).
2. Если строки большие и читаются повторно — переходите на хеш через hashlib.blake2b(data, digest_size=8) -> int. Это даёт 8-байтные ключи и стабильный хеш между запусками.

import hashlib

def short_key(s: str) -> int:
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), 'big')

# на 100K вставок длинных строк через short_key
# выигрыш ~3-4× по сравнению с прямым использованием строк

Анти-паттерн 3: dataclass без frozen=True

from dataclasses import dataclass

@dataclass
class User:
    user_id: int
    name: str

u = User(1, "Anna")
try:
    s = {u}            # хотим положить в set
except TypeError as e:
    print(e)           # unhashable type: 'User'

По умолчанию dataclass:

• Генерирует __eq__ (если eq=True, дефолт).
• Устанавливает __hash__ = None — потому что mutable + custom eq.

Это намеренная защита: если объект mutable, его хеш может измениться, и он потеряется в dict/set.

Решение: frozen=True.

@dataclass(frozen=True)
class User:
    user_id: int
    name: str

u = User(1, "Anna")
s = {u}                # OK
d = {u: "value"}       # OK
print(hash(u))         # генерируется автоматически

frozen=True делает две вещи:

1. Запрещает мутацию (попытка u.name = "X" даёт FrozenInstanceError).
2. Автогенерирует __hash__ = hash от tuple всех полей.

Это правильный паттерн для бизнес-объектов, которые кладёте в dict/set.

Анти-паттерн 4: «полу-плохой» __hash__

Хуже отсутствия __hash__ — кастомный, который кажется работающим, но даёт коллизии:

class Order:
    def __init__(self, user_id, product_id, qty):
        self.user_id = user_id
        self.product_id = product_id
        self.qty = qty

    def __hash__(self):
        return hash(self.user_id)   # хешируем только по user_id

    def __eq__(self, other):
        return (self.user_id == other.user_id and
                self.product_id == other.product_id and
                self.qty == other.qty)

Что плохого? Если у одного user_id много заказов (что нормально), все они получают один и тот же хеш. Когда вы кладёте 100К заказов от 1000 разных user’ов, в среднем 100 заказов имеют один хеш. Это даёт probing-цепочки длиной до 100 — операции замедляются в 50-100 раз.

Решение: хешируйте по всем полям, участвующим в __eq__:

class Order:
    def __hash__(self):
        return hash((self.user_id, self.product_id, self.qty))

Или используйте @dataclass(frozen=True) — он автоматически делает правильно:

@dataclass(frozen=True)
class Order:
    user_id: int
    product_id: int
    qty: int
# __hash__ = hash((user_id, product_id, qty)) — автоматически

Анти-паттерн 5: list-based dedup

Самая частая ошибка junior’ов:

# плохо
unique = []
for item in data:
    if item not in unique:    # O(n) проверка
        unique.append(item)

# хорошо — set
unique = list(set(data))      # O(n) total, теряем порядок

# хорошо — dict.fromkeys, сохраняем порядок (3.7+)
unique = list(dict.fromkeys(data))

На 1M записей разница 1000-10000× в зависимости от числа дублей.

Анти-паттерн 6: дублирующие lookup

Каждое обращение к dict — операция. Если вы делаете её несколько раз для одного ключа, теряете время:

# плохо — два lookup'а
if "name" in user_dict:
    name = user_dict["name"]
else:
    name = "Unknown"

# хорошо — один lookup
name = user_dict.get("name", "Unknown")

# плохо — три lookup'а внутри цикла
for user_id in user_ids:
    if user_id in lookup:
        if lookup[user_id]["country"] == "RU":
            ru_users.append(lookup[user_id])

# хорошо — один lookup, кешируем
for user_id in user_ids:
    user = lookup.get(user_id)
    if user and user["country"] == "RU":
        ru_users.append(user)

Разница на сотнях миллионов операций — секунды.

Анти-паттерн 7: dict перестроение при каждом вызове

def is_in_whitelist(item):
    whitelist = ["alice", "bob", "carol", ...]  # пересоздаётся каждый вызов
    return item in whitelist

Это вдвойне плохо:

1. Каждый вызов создаёт новый list (alloc + GC).
2. in list — O(n).

Решение: вынести структуру в module-level или использовать lru_cache:

_WHITELIST = frozenset(["alice", "bob", "carol"])  # один раз

def is_in_whitelist(item):
    return item in _WHITELIST   # O(1) lookup

frozenset вместо set — потому что неизменяемый, можно делать module-level безопасно.

Анти-паттерн 8: ненужное преобразование dict-keys в list

# плохо
keys_list = list(d.keys())
if "key" in keys_list:    # O(n) поиск в list!
    ...

# хорошо
if "key" in d:            # O(1) — dict сам поддерживает in
    ...

dict.keys() — это view, не list. in на dict работает за O(1) напрямую. Преобразование в list создаёт временную копию и теряет O(1) свойство.

Реальный случай: dataclass без __hash__ vs hash(frozenset(...))

Допустим, у вас приложение с permissions. Один пользователь имеет набор прав. Вам нужен dict, где ключ — «множество прав», значение — название роли.

Подход 1: dataclass без frozen

@dataclass
class Permissions:
    perms: frozenset[str]

# не сработает — Permissions не hashable
roles = {Permissions(frozenset({"read"})): "viewer"}   # TypeError

Подход 2: dataclass с frozen=True

@dataclass(frozen=True)
class Permissions:
    perms: frozenset[str]

roles = {
    Permissions(frozenset({"read"})): "viewer",
    Permissions(frozenset({"read", "write"})): "editor",
}

# работает, но overkill: класс ради одного поля

Подход 3: прямо frozenset

roles = {
    frozenset({"read"}): "viewer",
    frozenset({"read", "write"}): "editor",
    frozenset({"read", "write", "delete"}): "admin",
}

# работает, минимум кода
user_perms = frozenset({"write", "read"})
print(roles[user_perms])   # "editor"

Если хранится одно поле — используйте напрямую (frozenset, tuple). Если несколько — @dataclass(frozen=True). Никогда — обычный dataclass для ключей.

Профилирование: где у вас dict ест время

Используйте cProfile, чтобы найти горячие dict-операции:

import cProfile
import pstats

def my_pipeline():
    # ваш код с dict
    ...

profiler = cProfile.Profile()
profiler.enable()
my_pipeline()
profiler.disable()

stats = pstats.Stats(profiler).sort_stats('cumulative')
stats.print_stats(20)

Что искать:

• Много вызовов __hash__ или __eq__ на одной строке — подозрение на коллизии.
• Время в dict.__contains__ или dict.__getitem__ несоизмеримо большое — медленный hash() или плохой hash.
• Множественные обращения к одному ключу — паттерн «дублирующие lookup».

Чек-лист для review

Когда смотрите чужой код:

1. [ok] Все ли ключи immutable? Любая попытка положить list или mutable объект?
2. [ok] Если custom класс — есть ли @dataclass(frozen=True) или явные hash/eq?
3. [ok] Нет ли if x in some_list в цикле — пора в set/dict?
4. [ok] Нет ли дублирующих lookup d[k] d[k] рядом?
5. [ok] Длинные строковые ключи — есть ли возможность сократить (UUID.int, blake2b)?
6. [ok] Постоянные структуры (whitelist’ы, mappings) — вынесены в module-level frozenset/dict?

Попробуй сам

import time

# 1. Найдите анти-паттерны в этом коде
# (см. ниже исправленные варианты)
def slow_process(data):
    seen = []
    result = []
    for item in data:
        if item not in seen:
            seen.append(item)
            result.append(item.upper())
    return result

# исправленный
def fast_process(data):
    seen = set()
    result = []
    for item in data:
        if item not in seen:
            seen.add(item)
            result.append(item.upper())
    return result

# сравните на 100K элементах с 90% дублей
data = ["key_" + str(i % 10000) for i in range(100_000)]

start = time.perf_counter()
slow_process(data)
print(f"slow: {(time.perf_counter()-start)*1000:.0f} ms")

start = time.perf_counter()
fast_process(data)
print(f"fast: {(time.perf_counter()-start)*1000:.0f} ms")

# 2. dataclass без frozen — что будет с set?
from dataclasses import dataclass

@dataclass
class User:
    user_id: int
    name: str

try:
    s = {User(1, "A"), User(2, "B")}
except TypeError as e:
    print(f"\nTypeError: {e}")

# с frozen
@dataclass(frozen=True)
class UserFrozen:
    user_id: int
    name: str

s = {UserFrozen(1, "A"), UserFrozen(2, "B"), UserFrozen(1, "A")}   # дубль
print(f"frozen set: {len(s)} elements")   # 2 — дубль отсеян

# 3. Преобразование длинных строк в короткие хеши
import hashlib

def short(s):
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), 'big')

long_keys = ["very_long_string_with_uuid_" + str(i) for i in range(100_000)]

start = time.perf_counter()
d = {}
for k in long_keys:
    d[k] = 1
t1 = time.perf_counter() - start

start = time.perf_counter()
d = {}
for k in long_keys:
    d[short(k)] = 1
t2 = time.perf_counter() - start

print(f"\nlong str keys:  {t1*1000:.0f} ms")
print(f"hashed int keys: {t2*1000:.0f} ms")
print(f"ratio: {t1/t2:.1f}x")

В следующем модуле переходим к деревьям. Hash-таблицы остаются за нами — вы теперь знаете, как они работают, что внутри, и как не делать их медленными.