"""Что стоит дорого у списка и почему — время операций в начале и в конце.

ЗАЧЕМ ЭТОТ СКРИПТ. «`insert(0)` медленный» знают все, «`append` быстрый» —
тоже. Здесь проверяется не это, а три вещи, которые из общего знания не
следуют:

1. Насколько именно медленный. Не «в разы», а как растёт с длиной: удвоение
   длины даёт вчетверо больше времени — это и есть предъявленная квадратичность,
   а не её пересказ.
2. Что `del L[0]` и `L.pop(0)` — РАЗНЫЕ по цене операции, хотя делают одно и
   то же. Разница появилась в 3.13 вместе с изменением в `list_ass_item`
   (см. `shrink.py`, там же расходится и ёмкость).
3. Чего это стоит по сравнению с `collections.deque`, у которого обе стороны
   дешёвые.

ПРАВИЛО ЗАМЕРА. Всё меряется ВНУТРИ ОДНОГО запуска ОДНОГО интерпретатора, и
сравниваются только числа из одного прогона (bench/README.md). Между версиями
время не сравнивается вовсе: у сборок песочницы разные компиляторы и разные
флаги, и разделить «стал быстрее язык» и «стала быстрее сборка» нечем. Поэтому
запись прогона здесь одна, и суффикса версии у неё нет.

МЕТОДИКА. `timeit`, лучшее из семи раундов. Берётся лучшее, а не среднее: шум
на этой машине односторонний — соседний процесс может отнять время, но не может
его добавить.

ПОЧЕМУ ОПЕРАЦИЯ МЕРЯЕТСЯ ПАРТИЕЙ. Одно `insert(0)` в список из десяти тысяч
стоит микросекунды, одно `append` — наносекунды. Один цикл `timeit` на обе не
натягивается: у первой он утонет в шуме, у второй сам цикл будет дороже
операции. Поэтому меряется «опустошить список целиком» и «наполнить список
целиком», а цена одной операции получается делением. Числа в колонке «нс на
операцию» — амортизированные, и это сказано в заголовке колонки.

ЗАПУСК:

    python3.13 bench/lists/ops.py
"""

import platform
import sys
import timeit

ROUNDS = 7
N = 10_000


def best(stmt: str, setup: str, number: int) -> float:
    """Секунды на один прогон stmt. Лучшее из ROUNDS раундов."""
    timer = timeit.Timer(stmt, setup)
    return min(timer.repeat(ROUNDS, number)) / number


def head(n: int, title: str) -> None:
    line = f"{n}. {title}"
    print(f"\n{line}\n{'-' * len(line)}")


def main() -> None:
    print(f"Python {platform.python_version()}")
    print(f"Сборка: {sys.version.split('[')[-1].rstrip('] ')}")
    print(f"\nВсе числа сняты одним запуском одного интерпретатора: сравнивать")
    print("их можно только между собой, с другими версиями — нельзя.")
    print(f"Длина списка в замерах: {N}. Лучшее из {ROUNDS} раундов.")

    head(1, "НАПОЛНИТЬ СПИСОК: С КОНЦА И С НАЧАЛА")
    fill = [
        ("L.append(i)", "L=[]\nfor i in r: L.append(i)", f"r=range({N})", 100),
        ("L.insert(0, i)", "L=[]\nfor i in r: L.insert(0,i)", f"r=range({N})", 10),
        ("d.append(i)", "d=deque()\nfor i in r: d.append(i)",
         f"from collections import deque\nr=range({N})", 100),
        ("d.appendleft(i)", "d=deque()\nfor i in r: d.appendleft(i)",
         f"from collections import deque\nr=range({N})", 100),
    ]
    print(f"  операция, повторённая {N} раз       всего, мкс   нс на операцию")
    for name, stmt, setup, number in fill:
        sec = best(stmt, setup, number)
        print(f"  {name:<32s} {sec * 1e6:>10.0f} {sec / N * 1e9:>16.1f}")
    print("\n  Работа одна и та же — добавить десять тысяч элементов. Различает")
    print("  строки только то, с какого края это делают и какая это структура.")

    head(2, "ОПУСТОШИТЬ СПИСОК: С КОНЦА, С НАЧАЛА, ДВУМЯ СПОСОБАМИ")
    drain = [
        ("L.pop()", "L=src.copy()\nwhile L: L.pop()", 50),
        ("del L[-1]", "L=src.copy()\nwhile L: del L[-1]", 50),
        ("L.pop(0)", "L=src.copy()\nwhile L: L.pop(0)", 10),
        ("del L[0]", "L=src.copy()\nwhile L: del L[0]", 10),
        ("d.pop()", "d=deque(src)\nwhile d: d.pop()", 50),
        ("d.popleft()", "d=deque(src)\nwhile d: d.popleft()", 50),
    ]
    setup = f"from collections import deque\nsrc=list(range({N}))"
    print(f"  операция, повторённая {N} раз       всего, мкс   нс на операцию")
    got = {}
    for name, stmt, number in drain:
        sec = best(stmt, setup, number)
        got[name] = sec
        print(f"  {name:<32s} {sec * 1e6:>10.0f} {sec / N * 1e9:>16.1f}")
    ratio = got["L.pop(0)"] / got["del L[0]"]
    print(f"\n  L.pop(0) / del L[0] = ×{ratio:.1f} — одна и та же работа по смыслу,")
    print("  разные пути в реализации. Что при этом происходит с ёмкостью — в shrink.py.")

    head(3, "КВАДРАТИЧНОСТЬ, ПРЕДЪЯВЛЕННАЯ, А НЕ НАЗВАННАЯ")
    print("  наполнение через insert(0): длина удваивается — время вчетверо")
    print("  длина    всего, мкс   нс на операцию   отношение к предыдущей строке")
    prev = None
    for n in (2_500, 5_000, 10_000, 20_000):
        sec = best("L=[]\nfor i in r: L.insert(0,i)", f"r=range({n})", 10)
        rel = "—" if prev is None else f"×{sec / prev:.2f}"
        print(f"  {n:>6d} {sec * 1e6:>12.0f} {sec / n * 1e9:>16.1f}   {rel:>10s}")
        prev = sec
    print("\n  Для сравнения — та же таблица для append, где отношение около двух:")
    print("  длина    всего, мкс   нс на операцию   отношение к предыдущей строке")
    prev = None
    for n in (2_500, 5_000, 10_000, 20_000):
        sec = best("L=[]\nfor i in r: L.append(i)", f"r=range({n})", 50)
        rel = "—" if prev is None else f"×{sec / prev:.2f}"
        print(f"  {n:>6d} {sec * 1e6:>12.0f} {sec / n * 1e9:>16.1f}   {rel:>10s}")
        prev = sec

    head(4, "ЧЕМ ЗА ЭТО ПЛАТИТ deque: ЦЕНА ИНДЕКСА")
    print("  Обе стороны у deque дёшевы — но индекс перестал быть постоянным.")
    setup = "from collections import deque\nL=list(range(100000))\nd=deque(L)"
    print("  выражение, повторённое 1000 раз в витке     нс на операцию")
    for expr in ("L[0]", "L[50000]", "L[99999]", "d[0]", "d[50000]", "d[99999]"):
        stmt = "; ".join([expr] * 1000)
        sec = best(stmt, setup, 200)
        print(f"  {expr:<42s} {sec / 1000 * 1e9:>10.1f}")
    print("\n  У списка три числа почти совпали, у deque середина дороже краёв в сотни раз:")
    print("  это и есть разница между массивом указателей и связкой блоков.")


main()