"""Раскладка словаря, пороги роста и то, что делают с ней удаления.

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

Здесь пять блоков, и каждый отвечает на один вопрос:

  1. КАК УСТРОЕНА ТАБЛИЦА — во что обходится разреженный `dk_indices` против
     наивной таблицы записей и откуда берутся «на 20–25 % меньше памяти».
  2. ШИРИНА ИНДЕКСА — сколько байт занимает один слот `dk_indices`. Она
     зависит от `dk_size`, и наивный расчёт «по два байта всегда» даёт
     неверные числа на больших таблицах.
  3. РОСТ — где именно словарь пересобирается и во сколько раз.
  4. УДАЛЕНИЯ — что размер не возвращается, и что вернуть его можно только
     пересборкой.
  5. РЕЖИМ СТРОКОВЫХ КЛЮЧЕЙ — экономия из 3.11, когда все ключи строки.

ЧЕГО ЗДЕСЬ НЕТ И ПОЧЕМУ. Времени. Все утверждения статьи про словарь — про
раскладку и байты, а не про наносекунды, и мерить время значило бы добавить
числа, которые ничего в статье не подпирают. Общее правило замеров про
несравнимость версий по времени поэтому здесь не задействовано: сравнивать
нечего.

ПОЧЕМУ ЭТОТ СКРИПТ ПОЯВИЛСЯ ПОЗЖЕ СТАТЬИ. Числа статьи считались вручную и
скрипта не имели вовсе — то есть перезапустить их было нечем. Это ровно то,
что запрещает главное правило замеров: числа в статьях берутся из скриптов,
а не из головы.
"""
import sys
import sysconfig

PTR = sysconfig.get_config_var("SIZEOF_VOID_P") or 8


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


# ---------------------------------------------------------------- 1. раскладка
rule("1. Разреженный dk_indices против наивной таблицы записей")

# Запись общего вида PyDictKeyEntry — три указателя: hash, key, value.
ENTRY_GENERAL = 3 * PTR
# Запись строкового режима PyDictUnicodeEntry — два: key, value. Хеш не
# хранится, он уже закеширован в самом строковом объекте.
ENTRY_UNICODE = 2 * PTR


def index_width(dk_size):
    """Сколько байт занимает один слот dk_indices при данном dk_size.

    Ширина растёт вместе с таблицей: в слот надо уместить номер записи.
    Правило записано в Objects/dictobject.c рядом с DK_ENTRIES.
    """
    if dk_size <= 0xFF:
        return 1
    if dk_size <= 0xFFFF:
        return 2
    if dk_size <= 0xFFFFFFFF:
        return 4
    return 8


def usable_fraction(dk_size):
    """USABLE_FRACTION из Objects/dictobject.c: (n << 1) / 3."""
    return (dk_size << 1) // 3


# Лестница целиком: экономия не постоянна, она ступенчато падает вместе с
# шириной слота dk_indices. Три точки этого не показывают — нужна вся линия,
# иначе «на 20–25 % меньше памяти» читается как свойство словаря вообще.
for dk_size in (8, 32, 128, 256, 1024, 4096, 16384, 65536, 262144, 1048576):
    usable = usable_fraction(dk_size)
    width = index_width(dk_size)
    naive = dk_size * ENTRY_GENERAL          # запись в каждом слоте
    compact = dk_size * width + usable * ENTRY_GENERAL
    saved = (naive - compact) / naive * 100
    print(
        f"  dk_size={dk_size:>6}  полезных записей={usable:>6}  "
        f"индекс={width} Б  наивно={naive:>9} Б  компактно={compact:>9} Б  "
        f"экономия {saved:.1f} %"
    )

print("  (ENTRY_GENERAL =", ENTRY_GENERAL, "Б, ENTRY_UNICODE =", ENTRY_UNICODE, "Б)")

# Формулу выше нельзя оставлять на веру: она вся держится на index_width, а
# именно там легко ошибиться на порядок — ширина индекса растёт ступенями, и
# «два байта всегда» даёт правдоподобное, но неверное число на больших
# таблицах. Поэтому она сверяется с тем, что говорит сам интерпретатор.
rule("1b. Проверка формулы против sys.getsizeof")

DICT_HEADER = 48        # PyDictObject
KEYS_HEADER = 48        # PyDictKeysObject


def predict(dk_size, entry_size):
    return DICT_HEADER + KEYS_HEADER + dk_size * index_width(dk_size) + usable_fraction(dk_size) * entry_size


print("  ключи целые (общий режим):")
ok = True
for n in (5, 10, 21, 42, 85, 170):
    d = {i: i for i in range(n)}
    dk_size = 8
    while usable_fraction(dk_size) < n:
        dk_size <<= 1
    got = sys.getsizeof(d)
    want = predict(dk_size, ENTRY_GENERAL)
    mark = "==" if got == want else "!="
    ok &= got == want
    print(f"    {n:>4} ключей  dk_size={dk_size:>5}  getsizeof={got:>7}  формула={want:>7}  {mark}")
print("  формула совпадает с интерпретатором:", ok)

# ------------------------------------------------------------------- 2. рост
rule("2. Где словарь пересобирается")

d = {}
prev = sys.getsizeof(d)
changes = []
for i in range(200):
    d[i] = i
    now = sys.getsizeof(d)
    if now != prev:
        changes.append((len(d), prev, now))
        prev = now
print("  вставок -> размер до и после пересборки:")
for n, before, after in changes:
    print(f"    на {n:>4}-й вставке  {before:>7} -> {after:>7} Б")

# --------------------------------------------------------------- 3. удаления
rule("3. Удаления ёмкость не возвращают")

big = {i: i for i in range(1000)}
size_full = sys.getsizeof(big)
for i in range(999):
    del big[i]
size_after_del = sys.getsizeof(big)
rebuilt = dict(big)
size_rebuilt = sys.getsizeof(rebuilt)

print(f"  1000 ключей                     {size_full:>7} Б")
print(f"  остался 1 ключ, размер          {size_after_del:>7} Б   <- не изменился")
print(f"  после dict(d)                   {size_rebuilt:>7} Б")

empty = {i: i for i in range(1000)}
empty.clear()
print(f"  после clear() на таком же       {sys.getsizeof(empty):>7} Б")

# ---------------------------------------------------- 4. режим строковых ключей
rule("4. Режим строковых ключей (3.11+)")

str_keys = dict.fromkeys("abcdefg")
mixed = dict.fromkeys("abcdefg")
mixed[1] = None
print(f"  dict.fromkeys('abcdefg')                 {sys.getsizeof(str_keys):>5} Б")
print(f"  то же плюс один нестроковый ключ         {sys.getsizeof(mixed):>5} Б")

# -------------------------------------------------------------- 5. про хеши
rule("5. Хеш")

print("  sys.hash_info.algorithm :", sys.hash_info.algorithm)
print("  PYTHONHASHSEED влияет на str/bytes; для int hash(n) == n при малых n:")
print("    hash(1), hash(2), hash(-1) =", hash(1), hash(2), hash(-1))
print("  PY", sys.version.split()[0])