"""Цена двух операций, по которым выбирают коллекцию: поиск `in` и удаление из начала.

ЗАЧЕМ. «Проверку вхождения делай по множеству» и «очередь — не список» —
правила, которые на собеседовании ждут услышать. Оба держатся на асимптотике,
а асимптотика ничего не говорит о маленьких размерах. Здесь видно и то и
другое: где разница огромна и где её нет вовсе.

ЧТО МЕРЯЕТСЯ (нс на одну операцию):

  `x in коллекция` — искомый элемент последний в списке (худший случай для
  списка), размеры 10, 1 000 и 100 000; список, кортеж, множество, ключи
  словаря.

  удаление из начала — `lst.pop(0)` против `deque.popleft()` и против
  `lst.pop()` с конца, на коллекции из 100 000 элементов: каждая операция
  уменьшает коллекцию на один, поэтому меряется проход до половины длины.

КАК. Формы меряются вперемежку, ROUNDS кругов; печатаются минимум, медиана
и максимум по кругам — чтобы был виден разброс, а не один удачный прогон.
Время — вместе с циклом; пустой цикл того же размера напечатан отдельно.

Запускать: python3.13 / 3.14. Числа — этой машины; отношения — наблюдение
этой конфигурации, на другой машине и версии их надо мерить заново.
"""
import statistics
import sys
import time
from collections import deque

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

ROUNDS = 9


def clock(fn):
    """Время вызова. Если функция сама вернула время — берём его: так из
    замера исключается подготовка (создание коллекции)."""
    t0 = time.perf_counter()
    inner = fn()
    total = time.perf_counter() - t0
    return inner if inner is not None else total


def report(title, forms, per):
    samples = {name: [] for name, _ in forms}
    for _ in range(ROUNDS):
        for name, fn in forms:
            samples[name].append(clock(fn) / per * 1e9)
    print(title)
    print(f"   {'форма':<26}{'мин':>10}{'медиана':>10}{'макс':>10}")
    med = {}
    for name, _ in forms:
        xs = samples[name]
        med[name] = statistics.median(xs)
        print(f"   {name:<26}{min(xs):>10.1f}{med[name]:>10.1f}{max(xs):>10.1f}")
    return med


# ── 1: x in коллекция ────────────────────────────────────────────────────
print("1) x in коллекция: искомый элемент последний, нс на проверку")
REPS = 20_000
for size in (10, 1_000, 100_000):
    items = list(range(size))
    target = size - 1
    lst, tup, st, dct = list(items), tuple(items), set(items), dict.fromkeys(items)
    reps = REPS if size <= 1_000 else 200

    def mk(container, reps=reps, target=target):
        def run():
            for _ in range(reps):
                target in container
        return run

    def empty(reps=reps):
        for _ in range(reps):
            pass

    forms = [("пустой цикл", empty), ("list", mk(lst)), ("tuple", mk(tup)), ("set", mk(st)), ("dict (ключи)", mk(dct))]
    if size == 10:
        # На маленьком списке исход зависит от того, где элемент: первый
        # находится сразу, без хеширования.
        forms.insert(2, ("list, элемент первый", mk(lst, target=0)))
    med = report(f"   размер {size}:", forms, reps)
    print(f"   list / set по медианам: {med['list'] / med['set']:.1f}")
    print()

# ── 2: удаление из начала ────────────────────────────────────────────────
print("2) удаление из начала: 50 000 удалений из коллекции в 100 000, нс на удаление")
N = 100_000
K = 50_000


# Коллекция создаётся до засечки времени: меряется только цикл удалений.
def pop_front_list():
    lst = list(range(N))
    t0 = time.perf_counter()
    for _ in range(K):
        lst.pop(0)
    return time.perf_counter() - t0


def popleft_deque():
    dq = deque(range(N))
    t0 = time.perf_counter()
    for _ in range(K):
        dq.popleft()
    return time.perf_counter() - t0


def pop_back_list():
    lst = list(range(N))
    t0 = time.perf_counter()
    for _ in range(K):
        lst.pop()
    return time.perf_counter() - t0


med = report(
    "   (создание коллекции в замер не входит)",
    [("list.pop(0)", pop_front_list), ("deque.popleft()", popleft_deque), ("list.pop() с конца", pop_back_list)],
    K,
)
print(f"   list.pop(0) / deque.popleft() по медианам: {med['list.pop(0)'] / med['deque.popleft()']:.0f}")