Конспект раздела: структуры данных на практике

Одна мысль на весь раздел

Асимптотика говорит, кто победит на больших входах, а секундомер - сколько это стоит на этой машине. Между ними три вещи, которых модель RAM не видит: константы (как устроен контейнер, сколько стоит вызов и сравнение), память (где лежат данные, в кеше или нет) и история (к какой версии структуры вернулись и кто ещё её трогает). Каждая глава раздела - про одну из них.

Дерево решений

код медленнее, чем обещает асимптотика?
├── контейнер не под операцию
│   ├── вставка в начало, pop(0)       -> deque
│   ├── минимум из меняющегося набора  -> heapq
│   ├── поиск в отсортированном        -> bisect, но не insort в цикле
│   └── x in список в цикле            -> set / dict
├── данные не помещаются в кеш
│   ├── обход вразброс                 -> массив, порядок по адресам
│   └── миллионы объектов-чисел        -> array / NumPy
├── сравниваешь две реализации
│   ├── один прогон или среднее        -> прогрев, повторы, [q1, q3]
│   ├── хочешь знать рост              -> опыт с удвоением
│   └── нужен порог гибрида            -> точка пересечения замером
├── нужны старые версии
│   ├── стек                           -> неизменяемые узлы, бесплатно
│   ├── дерево, массив                 -> копирование пути + баланс
│   └── амортизированная структура     -> ленивость + запоминание
└── много потоков без замков
    ├── одна ячейка                    -> цикл CAS, стек Трайбера
    ├── два конца                      -> Майкл - Скотт, помощь
    ├── узлы переиспользуются          -> метка, LL/SC, hazard ptr
    └── только чтения и записи         -> нельзя: консенсус 1

Как части связаны

что модель не видит	где появилось	чем это меряют или лечат
рост ёмкости, пустышки	`list`, `dict`, `set`	`sys.getsizeof`, устройство из исходников
константы гибрида	Timsort, introsort, вставки	счёт сравнений, точка пересечения
порядок слияний	powersort	цена = сумма длин, граница `n·H`
предвыборка, лестница кешей	обход вразброс	замер по размерам данных
шум машины	любой замер	прогрев, медиана, квартили, повторная серия
повторный доступ к версии	амортизация	ленивость, учёт долгом
чужой поток между чтением и CAS	стек, очередь	CAS, помощь, метка версии

Одна идея проходит через весь раздел в разных одеждах: посмотри на вход, прежде чем работать. Timsort ищет серии, галоп ждёт улики, powersort смотрит на позицию границы, introsort - на глубину, честный замер - на разброс, ленивая очередь - на то, нужен ли уже результат.

Числа раздела, которые стоит помнить

list: ёмкость ~ n + n//8 + 6; 10⁶ append - 86 переездов, 8,45 копии
dict: пороги 6, 11, 22, 43, 86; k << 16: 45 150 проб, с perturb 1249
set: 10 ячеек подряд; 2,98 пробы, но 1,55 строки кеша против 2,5
insort 200 000 раз - 4,3 с; heappush - 20 мс
sorted 10⁵: готовые - 99 999 сравнений; случайные - на 0,8% выше log₂ n!
противник Макилроя, n = 200: 10 135 сравнений; с защитой глубины - 4664
sum вразброс на 125 МБ - в 6 раз медленнее, чем подряд; на 31 КБ - так же
опыт с удвоением: dict O(n) показал 1,1-1,6 - кеш
вставки против слияния: модель - граница 32-64, Python - 64-128
300 версий дерева: 2832 узла против 45 150 копированием
очередь из двух стеков, от одной версии 100 раз: 9900; банкира - 6
ABA: 121 состояние, 1 испорченное; с метками - 0

Границы, общие для всех результатов

Числа CPython сняты на 3.12 (так работает сайт): с 3.13 у Timsort убывающие серии нестрогие, и в других версиях отдельные числа могут сдвинуться. Замеры - на одной машине (Core i5-3350P), у другой ступени кеша на других размерах. Модели перебора чередований верны в своей модели памяти: последовательно согласованной, без переупорядочения записей процессором.

Ловушки джокера

Очередь на list и insort в цикле. Асимптотика поиска не равна асимптотике вставки.

Удалённый ключ как пустая ячейка. Поиск обрывается и теряет чужие ключи.

NaN в сортировке. Результат не отсортирован, ошибки нет.

Своя быстрая сортировка в сервисе. Противник строит вход-убийцу один раз.

Бенчмарк на данных, которые помещаются в кеш. Разбросанная структура выглядит не хуже компактной.

Один прогон или средние. Выбросы и прогрев решают за тебя.

История из ссылок и амортизация под отменой. Старое состояние либо потеряно, либо пересчитывается в каждой ветке.

CAS без защиты от ABA при переиспользовании узлов. Порча, которую не ловят случайные тесты.

Сохранённая версия и согласованная публикация

Задача	Инструмент	Условие или граница
Очередь реального времени	Расписание и мемоизация	Распределяй работу по операциям; учитывай разделение версий.
Доступ в функциональном списке	Скошенное двоичное представление	Сохраняй каноническое правило весов.
Разгрузка конкурентного узла	Элиминация и счётные сети	Подтверждение пары атомарно; ступенька в покое не означает линеаризуемость.
Согласованная публикация	STM/HTM	Сохраняй зависимости первых чтений; повторы и внешние эффекты требуют протокола.

Проверь, что можешь объяснить

Почему рост ёмкости списка в 9/8 раза не ломает амортизированное O(1) у append?
Почему удалённый ключ в dict оставляет пустышку, а не пустую ячейку?
Почему {1, 1.0, True} - одно число, а два разных объекта NaN - два?
Зачем Timsort добивает короткие серии до minrun и почему minrun не всегда 32?
Почему галоп включается только после семи побед подряд?
Почему у powersort есть гарантия, а у старого правила стека - нет, хотя на некоторых входах старое лучше?
Как противник Макилроя ломает медиану трёх и что делает introsort?
Почему сумма по перемешанному списку медленнее только на больших данных?
Какое число записать в отчёт по замеру и когда вывод - «не различить»?
Почему построение словаря дало показатель роста больше единицы?
Почему очередь из двух стеков теряет амортизацию при персистентности и как её возвращает запоминание?
Почему неблокирующую очередь нельзя построить из чтений и записей, а из CAS - можно?