"""Сложность операций: O-нотация, посчитанная, а не заученная.

Времени здесь нет — только счёт. O-нотация говорит не о секундах, а о том,
как растёт объём работы с ростом n. Работу проще всего посчитать прямо:
сколько раз Python сравнил два элемента. Для этого элементы — объекты
класса Key, который считает вызовы своих __eq__ и __lt__. Время — в cost.py.

СЕМЬ СЮЖЕТОВ:

1. ПОИСК. `x in list` сравнивает элементы по очереди: n сравнений, если
   элемент последний. `x in set` находит элемент по хешу: у Key без
   коллизий — одно сравнение на всех проверенных n (это наблюдение для
   этого набора, а не свойство множества — см. раздел 6). `bisect` по
   отсортированному списку — около log2(n).

2. APPEND. Список выделяет память с запасом, поэтому перевыделений на
   тысячи append — десятки, а не тысячи. Отсюда «амортизированное O(1)».

3. СКРЫТЫЙ КВАДРАТ. `[x for x in a if x in b]` — цикл внутри цикла, если
   b — список: n × n сравнений. Тот же код с b-множеством — ноль сравнений
   сверх хешей.

4. СОРТИРОВКА. sorted() на случайных данных делает около n·log2(n)
   сравнений — близко к lg(n!), теоретическому минимуму сортировки
   сравнениями в среднем, — а на уже отсортированных — ровно n − 1.

5. ХУДШИЙ СЛУЧАЙ СЛОВАРЯ. Если у всех ключей одинаковый хеш, поиск по
   ключу перестаёт быть O(1) и сравнивает ключи по очереди.

6. ХУДШИЙ СЛУЧАЙ МНОЖЕСТВА. То же для set: при одном хеше на всех поиск
   вызывает __eq__ порядка n раз (и больше n — множество проверяет часть
   ячеек повторно), а построение — порядка n²/2. Найденный по тождеству
   элемент __eq__ не вызывает вовсе. Счётчики — наблюдение CPython, не
   контракт языка.

7. BISECT И «НАШЛИ». bisect_left возвращает позицию вставки; найден ли
   элемент, решает отдельная проверка границы и равенства после неё.

Запускать: python3.11 / 3.12 / 3.13 / 3.14.
"""
import bisect
import math
import random
import sys

print("PY", sys.version.split()[0])
print()

COUNT = {"eq": 0, "lt": 0}


class Key:
    """Целое число, которое считает, сколько раз его сравнили."""

    __slots__ = ("v",)

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

    def __eq__(self, other):
        COUNT["eq"] += 1
        return self.v == other.v

    def __lt__(self, other):
        COUNT["lt"] += 1
        return self.v < other.v

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


def counted(fn):
    COUNT["eq"] = COUNT["lt"] = 0
    fn()
    return COUNT["eq"] + COUNT["lt"]


# ── 1 ─────────────────────────────────────────────────────────────────────
print("1) поиск: сколько сравнений, искомый элемент последний")
print(f"   {'n':>7}{'x in list':>12}{'x in set':>10}{'bisect':>8}{'log2(n)':>9}")
for n in (10, 100, 1_000, 10_000, 100_000):
    lst = [Key(i) for i in range(n)]
    st = set(lst)
    # Искомый — новый объект, равный последнему: иначе Python узнал бы его
    # по тождеству и не стал бы вызывать __eq__.
    target = Key(n - 1)
    c_list = counted(lambda: target in lst)
    c_set = counted(lambda: target in st)
    c_bis = counted(lambda: bisect.bisect_left(lst, target))
    print(f"   {n:>7}{c_list:>12}{c_set:>10}{c_bis:>8}{math.log2(n):>9.1f}")
unsorted = [5, 1, 4, 2, 3]
print(f"   bisect на неотсортированном {unsorted}, ищем 1: индекс {bisect.bisect_left(unsorted, 1)},"
      f" а 1 стоит на месте {unsorted.index(1)} — ошибки нет")
print()

# ── 2 ─────────────────────────────────────────────────────────────────────
print("2) append: сколько раз список перевыделял память")
EMPTY = sys.getsizeof([])
lst = []
capacities = []
last = sys.getsizeof(lst)
reallocs = {}
for i in range(1, 100_001):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != last:
        capacities.append((size - EMPTY) // 8)
        last = size
    if i in (1_000, 10_000, 100_000):
        reallocs[i] = len(capacities)
print("   первые ёмкости (мест под элементы):", capacities[:12])
for n, r in reallocs.items():
    print(f"   {n:>7} append — перевыделений: {r}")
print()

# ── 3 ─────────────────────────────────────────────────────────────────────
print("3) скрытый квадрат: [x for x in a if x in b], общих элементов нет")
print(f"   {'n':>7}{'b — список':>14}{'b — множество':>16}")
for n in (100, 1_000):
    a = [Key(i) for i in range(n)]
    b_list = [Key(i) for i in range(n, 2 * n)]
    b_set = set(b_list)
    c_list = counted(lambda: [x for x in a if x in b_list])
    c_set = counted(lambda: [x for x in a if x in b_set])
    print(f"   {n:>7}{c_list:>14}{c_set:>16}")
print()

# ── 4 ─────────────────────────────────────────────────────────────────────
print("4) sorted(): сколько сравнений")
print(f"   {'n':>7}{'случайные':>11}{'lg(n!)':>9}{'n·log2(n)':>11}{'отсортированные':>17}{'обратные':>10}")
rng = random.Random(42)
for n in (1_000, 10_000, 100_000):
    data = [Key(i) for i in range(n)]
    shuffled = data[:]
    rng.shuffle(shuffled)
    c_rand = counted(lambda: sorted(shuffled))
    c_sorted = counted(lambda: sorted(data))
    c_rev = counted(lambda: sorted(data[::-1]))
    lg_fact = round(math.lgamma(n + 1) / math.log(2))
    print(f"   {n:>7}{c_rand:>11}{lg_fact:>9}{round(n * math.log2(n)):>11}{c_sorted:>17}{c_rev:>10}")
print()

# ── 5 ─────────────────────────────────────────────────────────────────────
print("5) словарь, у всех ключей один и тот же хеш: сравнений на поиск последнего ключа")


class SameHash(Key):
    __slots__ = ()

    def __hash__(self):
        return 1


for n in (10, 100, 1_000):
    normal = {Key(i): i for i in range(n)}
    bad = {SameHash(i): i for i in range(n)}
    c_normal = counted(lambda: normal[Key(n - 1)])
    c_bad = counted(lambda: bad[SameHash(n - 1)])
    print(f"   n = {n:>5}: обычные хеши — {c_normal}, один хеш на всех — {c_bad}")
print()

# ── 6 ─────────────────────────────────────────────────────────────────────
# Добавлено 14.10.2026 по внешнему аудиту (PY-CMP-01): «одно сравнение у
# x in set» в разделе 1 — наблюдение для Key без коллизий, а не свойство
# множества. Здесь то же множество, но у всех элементов один хеш.
print("6) множество, у всех элементов один и тот же хеш: вызовов __eq__")
print(f"   {'n':>7}{'обычные хеши':>14}{'один хеш: поиск':>17}{'один хеш: построение':>22}")
for n in (10, 100, 1_000, 10_000):
    normal = set(Key(i) for i in range(n))
    COUNT["eq"] = 0
    bad = set(SameHash(i) for i in range(n))
    c_build = COUNT["eq"]
    c_normal = counted(lambda: Key(n - 1) in normal)
    c_bad = counted(lambda: SameHash(n - 1) in bad)
    print(f"   {n:>7}{c_normal:>14}{c_bad:>17}{c_build:>22}")


class ZeroHash(Key):
    __slots__ = ()

    def __hash__(self):
        return 0


zero = set(ZeroHash(i) for i in range(100))
print("   тот же опыт с хешем 0 вместо 1, n = 100: поиск —", counted(lambda: ZeroHash(99) in zero))
same_obj = [Key(i) for i in range(100)]
same_set = set(same_obj)
print("   обычные хеши, искомый — тот же объект, а не равный ему: поиск —",
      counted(lambda: same_obj[-1] in same_set))
print()

# ── 7 ─────────────────────────────────────────────────────────────────────
# bisect_left возвращает позицию вставки, а не ответ «нашли»: найден ли
# элемент, решает отдельная проверка границы и равенства после неё.
print("7) bisect: позиция вставки ещё не «нашли» — нужна проверка после неё")
evens = [Key(2 * i) for i in range(100_000)]
for x in (199_998, 77_777, 200_001):
    COUNT["eq"] = COUNT["lt"] = 0
    i = bisect.bisect_left(evens, Key(x))
    c_lt = COUNT["lt"]
    found = i < len(evens) and evens[i] == Key(x)
    print(f"   ищем {x:>7} в 0, 2, 4, …, 199998: позиция {i:>6}, __lt__ — {c_lt},"
          f" __eq__ — {COUNT['eq']}, найден: {found}")