"""Чем список отличается от кортежа в памяти — и почему разница не «16 байт».

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

  1. ЗАГОЛОВОК. У кортежа элементы лежат в самом объекте, сразу за заголовком.
     У списка в объекте лежит только указатель на отдельный массив — плюс поле
     `allocated`, которого у кортежа нет вовсе.
  2. ЗАПАС. Список при росте выделяет больше, чем попросили, и этот запас в
     `getsizeof` не виден, потому что живёт в отдельном массиве.

Из-за второго пункта наивное сравнение `getsizeof(list)` и `getsizeof(tuple)`
занижает разницу — иногда до нуля. Поэтому здесь меряется и то и другое:
`getsizeof` (что видит читатель у себя в консоли) и `tracemalloc` на батче
(сколько на самом деле).

ОБЩЕЕ ПРАВИЛО ЗАМЕРОВ: память меряется `tracemalloc` на батче, а не
`sys.getsizeof`. Здесь `getsizeof` используется намеренно и в паре с
`tracemalloc` — потому что предмет замера в том числе и есть расхождение между
ними.
"""
import sys
import tracemalloc

PTR = 8  # sizeof(void *) на 64-битной сборке
EMPTY_LIST = sys.getsizeof([])  # заголовок списка без массива


def rule(title):
    print()
    print(title)
    print("-" * len(title))


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

# ------------------------------------------------------- 1. что видит getsizeof
rule("1. sys.getsizeof: список против кортежа")

print(f"  {'длина':>6} {'список':>9} {'кортеж':>9} {'разница':>9}")
for n in (0, 1, 2, 3, 5, 10, 100, 1000):
    lst = [None] * n
    tpl = (None,) * n
    a, b = sys.getsizeof(lst), sys.getsizeof(tpl)
    print(f"  {n:>6} {a:>9} {b:>9} {a - b:>9}")

print()
print("  Формулы, из которых эти числа складываются:")
print(f"    кортеж:  40 + 8·n   (проверка на n=100: {40 + 8 * 100} против {sys.getsizeof((None,) * 100)})")
print(f"    список:  56 + 8·n   (проверка на n=100: {56 + 8 * 100} против {sys.getsizeof([None] * 100)})")
print("  Разница ровно 16 байт — и это ВСЯ разница, которую показывает getsizeof.")

# --------------------------------------------------------- 2. откуда 16 байт
rule("2. Откуда берутся эти 16 байт")

print("  У обоих объектов есть PyObject_VAR_HEAD: ob_refcnt, ob_type, ob_size —")
print(f"  это {3 * PTR} байта. Дальше они расходятся:")
print()
print("    tuple:  ob_item[] лежит ПРЯМО В ОБЪЕКТЕ, сразу за заголовком.")
print("    list:   ob_item — УКАЗАТЕЛЬ на отдельный массив (8 байт),")
print("            и рядом поле allocated (ещё 8) — сколько места выделено.")
print()
print("  8 + 8 = 16. Поле allocated и есть то, чего у кортежа нет и быть не может:")
print("  кортежу незачем помнить запас, потому что он не растёт.")

# ------------------------------------------------- 3. запас, невидимый глазу
rule("3. Запас списка: то, чего getsizeof не показывает")

lst = []
prev = sys.getsizeof(lst)
print(f"  {'после append':>14} {'getsizeof':>10} {'выделено под':>13}")
print(f"  {'0':>14} {prev:>10} {(prev - 56) // PTR:>13}")
for i in range(24):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev:
        print(f"  {len(lst):>14} {size:>10} {(size - 56) // PTR:>13}")
        prev = size

print()
print("  Список из 17 элементов держит место под 24. Кортеж из 17 держит 17.")
print("  Это и есть цена изменяемости, и в getsizeof она ВИДНА —")
print("  а вот при построении через list(...) с известной длиной запаса нет:")
for n in (1, 3, 17):
    grown = []
    for i in range(n):
        grown.append(i)
    print(f"    n={n:<4} через append: {sys.getsizeof(grown):>5}   "
          f"через list(range(n)): {sys.getsizeof(list(range(n))):>5}   "
          f"литералом: {sys.getsizeof([None] * n):>5}")

# ------------------------------------------- 3b. по какому правилу растёт запас
rule("3b. Формула роста: не удвоение, а +12,5 % и ещё шесть")

# ЗАЧЕМ ОТДЕЛЬНЫЙ РАЗДЕЛ. Раздел 3 показывает лестницу 0, 4, 8, 16, 24 — то
# есть ВЫВОД правила. Само правило из неё не читается, а именно оно и
# опровергает расхожее «список удваивается»: коэффициент здесь 1,125.
# Формула берётся из list_resize и проверяется на замере, а не наоборот.


def resize_formula(newsize: int) -> int:
    """new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3

    Objects/listobject.c, list_resize. Тег v3.13.7.
    """
    if newsize == 0:
        return 0
    return (newsize + (newsize >> 3) + 6) & ~3


def capacity(seq: list) -> int:
    """Сколько указателей помещается в выделенный массив."""
    return (sys.getsizeof(seq) - EMPTY_LIST) // PTR


print("  Формула из list_resize: newsize + newsize//8 + 6, округлённое вниз")
print("  до кратного четырём. Проверяем её на первых двенадцати ступенях:")
print()
print(f"    {'длина':>7} {'замер':>7} {'формула':>9}")
lst = []
prev = -1
steps = 0
n = 0
while steps < 12:
    lst.append(n)
    n += 1
    cap = capacity(lst)
    if cap != prev:
        f = resize_formula(len(lst))
        mark = "" if cap == f else "   <-- РАСХОЖДЕНИЕ"
        print(f"    {len(lst):>7} {cap:>7} {f:>9}{mark}")
        prev = cap
        steps += 1

print()
print("  ЧТО ЗДЕСЬ ЛЕГКО ПРОЧЕСТЬ НЕВЕРНО. Формула считает запас от ДЛИНЫ, а не")
print("  от прошлого запаса. Поэтому «плюс восьмая часть» и отношение соседних")
print("  запасов — не одно и то же число: на коротком списке правит слагаемое")
print("  +6, и запас поначалу удваивается. Отношение видно только на замере:")
print()
print(f"    {'длина':>8} {'запас':>8} {'к прошлому запасу':>19}")
lst2: list[int] = []
prev2 = -1
ladder = []
for i in range(300000):
    lst2.append(i)
    c = capacity(lst2)
    if c != prev2:
        ladder.append((len(lst2), c))
        prev2 = c
for k in range(1, len(ladder)):
    n2, c2 = ladder[k]
    if k <= 6 or n2 in (129, 673, 2885, 11977, 49365) or k == len(ladder) - 1:
        print(f"    {n2:>8} {c2:>8} {c2 / ladder[k - 1][1]:>19.3f}")
print()
print("  То есть 1,125 — это ПРЕДЕЛ, к которому отношение сходится на длинных")
print("  списках, а не множитель на каждом шаге. Удвоение (C++ vector, срез в Go")
print("  до 256 элементов) — другая стратегия, и разницу видно на счёте:")
print()


def realloc_count(target: int, grow) -> int:
    cap_, steps_ = 0, 0
    for n2 in range(1, target + 1):
        if n2 > cap_:
            cap_ = grow(cap_, n2)
            steps_ += 1
    return steps_, cap_


TARGET = 300000
py_steps, py_cap = realloc_count(TARGET, lambda c, n2: resize_formula(n2))
x2_steps, x2_cap = realloc_count(TARGET, lambda c, n2: max(4, c * 2))
print(f"    до {TARGET} элементов, перевыделений: CPython {py_steps}, удвоением {x2_steps}")
print(f"    итоговый запас:                     CPython {py_cap}, удвоением {x2_cap}")
print(f"    лишнего сверх длины:                CPython {(py_cap - TARGET) / TARGET:.1%}, "
      f"удвоением {(x2_cap - TARGET) / TARGET:.1%}")
print()
print("  Вот и весь размен: вчетверо больше перевыделений ради того, чтобы")
print("  готовый список не держал лишнего на три четверти своей длины.")

print()
print("  Большой скачок за один раз запаса НЕ получает — в list_resize для")
print("  этого стоит отдельная ветка («Do not overallocate if the new size is")
print("  closer to overallocated size than to the old size»):")
at_once = []
at_once.extend(range(1000))
one_by_one = []
for i in range(1000):
    one_by_one.append(i)
print(f"    extend(range(1000)) за раз: выделено под {capacity(at_once)}")
print(f"    1000 раз append:           выделено под {capacity(one_by_one)}")

print()
print("  И обратный ход: список не отдаёт память, пока длина не упадёт НИЖЕ")
print("  половины запаса. В list_resize это условие записано так:")
print("      if (allocated >= newsize && newsize >= (allocated >> 1))")
shrink = list(range(1000))
print(f"    list(range(1000)):     запас {capacity(shrink)}, длина {len(shrink)}")
for _ in range(400):
    shrink.pop()
print(f"    после 400 pop:         запас {capacity(shrink)}, длина {len(shrink)}")
for _ in range(200):
    shrink.pop()
print(f"    после ещё 200 pop:     запас {capacity(shrink)}, длина {len(shrink)}")
print()
print("  Сжатие срабатывает на длине 499 — первой, что оказалась меньше")
print(f"  половины тысячи, — и даёт ровно formula(499) = {resize_formula(499)}.")

# ----------------------------------------------------- 4. tracemalloc на батче
rule("4. tracemalloc на батче — и сходится ли он с getsizeof")

# ЗАЧЕМ ЭТОТ РАЗДЕЛ ВЫГЛЯДИТ ИМЕННО ТАК. Общее правило замеров — «память
# меряется tracemalloc на батче, а не sys.getsizeof» — появилось из случая, где
# getsizeof даёт ответ с обратным знаком (__slots__). Соблазн распространить
# его на всё велик, и здесь он проверяется, а не принимается: для списка и
# кортежа из общих элементов два инструмента сходятся ТОЧНО, если вычесть
# список, который держит батч.
#
# Без контрольного замера этого не увидеть: сам keep стоит ~8,5 байта на
# объект (указатель плюс собственный запас), и без поправки кажется, будто
# tracemalloc «нашёл» лишнее.

N = 10_000
LEN = 10


def measure(make):
    tracemalloc.start()
    before = tracemalloc.get_traced_memory()[0]
    keep = [make() for _ in range(N)]
    after = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    del keep
    return (after - before) / N


# Контроль: во что обходится сам батч, если объекты бесплатны.
# None — синглтон, память под него не выделяется.
overhead = measure(lambda: None)

rows = [
    ("список через включение", lambda: [i for i in range(LEN)], [i for i in range(LEN)]),
    ("список через list(range)", lambda: list(range(LEN)), list(range(LEN))),
    ("кортеж", lambda: tuple(range(LEN)), tuple(range(LEN))),
]

print(f"  {N:,} объектов по {LEN} элементов".replace(",", " "))
print(f"  Список, который держит батч, стоит {overhead:.2f} байта на объект — он вычтен.")
print()
print(f"    {'что мерим':<26} {'tracemalloc':>12} {'getsizeof':>10} {'разница':>9}")
for label, make, sample in rows:
    traced = measure(make) - overhead
    sized = sys.getsizeof(sample)
    print(f"    {label:<26} {traced:12.1f} {sized:10} {traced - sized:9.1f}")

print()
print("  Два инструмента сходятся. Для этих объектов getsizeof не занижает")
print("  ничего: массив списка вместе с запасом он считает целиком.")
print()
print("  Занижает он другое — то, на что объект ССЫЛАЕТСЯ. Здесь этого не")
print("  видно, потому что элементы общие: малые целые числа — синглтоны, и")
print("  списку с кортежем принадлежат не они, а только указатели на них.")
print("  Проверка: батч из списков с непустыми строками, которые создаются")
print("  заново каждый раз, — вот там расхождение и появляется.")

fresh = measure(lambda: [f"s{i}" * 3 for i in range(LEN)]) - overhead
fresh_sample = [f"s{i}" * 3 for i in range(LEN)]
print()
print(f"    {'список свежих строк':<26} {fresh:12.1f} {sys.getsizeof(fresh_sample):10} "
      f"{fresh - sys.getsizeof(fresh_sample):9.1f}")
print("    ^ вот здесь getsizeof и занижает: строки в него не входят.")