Почему амортизация ломается, когда к старой версии возвращаются

Если ты знаешь, почему амортизированные оценки неверны при повторном доступе к старым версиям и что именно ломается в методах предоплаты и потенциалов, листай до «Теперь сам».

Как думаешь, сколько это стоит

Очередь из двух стеков из раздела 4: кладём в «зад», берём из «переда», а когда перед пуст - переливаем в него перевёрнутый зад. Амортизированно - O(1) на операцию, это доказано методом потенциалов. Теперь стеки персистентные, узлы неизменяемые. Положили 100 элементов, получили версию q. Сто раз подряд извлекаем первый элемент - каждый раз из той же версии q. Сколько это стоит в сумме?

Ответь себе до чтения. «Сто, амортизированно по единице» - неверно: разбор покажет 9900.

На что это похоже

Копилка на крупную покупку. Каждую неделю бросаешь по сотне, и через год хватает на холодильник: дорогая покупка оплачена дешёвыми взносами. Теперь у тебя машина времени: можно вернуться в день, когда копилка полна, и купить холодильник ещё раз. И ещё. Покупок сколько угодно, а копилка одна - деньги в ней были на один холодильник. Амортизация - это копилка; персистентность - машина времени.

Механизм: у версии много будущих

Вспомним, что доказывали методы раздела 3.

Предоплата (метод банкира). Дешёвые операции переплачивают, кредит лежит на элементах; дорогая операция тратит кредит. Требование: каждая монета тратится один раз. В очереди каждый элемент зада несёт монету на будущий переворот. Первое извлечение из q тратит все монеты зада. Второе извлечение из той же q снова переворачивает тот же зад. Монеты - не данные очереди, а запись в доказательстве: сама q не изменилась, но доказательство уже засчитало её монеты первому будущему, и второму платить нечем.

Потенциалы (метод физика). Амортизированная цена = настоящая + изменение потенциала Φ от состояния до операции к состоянию после. Сумма телескопически сокращается - но только если каждая следующая операция начинается с результата предыдущей. Если начать снова с q, потенциал q используется дважды, и сокращения нет.

Окасаки в «Чисто функциональных структурах данных» (глава 5.6) показывает именно этот пример: обычные амортизированные структуры при персистентном использовании теряют свои оценки. Худшие оценки при этом живут: операция, которая в худшем случае O(log n), остаётся такой в любом будущем.

Правило

Амортизированная оценка верна только для цепочки операций, где каждая берёт результат предыдущей. Персистентный доступ даёт версии много будущих, и дорогая операция повторяется в каждом; накопленный кредит и потенциал одни на всех. Персистентной структуре нужны либо оценки в худшем случае, либо особая амортизация, переживающая повторы, - ленивая, со следующего урока.

Разбор: очередь из двух стеков

Стеки - персистентные, из прошлых уроков: узлы в общих списках, версия очереди - пара вершин. Считаем работу - сколько узлов создано, в том числе при перевороте; остальные шаги дешёвые и тут не считаются.

# очередь из двух неизменяемых стеков: перед (откуда берём) и зад (куда
# кладём); узлы стеков - в общих списках, версия - [перед, зад]
znach = []
dalshe = []
rabota = [0]

def polozhit(verh, x):
    znach.append(x)
    dalshe.append(verh)
    rabota[0] = rabota[0] + 1
    return len(znach) - 1

def perevernut(verh):
    out = -1
    while verh != -1:
        out = polozhit(out, znach[verh])
        verh = dalshe[verh]
    return out

def proverit(pered, zad):
    # перед пуст - переливаем зад: дорогой шаг
    if pered == -1:
        return [perevernut(zad), -1]
    return [pered, zad]

def v_konec(q, x):
    return proverit(q[0], polozhit(q[1], x))

def bez_pervogo(q):
    # вызывают только у непустой очереди
    return proverit(dalshe[q[0]], q[1])

n = 100
q = [-1, -1]
for x in range(n):
    q = v_konec(q, x)
print("после", n, "вставок перед - 1 элемент, зад -", n - 1)

rabota[0] = 0
v = q
for i in range(n):                  # обычное использование: по цепочке
    v = bez_pervogo(v)
print("цепочкой", n, "раз bez_pervogo - работа", rabota[0])

rabota[0] = 0
for i in range(n):                  # персистентно: всё время от версии q
    v = bez_pervogo(q)
print("от одной версии", n, "раз - работа", rabota[0])

после 100 вставок перед - 1 элемент, зад - 99
цепочкой 100 раз bez_pervogo - работа 99
от одной версии 100 раз - работа 9900

Первая вставка попала в пустой перед, остальные 99 - в зад. Цепочкой: первое извлечение опустошило перед и перевернуло 99 элементов, следующие 99 извлечений - бесплатные. Итого 99 на 100 операций, меньше единицы на операцию, как и обещала амортизация. От одной версии: каждое из ста извлечений застаёт тот же пустой после извлечения перед и тот же зад из 99 - и переворачивает его заново. 9900 = 100 · 99: каждая операция стоит O(n), суммарно - квадрат.

Разбор: двоичный счётчик

Счётчик из раздела 3: прибавить единицу - перевернуть хвост из единиц и один ноль. Амортизированно - меньше двух переворотов на прибавление. Сравним цепочку и повторные прибавления к одной «неудобной» версии.

def perevernut_bity(x):
    # прибавить 1 к двоичному счётчику: сколько битов перевернётся
    bitov = 1
    while x & 1:
        bitov = bitov + 1
        x = x >> 1
    return bitov

vsego = 0
for x in range(1024):               # счётчик по цепочке: 0, 1, ..., 1023
    vsego = vsego + perevernut_bity(x)
print("1024 прибавления по цепочке:", vsego, "переворотов")

vsego = 0
for i in range(1024):               # 1024 раза от одной версии 1023
    vsego = vsego + perevernut_bity(1023)
print("1024 прибавления к версии 1023:", vsego, "переворотов")

1024 прибавления по цепочке: 2047 переворотов
1024 прибавления к версии 1023: 11264 переворотов

Цепочкой - 2047, ровно 2n − 1. Версия 1023 - это десять единиц подряд, каждое прибавление к ней переворачивает 11 битов, и 1024 повтора стоят 11 264. Здесь проигрыш - логарифм, а не n: самая дорогая операция счётчика стоит log₂ n + 1 переворот, то есть O(log n). Граница правила: персистентность превращает амортизированную оценку в худшую, а не во что-то ещё более страшное. Насколько это плохо, зависит от того, сколько стоит худшая операция структуры.

Что ломается без этого

Отмена действий поверх амортизированной структуры. Редактор хранит состояния документа в очередях-из-двух-стеков, пользователь отменяет и повторяет одну и ту же операцию - и каждый раз платит полный переворот.

Перебор с возвратом. Поиск ветвится от одного состояния: каждая ветка продолжает ту же версию. Если в состоянии лежит структура с отложенным дорогим шагом, его выполнит каждая ветка.

Параллельные читатели одной версии. Несколько потоков получили один снимок и каждый извлекает из него - та же картина, что «от одной версии» в разборе.

Зачем это в работе

Функциональные языки (Haskell, OCaml, Clojure, Scala) держат все коллекции персистентными, поэтому их стандартные очереди и кучи опираются либо на худшие оценки, либо на ленивую амортизацию Окасаки. В императивном коде ловушка та же, только незаметнее: «снимок» объекта с отложенной работой внутри (ленивый кеш, буфер, ожидающий сброса) при ветвлении выполнит эту работу в каждой ветке.

Теперь сам

1. Очередь: перед из 1 элемента, зад из 999. Сколько стоят 50 извлечений цепочкой и 50 извлечений из этой же версии?
2. Какое требование метода предоплаты нарушает повторный доступ к версии?
3. Почему оценка в худшем случае не ломается при персистентности?