"""Граница худшего случая у `dict`: что стоит за «`O(1)` вместо `O(n)`».

`O(1)` у словаря — амортизированная средняя при равномерном хеше. Худший
случай — `O(n)`, и он не гипотетический: достаточно `__hash__`, который для
всех ключей возвращает одно и то же. Тогда все ключи садятся в одну цепочку
проб, и поиск последнего вставленного ключа перебирает всю цепочку.

Скрипт меряет две вещи:

  * **точно** — сколько раз вызвался `__eq__` на один поиск. Это счётчик, а не
    время: число не зависит ни от машины, ни от сборки;
  * **как иллюстрацию** — время поиска. Сравниваются только строки одного
    прогона (правило замеров репозитория).

Плюс цена пользовательских `__hash__`/`__eq__` против встроенных ключей.

    python3.13 bench/dict/hash_collisions.py
"""
import sys
import timeit


class Counter:
    eq_calls = 0
    hash_calls = 0

    @classmethod
    def reset(cls):
        cls.eq_calls = 0
        cls.hash_calls = 0


class Colliding:
    """Намеренно плохой `__hash__`: все объекты — в одну корзину."""

    __slots__ = ("i",)

    def __init__(self, i):
        self.i = i

    def __hash__(self):
        Counter.hash_calls += 1
        return 0

    def __eq__(self, other):
        Counter.eq_calls += 1
        return isinstance(other, Colliding) and self.i == other.i


class Spread:
    """Тот же класс, но хеш различает ключи."""

    __slots__ = ("i",)

    def __init__(self, i):
        self.i = i

    def __hash__(self):
        Counter.hash_calls += 1
        return hash(self.i)

    def __eq__(self, other):
        Counter.eq_calls += 1
        return isinstance(other, Spread) and self.i == other.i


def probe_counts(cls, n):
    """Сколько сравнений уходит на поиск первого и последнего ключа.

    Ищется **новый равный объект**, а не тот же самый: CPython сначала
    проверяет тождество (`startkey == key` идёт после `is`), и поиск того же
    объекта завершился бы на первом же слоте независимо от хеша.
    """
    d = {cls(i): i for i in range(n)}
    out = {}
    for label, i in (("первый вставленный", 0), ("последний вставленный", n - 1)):
        key = cls(i)
        Counter.reset()
        assert d[key] == i
        out[label] = (Counter.eq_calls, Counter.hash_calls)
    return out


def lookup_time_ns(cls, n, repeat=5):
    """Время одного поиска последнего вставленного ключа, нс."""
    d = {cls(i): i for i in range(n)}
    key = cls(n - 1)
    number = max(10, 200_000 // max(n, 1))
    best = min(timeit.repeat(lambda: d[key], number=number, repeat=repeat))
    return best / number * 1e9


def cost_of_key_kind():
    """Цена ключа: встроенные типы против пользовательских протоколов."""
    n = 1000
    cases = []

    d_int = {i: i for i in range(n)}
    last_int = n - 1                  # ключ вычисляется заранее: меряем поиск
    cases.append(("int", lambda: d_int[last_int]))

    keys_str = [f"key-{i}" for i in range(n)]
    d_str = {k: i for i, k in enumerate(keys_str)}
    last_str = keys_str[-1]
    cases.append(("str (кеш хеша в объекте)", lambda: d_str[last_str]))

    class Plain:
        __slots__ = ("i",)

        def __init__(self, i):
            self.i = i

    objs = [Plain(i) for i in range(n)]
    d_obj = {o: i for i, o in enumerate(objs)}
    last_obj = objs[-1]
    cases.append(("объект без __hash__/__eq__ (по id)", lambda: d_obj[last_obj]))

    class PyHash:
        __slots__ = ("i",)

        def __init__(self, i):
            self.i = i

        def __hash__(self):
            return hash(self.i)

        def __eq__(self, other):
            return isinstance(other, PyHash) and self.i == other.i

    pyobjs = [PyHash(i) for i in range(n)]
    d_py = {o: i for i, o in enumerate(pyobjs)}
    probe_py = PyHash(n - 1)          # новый равный объект: тождество не спасёт
    cases.append(("объект с __hash__/__eq__ на Python", lambda: d_py[probe_py]))

    out = []
    for label, fn in cases:
        number = 200_000
        best = min(timeit.repeat(fn, number=number, repeat=5))
        out.append((label, best / number * 1e9))
    return out


def main():
    print("PY", sys.version.split()[0])
    print("Числа времени — только для сравнения строк внутри этого прогона.")
    print()

    print("1. Сколько сравнений (__eq__) уходит на один поиск")
    print(f"{'n':>7} | {'плохой хеш: первый':>19} | {'плохой хеш: последний':>21}"
          f" | {'нормальный хеш: последний':>26}")
    print("-" * 84)
    for n in (16, 64, 256, 1024, 4096):
        bad = probe_counts(Colliding, n)
        good = probe_counts(Spread, n)
        print(f"{n:>7} | {bad['первый вставленный'][0]:>19} |"
              f" {bad['последний вставленный'][0]:>21} |"
              f" {good['последний вставленный'][0]:>26}")
    print("  Плохой хеш: число сравнений равно числу ключей — это и есть O(n).")
    print("  Нормальный хеш: одно сравнение независимо от размера — O(1).")
    print()

    print("2. Время поиска последнего ключа, нс (иллюстрация к таблице выше)")
    print(f"{'n':>7} | {'плохой хеш':>14} | {'нормальный хеш':>16} | {'во сколько раз':>15}")
    print("-" * 62)
    base_bad = base_good = None
    for n in (16, 64, 256, 1024, 4096):
        t_bad = lookup_time_ns(Colliding, n)
        t_good = lookup_time_ns(Spread, n)
        if base_bad is None:
            base_bad, base_good = t_bad, t_good
        print(f"{n:>7} | {t_bad:>14.1f} | {t_good:>16.1f} | {t_bad / t_good:>14.1f}x")
    print(f"  рост плохого хеша от n=16 к n=4096: x{lookup_time_ns(Colliding, 4096) / base_bad:.1f}")
    print(f"  рост нормального за то же           : x{lookup_time_ns(Spread, 4096) / base_good:.1f}")
    print()

    print("3. Цена самого ключа при отсутствии коллизий, нс на поиск")
    for label, ns in cost_of_key_kind():
        print(f"  {label:<38} {ns:8.1f}")
    print("  Пользовательский протокол оплачивается на каждом поиске: `__hash__`")
    print("  на Python — это вызов функции там, где у int и str его нет вовсе.")


if __name__ == "__main__":
    main()