Конспект: персистентные структуры и ленивая амортизация

Понятия

Эфемерная структура - изменение уничтожает прошлое состояние. Персистентная - операция возвращает новую версию, старые доступны. Частичная - менять только последнюю версию, полная - любую, слияемая - ещё и соединять версии.

Общие части - узлы, которые делят несколько версий; возможны, только если узлы неизменяемы.

Копирование пути - правка создаёт новые копии узлов на пути от корня до места правки.

Обещание - отложенное вычисление; вызов по необходимости - вычислить при первой нужде и запомнить.

Учёт долгом - обещание создаёт долг, операции его гасят, вычислять можно только оплаченное.

Что унести

ПЕРСИСТЕНТНЫЙ СТЕК
узел [значение, следующий], версия = номер вершины
положить - 1 новый узел; снять - 0 новых; ветки - бесплатно
2000 операций с ветвлением: 1416 узлов против 55 421 при копиях
history.append(obj) хранит ссылку, а не снимок

КОПИРОВАНИЕ ПУТИ
вставить(v, k): копия v с новым ребёнком на стороне k, другой - старый
цена = длина пути: O(log n) с балансом, O(n) в цепочке
300 случайных вставок со всеми версиями: 2832 узла против 45 150
150 вставок по возрастанию: 11 325 - как копирование целиком
массив 2ᵏ: дерево по битам индекса, запись - k + 1 узлов
1024 нуля - 11 узлов (одинаковые половины - один узел)
Clojure/Scala: ветвление 32, миллион - глубина 4; git, LMDB, btrfs

АМОРТИЗАЦИЯ ПРИ ПОВТОРНОМ ДОСТУПЕ
оценки раздела 3 верны только для цепочки операций
предоплата: монета тратится один раз - у версии много будущих
потенциалы: каждое состояние используется один раз - нарушено
очередь из 2 стеков, 100 вставок: цепочкой 99, от одной версии 9900
счётчик 1023: 1024 прибавления от версии - 11 264 (цепочкой 2047)
худшие оценки при персистентности не ломаются

ОЧЕРЕДЬ БАНКИРА (ОКАСАКИ)
инвариант: |зад| ≤ |перед|
нарушен -> перед = обещание(перед ++ перевернуть(зад)), зад пуст
склейка ++ - по элементу; переворот зада - когда старый перед выбран
100 извлечений от одной версии: с запоминанием 6, без - 600
ветки перед переворотом: короткие - 1,3 на операцию, длинные - 1,09
худший O(1): расписание - вычислять обещание по кусочку (глава 7)

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

История из ссылок на изменяемый объект. Все «снимки» показывают последнее состояние.

Глубокая копия на каждую версию. Работает, но O(n) памяти и времени на версию - квадрат.

Правка общего узла на месте. Изменение всплывает во всех версиях, которые его делят.

Персистентное дерево без баланса. Отсортированный поток ключей - и копирование пути равно копии целиком.

Амортизированная структура под отменой и перебором с возвратом. Каждая ветка повторяет дорогой шаг.

Ленивость без запоминания. Обещание вычисляется при каждом обращении - атака повтором работает.

• Очередь реального времени (f,r,s): |s|=|f|-|r|, execute вынуждает шаг расписания; при пустом s запускается ленивый rotate. Мемоизация общая у версий, O(1) относится к модели структуры, не паузам runtime.

• Скошенный список: веса 2^(i+1)-1, равны могут быть только два первых дерева. Cons объединяет максимум два дерева, uncons раскрывает двух детей: O(1); индекс и изменение по пути O(log n), старые версии разделяют вершины.