chapter07.tex

\chapter{Избавление от амортизации}
\label{ch:7}

Чаще всего нас не интересует, являются ли ограничения, соблюдаемые
структурой, жёсткими или амортизированными; основные критерии для
выбора одной структуры данных вместо другой~--- общая эффективность и
простота реализации (возможно, ещё наличие исходного кода). Однако в
некоторых прикладных областях оказывается важно ограничить время
выполнения отдельных операций, а не их последовательностей. В
этих случаях структура с жёсткими ограничениями часто предпочтительнее
структуры с амортизированными характеристиками, даже если
амортизированная структура в целом проще и быстрее. Раман
\cite{Raman1992} перечисляет несколько таких прикладных областей, в
том числе
\begin{itemize}
\item \textbf{Системы реального времени.} В системах реального времени
  предсказуемость важнее голой скорости \cite{Stankovic1988}. Если
  из-за дорогой операции система пропустит жёсткий
  предельный срок, неважно будет, сколько дешёвых операций завершилось
  раньше назначенного времени.
\item \textbf{Параллельные системы.} Если один процессор в синхронной
  системе выполняет дорогую операцию в то время, как остальные
  выполняют дешёвые, то остальным процессорам придётся ждать, пока
  закончит работу самый медленный.
\item \textbf{Диалоговые системы.} Диалоговые системы подобны системам
  реального времени~--- для пользователей предсказуемость часто
  важнее, чем чистая скорость \cite{Butler1983}. Например,
  пользователи могут предпочесть 100 ответов с задержкой 1 секунда
  варианту с 99 ответами при задержке 0.25 секунд и одним ответом с
  задержкой 25 секунд, даже при том, что второй из этих сценариев
  вдвое быстрее.
\end{itemize}
\begin{remark}
  Раман упоминает ещё одну область приложений~--- устойчивые структуры
  данных. Как указано в предыдущей главе, долгое время считалось,
  что амортизация несовместима с устойчивостью. Однако, разумеется,
  теперь мы знаем, что это не так.
\end{remark}

Означает ли это, что для программистов в этих областях
амортизированные структуры данных не представляют интереса? Вовсе
нет. Поскольку часто амортизированные структуры данных устроены проще,
чем структуры с жёсткими ограничениями, иногда оказывается легче
сначала разработать амортизированную структуру, а затем преобразовать
ее в жёсткую, чем разработать структуру с жёсткими ограничениями с
нуля.

В этой главе мы описываем \term{расписания}{scheduling}~--- метод для
преобразования амортизированных структур данных в структуры с жёсткими
ограничениями путем систематического вынуждения задержек, так что ни
одна из них не выполняется слишком долго. При использовании этого
метода к каждому объекту добавляется дополнительная компонента~---
\term{расписание}{schedule}, управляющая порядком вынуждения задержек
внутри этого объекта.

\section{Расписания}
\label{sc:7.1}

Амортизированные структуры данных и структуры данных с жёсткими
ограничениями различаются в основном временем, когда происходит вычисление,
входящее в стоимость какой-либо операции. В структуре с жёсткими ограничениями для
наихудшего случая все вычисления, составляющие стоимость операции,
происходят во время самой этой операции. В амортизированной структуре
данных некоторые вычисления, входящие в стоимость операции, могут на
самом деле производиться во время более поздних операций. Отсюда мы
видим, что почти все структуры данных, считающиеся жёсткими, будучи
реализованы на чисто ленивом языке, превращаются в амортизированные,
поскольку многие вычисления оказываются задержаны без особой нужды.
Следовательно, для описания структур с жёсткими ограничениями нам
нужен энергичный язык. Если же нам нужно описывать как
амортизированные, так и жёсткие структуры данных, требуется язык,
поддерживающий как ленивый порядок вычисления, так и
энергичный. Имея такой язык, мы можем рассмотреть любопытный
гибридный подход: структуры с жёсткими характеристиками, использующие
внутри своей реализации ленивое вычисление. Мы получаем такие
структуры данных, беря за основу ленивые амортизированные структуры и
модифицируя их так, чтобы каждая операция укладывалась в отведенное ей
время.

В ленивой амортизированной структуре данных каждая конкретная операция
может занять дольше, чем её заявленное ограничение. Однако такое
происходит только в том случае, если эта операция вынуждает задержку,
которая уже была оплачена, но требует большого времени для
выполнения. Чтобы уложиться в жёсткие ограничения, мы должны
гарантировать, что всякая задержка выполняется не дольше отведенного
ей времени.

Определим \term{собственную стоимость}{intrinsic cost} задержки как
время, которое уходит на вынуждение задержки в предположении, что все
другие задержки, от которых она зависит, уже были вынуждены и
мемоизированы, и, следовательно, занимают по $O(1)$ времени
каждая. (Это определение похоже на определение нераздельной стоимости
операции.) Первым шагом в преобразовании амортизированной структуры в
жёсткую будет уменьшение собственной стоимости каждой
задержки до размеров меньше желаемого ограничения. Обычно при этом
требуется переписать дорогие монолитные функции и сделать их
пошаговыми~--- либо путем небольших изменений в алгоритмах, либо путем
перехода от представления, поддерживающего только монолитные функции,
скажем, задержанных списков, к такому, которое также поддерживает
пошаговые функции, скажем, к потокам.

Даже если каждая задержка имеет маленькую собственную стоимость,
некоторые задержки по-прежнему могут занимать долгое время. Это
происходит, когда одна задержка зависит от другой, эта вторая от
третьей, и так далее. Если ни одна из этих задержек заранее не была
выполнена, то вынуждение первой задержки приводит к каскаду других
вынуждений. Рассмотрим, например, следующее вычисление:
$$
(\cdots((s_1 \concat s_2) \concat s_3) \concat \cdots) \concat s_k
$$
Вынуждение задержки, возвращаемой самым внешним $\concat$, вызывает
цепную реакцию, в ходе которой каждая из $\concat$ производит по
шагу. Несмотря на то, что собственная стоимость внешней задержки
составляет $O(1)$, общее время на её вынуждение равно $O(k)$ (или даже
больше, если первая ячейка $s_1$ является дорогой по каким-либо ещё
причинам).
\begin{remark}
  Случалось ли вам ставить костяшки домино в ряд, чтобы каждая из них
  сбивала следующую? Несмотря на то, что собственная стоимость опрокидывания
  каждой костяшки равна $O(1)$, реальная стоимость опрокидывания первой
  костяшки может быть намного, намного больше.
\end{remark}

Второй шаг при преобразовании амортизированной структуры данных в
жёсткую~--- избежать каскадирования вынуждений, устроив так, чтобы
всякий раз при вынуждении задержки все другие задержки, от которых она
зависит, были уже вынуждены и мемоизированы. Тогда ни одна задержка не
занимает при выполнении больше, чем её собственная стоимость. Мы этого
добиваемся, строя систематическое \term{расписание}{schedule}
выполнений каждой задержки, чтобы все они были готовы к тому времени,
как нам понадобятся. Трюк здесь состоит в том, чтобы рассматривать
выплату долга буквально, и вынуждать каждую задержку в момент, когда
она оплачивается.

\begin{remark}
  Работа с расписанием подобна опрокидыванию ряда костяшек начиная с
  хвоста, так чтобы всякий раз, когда одна костяшка падает на другую,
  эта другая была уже заранее сбита. Тогда реальная стоимость
  опрокидывания каждой костяшки будет мала.
\end{remark}

Мы добавляем к каждому объекту новую компоненту, называемую
\term{расписание}{schedule}. Она содержит, по крайней мере,
концептуально, ссылки на все невычисленные задержки внутри
объекта. Некоторые из этих задержек, возможно, уже были вычислены в
рамках другого логического будущего, но вынуждение их по второму разу
безвредно, поскольку алгоритм от этого становится только ещё быстрее,
чем ожидалось, а не медленнее. Всякая операция, в дополнение к любым
другим действиям, которые она производит с объектом, вынуждает
несколько первых задержек в расписании. Точное количество вынуждаемых
задержек управляется амортизационным анализом; как правило, каждая
задержка для выполнения требует время $O(1)$, так что мы вынуждаем
задержки пропорционально амортизированной стоимости операции. В
зависимости от конкретной структуры данных, ведение расписания может
быть нетривиальной задачей. Чтобы наша методика была применима,
добавление новой задержки к расписанию, а также нахождение следующей
задержки, подлежащей вынуждению, не должно требовать больше времени,
чем желаемые жёсткие ограничения.

\section{Очереди реального времени}
\label{sc:7.2}

Как пример нашей методики мы преобразуем амортизированные очереди по
методу банкира из Раздела~\ref{sc:6.3.2} в очереди с жёсткими
ограничениями. Очереди вроде этих, поддерживающие все операции за
время $O(1)$ в худшем случае, называются \term{очередями реального
  времени}{real time queues} \cite{HoodMelville1981}.

В исходной структуре данных очереди проворачиваются с помощью
$\concat$ и \lstinline!reverse!. Поскольку операция
\lstinline!reverse! монолитна, первая наша задача состоит в том, чтобы
научиться делать проворот пошагово. Этого можно добиться, если проводить
по шагу \lstinline!reverse! на каждый шаг $\concat$. Определим функцию
\lstinline!rotate!, такую, что
$$
\lstinline!rotate (xs, ys, a)! \equiv \lstinline!xs $\concat$ reverse ys $\concat$ a!
$$
Тогда
$$
\lstinline!rotate (f, r, $\$$Nil)! \equiv \lstinline!f $\concat$ reverse r!
$$
Дополнительный аргумент \lstinline!a! называется \term{аккумулирующим
  параметром}{accumulating parameter} и служит для хранения частичных
результатов обращения \lstinline!r!. Изначально он пуст.

Проворот происходит, когда $|\lstinline!r!| = |\lstinline!f!| + 1$,
так что в начале $|\lstinline!xs!| = |\lstinline!ys!| + 1$. Это
соотношение сохраняется на протяжении всего проворота, так что когда
\lstinline!xs! становится пустым, \lstinline!ys! содержит единственный
элемент. Следовательно, основание рекурсии выглядит как
$$
\begin{array}{l}
  \lstinline!rotate ($\$$Nil, $\$$Cons (y, $\$$Nil), a)! \\
\qquad \equiv \lstinline!($\$$Nil) $\concat$ reverse ($\$$Cons (y, $\$$Nil)) $\concat$ a! \\
\qquad \equiv \lstinline!$\$$Cons (y, a)! \\
\end{array}
$$
Шаг рекурсии таков:
$$
\begin{array}{l}
  \lstinline!rotate ($\$$Cons (x, xs), $\$$Cons (y, ys), a)! \\
\qquad \equiv \lstinline!($\$$Cons (x, xs)) $\concat$ reverse ($\$$Cons (y, ys)) $\concat$ a! \\
\qquad \equiv \lstinline!$\$$Cons (x, xs $\concat$ reverse ($\$$Cons (y, ys) $\concat$ a)! \\
\qquad \equiv \lstinline!$\$$Cons (x, xs $\concat$ reverse ys $\concat$ $\$$Cons (y, a))! \\
\qquad \equiv \lstinline!$\$$Cons (x, rotate (xs, ys, $\$$Cons (y, a)))! \\
\end{array}
$$
Объединяя два уравнения, получаем
\begin{lstlisting}
  fun rotate ($\$$Nil, $\$$Cons (y, _), a) = $\$$Cons (y, a)
    | rotate ($\$$Cons (x, xs), $\$$Cons (y, ys), a) =
        $\$$Cons (x, rotate (xs, ys, $\$$Cons (y, a)))
\end{lstlisting}
Заметим, что собственная стоимость каждой задержки, создаваемой
функцией \lstinline!rotate!, равна $O(1)$.

\begin{exercise}\label{ex:7.1}
  Покажите, что замена \lstinline!f $\concat$ reverse r! на
\lstinline!rotate (f, r, $\$$Nil)! в очередях по методу банкира из
Раздела~\ref{sc:6.3.2} уменьшает худшее возможное время операций
\lstinline!snoc!, \lstinline!head! и \lstinline!tail! с $O(n)$ до
$O(\log n)$. (Подсказка: докажите, что самая длинная цепочка
зависимостей между задержками имеет длину $O(\log n)$.) Если это
упростит ваш анализ, можете задержать сопоставление с образцом в
функции \lstinline!rotate!, написав \lstinline!fun lazy! вместо
\lstinline!fun!.
\end{exercise}

Теперь мы добавим к нашему типу данных расписание. Исходный тип имел
вид
\begin{lstlisting}
  type $\alpha$ Queue = int $\times$ $\alpha$ Stream $\times$ int $\times$ $\alpha$ Stream
\end{lstlisting}
Мы его расширяем новым полем \lstinline!s! типа \lstinline!$\alpha$ Stream!, которое
представляет расписание вынуждения узлов \lstinline!f!. Можно думать об \lstinline!s!
двумя способами: либо рассматривать его как суффикс \lstinline!f!,
либо как указатель на первую невычисленную задержку внутри
\lstinline!f!. Чтобы вычислить следующую задержку в расписании, мы
просто вынуждаем \lstinline!s!.

Помимо добавления \lstinline!s!, мы производим в нашем типе данных ещё
два изменения.  Во-первых, чтобы подчеркнуть, что к элементам
\lstinline!r! расписание не относится, мы превращаем \lstinline!r! из
потока в список. Это влечет небольшие изменения в
\lstinline!rotate!. Во-вторых, мы больше не храним явно длины
списков. Как мы скоро увидим, они нам теперь не нужны, чтобы
определить, когда \lstinline!r! становится длиннее \lstinline!f!~---
мы можем получить эту информацию из расписания. Таким образом, новый
тип данных имеет вид
\begin{lstlisting}
  type $\alpha$ Queue = $\alpha$ Stream $\times$ $\alpha$ list $\times$ $\alpha$ Stream
\end{lstlisting}
\begin{remark}
  Выигрыш в памяти при замене четырехчленных кортежей трехчленными
  может оказаться достаточным, чтобы оправдать переход с одного
  представления на другое, даже если жёсткие ограничения по времени
  нас не волнуют.
\end{remark}

С новым представлением основные операции над очередями выглядят весьма
просто:
\begin{lstlisting}
  fun snoc ((f, r, s), x) = exec (f, x :: r, s)
  fun head ($\$$Cons (x, f), r, s) = x
  fun tail ($\$$Cons (x, f), r, s) = exec (f, r, s)
\end{lstlisting}
Вспомогательная функция \lstinline!exec! выполняет следующую задержку
и поддерживает инвариант $|\lstinline!s!| = |\lstinline!f!| -
|\lstinline!r!|$ (что, между прочим, гарантирует $|\lstinline!f!| \ge
|\lstinline!r!|$, поскольку $|\lstinline!s!|$ не может быть
отрицательной). Функция \lstinline!snoc! увеличивает $|\lstinline!r!|$
на единицу, а \lstinline!tail! уменьшает $|\lstinline!f!|$ на единицу,
так что к моменту вызова \lstinline!exec! имеем $|\lstinline!s!| =
|\lstinline!f!| - |\lstinline!r!| + 1$. Если \lstinline!s! непуст,
для восстановления инварианта мы просто берем хвост
\lstinline!s!. Если же \lstinline!s! пуст, то \lstinline!r! на
единицу длиннее, чем \lstinline!f!, так что мы проворачиваем
очередь. В любом из этих случаев сопоставление \lstinline!s! с
образцом, когда мы выясняем, пуст ли он, само по себе вынуждает и мемоизирует
следующую задержку в расписании.
\begin{lstlisting}
  fun exec (f, r, $\$$Cons (x, s)) = (f, r, s)
    | exec (f, r, $\$$Nil) = let val f' = rotate (f, r, $\$$Nil) in (f', [], f') end
\end{lstlisting}
Полный код этой реализации очередей приведен на Рис.~\ref{fig:7.1}.

\begin{figure}
  \centering

  \caption{Очереди реального времени на основе расписания.}
  \label{fig:7.1}
\end{figure}

Путем просмотра кода можно убедиться, что каждая операция над очередью
занимает всего лишь $O(1)$ помимо вынуждения задержек, и что ни одна
операция не вынуждает более трех задержек.  Следовательно, чтобы
показать, что все операции в худшем случае занимают время $O(1)$,
остается доказать, что ни одна задержка при вычислении не занимает
время больше $O(1)$.

Операции над очередями создают только три различных вида задержек:
\begin{itemize}
\item \lstinline!$\$$Nil! создается функциями \lstinline!empty! и
  \lstinline!exec! (при первом вызове \lstinline!rotate!). Эта
  задержка тривиальна и всегда выполняется за время $O(1)$, независимо
  от того, была ли она вынуждена и мемоизирована раньше.
\item \lstinline!$\$$Cons (y, a)! создается в обеих строках
  \lstinline!rotate!. Эта задержка также тривиальна.
\item \lstinline!$\$$Cons (x, rotate (xs, ys, $\$$Cons (y, a)))!
  создается во второй строке \lstinline!rotate!. Эта задержка выделяет
  ячейку \lstinline!Cons!, создает новую задержку, и рекурсивно
  вызывает \lstinline!rotate!, которая производит сопоставление
  образца с первой ячейкой \lstinline!xs! и немедленно создает ещё
  одну задержку. Из всех этих действий только вынуждение, связанное с
  сопоставлением с образцом, в принципе могло бы занимать больше, чем
  время $O(1)$. Заметим, однако, что \lstinline!xs!~--- суффикс
  головного потока, который существовал перед предыдущим проворотом
  очереди. Наш режим работы с расписанием \lstinline!s! гарантирует,
  что \emph{все} ячейки этого потока были вынуждены и мемоизированы,
  прежде чем запустился проворот, так что новое вынуждение этой ячейки
  занимает только $O(1)$ времени.
\end{itemize}
Поскольку все задержки выполняются за время $O(1)$, наихудшее время
выполнения любой из операций над очередью также $O(1)$.

\begin{hint}
  Эти очереди намного проще всех других реализаций реального
  времени. Кроме того, это одна из самых быстрых реализаций~--- с
  жёсткими ограничениями или амортизированными,~--- для приложений,
  где активно используется устойчивость.
\end{hint}

\begin{exercise}\label{ex:7.2}
  Вычислите размер очереди на основе размеров \lstinline!s! и
  \lstinline!r!. Насколько быстрее будет работать такая функция по
  сравнению с вычислением на основе размеров \lstinline!f! и
  \lstinline!r!?
\end{exercise}

\section{Биномиальные кучи}
\label{sc:7.3}

Мы возвращаемся к биномиальным кучам из Раздела~\ref{sc:6.4.1}, и с
помощью расписания обеспечиваем вставку за время $O(1)$ в худшем
случае. Напомним, что в предыдущей реализации представление кучи
выглядело как \lstinline!Tree list susp!, и поэтому функция \lstinline!insert!
по необходимости была монолитной. Первая наша цель~--- сделать её
пошаговой.

Сначала заменим задержанные списки в типе данных кучи на
потоки. Операция \lstinline!insert! зовет вспомогательную функцию
\lstinline!insTree!, которую теперь можно записать как
\begin{lstlisting}
  fun lazy insTree (t, $\$$Nil) = $\$$Cons (t, $\$$Nil)
         | insTree (t, ts as $\$$Cons (t', ts')) =
              if rank t < rank t' then $\$$Cons (t, ts)
              else insTree (link (t, t'), ts')
\end{lstlisting}
Эта функция по-прежнему монолитна, поскольку она не может вернуть
первое дерево, пока не выполнены все связывания. Чтобы сделать функцию
пошаговой, нужно как-то заставить \lstinline!insTree! возвращать после
каждой итерации частичный результат. Можно этого добиться, если
сделать связь между биномиальными кучами и двоичными числами более
явной. Деревья в куче соответствуют единицам в двоичном представлении
размера кучи. Мы расширяем это соответствие, вводя явное представление
для нулей.
\begin{lstlisting}
  datatype Tree = Node of Elem.T $\times$ Tree list
  datatype Digit = Zero | One of Tree
  type Heap = Digit stream
\end{lstlisting}
Заметим, что мы исключили поле ранга из конструктора \lstinline!Node!,
поскольку ранг каждого дерева полностью определяется его позицией:
дерево, хранящееся в $i$-й цифре, имеет ранг $i$, а дети ячейки ранга
$r$ имеют ранги $r - 1,\ldots, 0$. Кроме того, мы требуем, чтобы
всякий непустой поток заканчивался единицей-\lstinline!One!.

Теперь можно написать \lstinline!insTree!:
\begin{lstlisting}
  fun lazy insTree (t, $\$$Nil) = $\$$Cons (One t, $\$$Nil)
         | insTree (t, $\$$Cons(Zero, ds)) = $\$$Cons (One t, ds)
         | insTree (t, $\$$Cons (One t', ds)) =
              $\$$Cons (Zero, insTree (link (t, t'), ds))
\end{lstlisting}
Эта функция пошаговая, поскольку каждый ее промежуточный шаг
возвращает ячейку \lstinline!Cons!, содержащую ноль-\lstinline!Zero! и
задержку для остального
вычисления. Последний шаг возвращает единицу.

На следующем шаге мы добавляем к нашему типу данных
расписание. Расписание выглядит как список заданий, а каждое
задание~--- поток \lstinline!Digit Stream!, представляющий
не выполненный пока полностью вызов \lstinline!insTree!.
\begin{lstlisting}
  type Schedule = Digit Stream list
  type Heap = Digit Stream $\times$ Schedule
\end{lstlisting}
Когда нам нужно выполнить шаг в расписании, мы вынуждаем голову
первого задания. Если в результате получается \lstinline!One!, значит,
это задание выполнено, и мы его из расписания изымаем. Если же
получается \lstinline!Zero!, мы кладем остаток задания обратно в
расписание.
\begin{lstlisting}
  fun exec [] = []
    | exec (($\$$Cons (One t, _)) :: sched) = sched
    | exec (($\$$Cons (Zero, job) :: sched) = job :: sched
\end{lstlisting}
Наконец, мы меняем код функции \lstinline!insert!, чтобы она
поддерживала расписание. Поскольку амортизированная стоимость
\lstinline!insert! равнялась двум, мы предполагаем, что выполнение двух
шагов при каждом \lstinline!insert! будет достаточно, чтобы ко
времени, когда каждая задержка потребуется, она была уже вынуждена.
\begin{lstlisting}
  fun insert (x, (ds, sched)) =
        let val ds' = insTree (Node (x, []), ds)
        in (ds', exec (exec (ds' :: sched))) end
\end{lstlisting}
Чтобы показать, что \lstinline!insert! занимает время $O(1)$ в худшем
случае, надо сначала показать, что \lstinline!exec! занимает $O(1)$ в
худшем случае. А именно, надо показать, что всякий раз, как
\lstinline!exec! вынуждает некоторую задержку (сопоставляя её с
образцом), все другие задержки, от которых зависит данная, уже
вычислены и мемоизированы.

Если мы развернем конструкцию \lstinline!fun lazy! в определении
\lstinline!insTree! и немного упростим результат, мы увидим, что
\lstinline!insTree! порождает задержку, эквивалентную такому коду:
\begin{lstlisting}
  $\$$case ds of
        $\$$Nil $\Rightarrow$ Cons (One t, $\$$Nil)
      | $\$$Cons (Zero, ds') $\Rightarrow$ Cons (One t, ds')
      | $\$$Cons (One t', ds') $\Rightarrow$ Cons (Zero, insTree (link (t, t'), ds'))
\end{lstlisting}
Задержка для каждой порождаемой \lstinline!insTree! цифры зависит от
задержки для предыдущей цифры того же индекса. Мы доказываем, что
никогда не бывает более одной ожидающей задержки на индекс потока
цифр, и, следовательно, что никакая невыполненная задержка не зависит
от другой невыполненной задержки.

Пусть \term{область}{range} задания в расписании будет набор цифр,
порожденных соответствующим вызовом \lstinline!insTree!. Каждая такая
область содержит последовательность нулей (возможно, пустую) с единицей в
конце. Мы говорим, что две области \term{перекрываются}{overlap}, если
какие-то их цифры имеют один и тот же индекс в потоке цифр. Каждая
невычисленная цифра находится в области некоторого задания в
расписании, так что нам надо доказать, что никакие две области не
перекрываются.

Мы доказываем даже несколько более сильное утверждение. Назовем
\term{завершенным нолем}{completed zero} ноль, чья ячейка в потоке уже
вычислена и мемоизирована.

\begin{theorem}\label{th:7.1}
  В каждой правильно построенной куче есть по крайней мере два
  завершенных ноля перед первой областью в расписании, и по крайней
  мере по одному завершенному нолю между любыми двумя соседними
  областями в расписании.

  \emph{Доказательство.} Пусть $r_1$ и $r_2$~--- первые две области в
  расписании. Пусть $z_1$ и $z_2$~--- два завершенных ноля перед
  $r_1$, а $z_3$~--- завершенный ноль между $r_1$ и $r_2$. Функция
  \lstinline!insert! добавляет новую область $r_0$ в начало
  расписания, а затем немедленно дважды вызывает
  \lstinline!exec!. Заметим, что $r_0$ заканчивается
  единицей-\lstinline!One!, замещающей $z_1$. Пусть $m$ будет
  количество нолей в $r_0$. Возможны три случая.
  \begin{description}
  \item[Случай 1.] $m = 0$. Единственная цифра в $r_0$~--- единица, так
    что $r_0$ уничтожается первым же \lstinline!exec!. Второй
    \lstinline!exec! вынуждает первую цифру $r_1$. Если это ноль, то
    он оказывается вторым завершенным нолем (помимо $z_2$) перед
    первой областью. Если же цифра~--- единица, то $r_1$ уничтожается,
    и новой первой областью становится $r_2$.  Перед $r_2$ имеется два
    завершенных ноля $z_2$ и $z_3$.
  \item[Случай 2.] $m = 1$. В $r_0$ содержится две цифры, ноль и
    единица. Эти две цифры немедленно вынуждаются двумя вызовами
    \lstinline!exec!, и $r_0$ уничтожается. Ведущий ноль заменяет
    $z_1$ как один из двух завершенных нолей перед $r_1$.
  \item[Случай 3.] $m \ge 2$. Первые две цифры $r_0$~--- ноли. После
    двух вызовов \lstinline!exec! они оказываются двумя завершенными
    нолями перед тем областью, которая теперь первая (остаток
    $r_0$). $z_2$ оказывается (единственным) завершенным нолем между
    $r_0$ и $r_1$.
  \end{description}
\end{theorem}

\begin{exercise}\label{ex:7.3}
  Покажите, что аннотацию \lstinline!lazy! в определении
  \lstinline!insTree! можно удалить без всякого вреда для времени
  работы \lstinline!insert!.
\end{exercise}

Адаптация остальных функций к новым типам данных не представляет
особого труда. Полная реализация приведена на
Рис.~\ref{fig:7.2}. По поводу этого кода имеет смысл сделать ещё
четыре небольших замечания. Во-первых, вместо того, чтобы пытаться
производить какие-либо ухищрения с расписанием, функции
\lstinline!merge! и \lstinline!deleteMin! выполняют все задержки в
системе (путем вызова функции \lstinline!normalize!), а расписание
устанавливают в \lstinline![]!. Во-вторых, как следует из
Теоремы~\ref{th:7.1}, в куче всегда содержится не более $O(\log n)$
невычисленных задержек, так что их вынуждение при нормализации или
поиске минимального корневого элемента не влияет на асимптотическое
время выполнения \lstinline!merge!, \lstinline!findMin! или
\lstinline!deleteMin!, поскольку каждая из них и так работает в худшем
случае за $O(\log n)$. В-третьих, вспомогательная функция
\lstinline!removeMinTree! иногда дает в результате потоки цифр,
завершающиеся нолями, однако эти потоки либо отбрасываются в
\lstinline!findMin!, либо сливаются со списком единиц внутри
\lstinline!deleteMin!. Наконец, \lstinline!deleteMin! должна теперь
производить больше работы, чем в предыдущих реализациях, преобразуя
список детей в правильно построенную кучу. В дополнение к обращению
списка, \lstinline!deleteMin! должна добавить по единице к каждому из
деревьев, а затем преобразовать список в поток. Если $c$~--- список
детей, весь процесс можно записать как
\begin{lstlisting}
  listToStream (map One (rev c))
\end{lstlisting}
где
\begin{lstlisting}
  fun listToStream [] = $\$$Nil
    | listToStream (x :: xs) = $\$$Cons (x, listToStream xs)

  fun map f [] = []
    | map f (x :: xs) = (f x) :: (map f xs)
\end{lstlisting}
Здесь \lstinline!map!~--- стандартная функция, применяющая другую
функцию (в нашем случае, конструктор \lstinline!One!) ко всем
элементам списка.

\begin{figure}
  \centering

  \caption{Биномиальные кучи с расписанием.}
  \label{fig:7.2}
\end{figure}

\begin{exercise}\label{ex:7.4}
  Напишите эффективную специализированную версию \lstinline!mrg!,
  называемую \lstinline!mrgWithList!, чтобы \lstinline!deleteMin! мог
  вызывать
  \begin{lstlisting}
    mrgWithList (rev c, ds')
  \end{lstlisting}
  вместо
  \begin{lstlisting}
    mrg (listToStream (map One (rev c)), ds')
  \end{lstlisting}
\end{exercise}

\section{Сортировка снизу вверх с расписанием}

В качестве третьего примера расписаний, мы изменяем сортируемые
коллекции из Раздела~\ref{sc:6.4.3}, чтобы \lstinline!add! работала в
худшем случае за время $O(\log n)$, а \lstinline!sort! в худшем случае за $O(n)$.

Единственное место, где в амортизированной реализации используется
ленивое вычисление~---задержанный вызов \lstinline!addSeg! в функции
\lstinline!add!. Задержка монолитна, так что нашей первой задачей
будет пошаговое выполнение этого вычисления. В сущности, достаточно
сделать пошаговой только функцию \lstinline!mrg!: поскольку
\lstinline!addSeg! требует всего лишь $O(\log n)$ шагов, мы можем себе
позволить вычислять ее энергично.  Следовательно, мы представляем
сегменты в виде потоков, а не списков, и отказываемся от задержки при
коллекции сегментов. Новый тип для коллекции сегментов будет
\lstinline!Elem.T Stream list!, а не \lstinline!Elem.T list list susp!.

Модификация функций \lstinline!mrg!, \lstinline!add! и
\lstinline!sort! под это новое представление не составляет труда;
разве что \lstinline!sort! должна окончательный отсортированный
результат перевести обратно в список. Для этого используется функция
преобразования \lstinline!streamToList!.
\begin{lstlisting}
  fun streamToList ($\$$Nil) = []
    | streamToList ($\$$Cons (x, xs)) = x :: streamToList xs
\end{lstlisting}

Новая версия \lstinline!mrg!, приведенная на Рис.~\ref{fig:7.3},
производит слияние по шагу за раз, и собственная стоимость такого шага
$O(1)$. Вторая наша цель состоит в том, чтобы проводить достаточное
количество шагов слияния при каждом \lstinline!add! и
гарантировать, что любая сортируемая коллекция содержит не более
$O(n)$ невычисленных задержек. Тогда \lstinline!sort! будет проводить
не более $O(n)$ вынуждений в дополнение к своей собственной работе
ценой также $O(n)$. Вынуждение невычисленных задержек отнимает
максимум $O(n)$ времени, так что общая стоимость \lstinline!sort!
оказывается не более $O(n)$.

При амортизационном анализе амортизированная стоимость
\lstinline!add! составляла приблизительно $2B'$, где $B'$~--- число
единичных битов в $n' = n + 1$. Это наводит на мысль, что
\lstinline!add! должна выполнять две задержки на каждый бит, или, что
то же самое, две задержки на сегмент. Мы храним отдельное расписание
для каждого сегмента. Каждое расписание является списком
потоков, которые представляют невыполненные пока полностью вызовы
\lstinline!mrg!. Таким образом, полный тип выглядит так:
\begin{lstlisting}
  type Schedule = Elem.T Stream list
  type Sortable = int $\times$ (Elem.T Stream $\times$ Schedule) list
\end{lstlisting}
Чтобы выполнить один шаг расписания, мы зовем функцию
\lstinline!exec1!.
\begin{lstlisting}
  fun exec1 [] = []
    | exec1 (($\$$Nil):: sched) = exec1 sched
    | exec1 (($\$$Cons (x, xs) :: sched)) = xs :: sched
\end{lstlisting}
Во второй строке этой функции мы достигаем конца одного потока и
выполняем первый шаг в следующем потоке. Здесь не может образоваться
цикл, поскольку только первый поток в списке может быть пуст. Функция
\lstinline!exec2! берет сегмент и дважды применяет \lstinline!exec1!
к его расписанию.
\begin{lstlisting}
  fun exec2 (xs, sched) = (xs, exec1 (exec1 sched))
\end{lstlisting}
Функция \lstinline!add! вызывает \lstinline!exec2! для каждого
сегмента, но кроме этого она отвечает за построение расписания для
нового сегмента. Если младшие $k$ битов размера $n$ равны единице, то
добавление нового элемента приведет к $k$ слияниям вида
$$
((s_0 \bowtie s_1) \bowtie s_2) \cdots \bowtie s_k
$$
где $s_0$~--- новый одноэлементный сегмент, а $s_1 \ldots s_k$~---
первые $k$ сегментов существующей коллекции. Частичными результатами
этого вычисления будут $s'_1 \ldots s'_k$, где $s'_1 = s_0 \bowtie
s_1$, а $s'_i = s'_{i-1} \bowtie s_i$. Поскольку задержки в $s'_i$
зависят от задержек в $s'_{i-1}$, нам нужно спланировать выполнение
$s'_{i-1}$ прежде выполнения $s'_i$.  Кроме этого, задержки в $s'_i$
зависят от задержек в $s_i$, но тут мы гарантируем, что ко времени
вызова \lstinline!add! значения $s_1 \ldots s_k$ будут уже полностью
вычислены.

Окончательная версия функции \lstinline!add!, создающая новое
расписание и выполняющая по две задержки на сегмент, выглядит так:
\begin{lstlisting}
  fun add (x, (size, segs)) =
       let fun addSeg (xs, segs, size, rsched) =
                 if size mod 2 = 0 then (xs, rev rsched) :: segs
                 else let val ((xs', []) :: segs') = segs
                          val xs'' = mrg (xs, xs')
                      in addSeg (xs'', segs', size div 2, xs'' :: rsched) end
           val segs' = addSeg ($\$$Cons (x, $\$$Nil), segs, size, [])
       in (size+1, map exec2 segs') end
\end{lstlisting}
Аккумулирующий параметр \lstinline!rsched! собирает свежеслитые потоки
в обратном порядке. Поэтому мы обращаем их список в конце и
получаем правильный порядок. Сопоставление с образцом в четвертой
строке требует, чтобы старое расписание для текущего сегмента было
пустым, т.~е., чтобы оно уже было полностью выполнено. Мы вскоре
увидим, почему это так.

Полный код нашей реализации приведен на Рис.~\ref{fig:7.3}. Функция
\lstinline!add! имеет нераздельную стоимость $O(\log n)$, а
\lstinline!sort! нераздельную стоимость $O(n)$, так что, чтобы
доказать ограничения для худшего случая, мы должны доказать, что
$O(\log n)$ задержек, вынуждаемых \lstinline!add!, занимают время
$O(1)$ каждая, и что $O(n)$ невычисленных задержек, вынуждаемых
\lstinline!sort!, вместе требуют $O(n)$.

\begin{figure}
  \centering

  \caption{Сортировка слиянием снизу вверх с расписанием.}
  \label{fig:7.3}
\end{figure}

Каждый шаг слияния, вынуждаемый изнутри \lstinline!add! (через
\lstinline!exec2! и \lstinline!exec1!) зависит от двух других
потоков. Если текущий шаг является частью потока $s'_i$, то он зависит
от потоков $s'_{i-1}$ и $s_i$. Поток $s'_{i-1}$ находился в расписании
раньше $s'_i$, так что ко времени начала вычисления $s'_i$ он уже был
полностью вычислен. Кроме того, $s_i$ был уже полностью вычислен ко
времени вызова \lstinline!add!, который создал $s'_i$. Поскольку
собственная стоимость каждого шага слияния равна $O(1)$, а задержки,
вынуждаемые каждым шагом, уже были вынуждены и мемоизированы, каждый
шаг слияния, вынуждаемый \lstinline!add!, отнимает время только $O(1)$
для наихудшего случая.

Следующая лемма доказывает, что каждый сегмент, вовлеченный в слияние
через \lstinline!addSeg!, уже полностью вычислен, и что коллекция в
целом содержит не более $O(n)$ невычисленных задержек.

\begin{lemma}\label{lm:7.2}
  Во всякой сортируемой коллекции размера $n$ расписание для сегмента
  размера $m = 2^k$ содержит не более $2m - 2(n \mod m + 1)$ элементов.

  \emph{Доказательство.} Рассмотрим сортируемую коллекцию размера $n$,
где $k$ младших битов $n$ равны единице (т.~е., $n$ можно записать как
$c2^{k+1} + 2^k -1$ для некоторого целого $c$). Тогда \lstinline!add!
порождает новый сегмент размера $m = 2^k$, и его расписание содержит
потоки размеров $2, 4, 8, \ldots 2^k$. Общий размер этого расписания
$2^{k+1} - 2 = 2m - 2$. После выполнения двух шагов размер расписания
оказывается $2m - 4$. Размер новой коллекции равен $n' = n + 1 =
c2^{k+1} + 2^k$. Поскольку $2m - 4  < 2m - 2(n' \mod m + 1) = 2m - 2$,
для этого сегмента лемма выполняется.

В важдом сегменте размера $m'$, большего $m$, при операции
\lstinline!add! выполняются только два шага
расписания, и больше ничего не происходит. Размер нового расписания
ограничен
$$
2m' - 2(n \mod m' + 1) - 2 = 2m' - 2(n' \mod m' + 1),
$$
так что и для этих сегментов лемма также выполняется.
\end{lemma}

Теперь всякий раз, когда младшие $k$ битов $n$ равны единице (т.~е.,
когда следующий \lstinline!add! собирается слить первые $k$
сегментов), мы из Леммы~\ref{lm:7.2} знаем, что для каждого сегмента
размера $m = 2^i$, где $i < k$, число элементов в расписании этого
сегмента не больше
$$
2m -2(n \mod m + 1) = 2m - 2((m-1) + 1) = 0
$$
Другими словами, этот сегмент уже полностью вычислен.

Наконец, общий размер расписаний для всех сегментов не может быть
больше
$$
2 \sum_{i=0}^\infty b_i(2^i - (n \mod 2^i + 1)) = 2n - 2 \sum_{i=0}^\infty b_i (n \mod 2^i + 1)
$$
элементов, где $b_i$~--- $i$-й бит числа $n$. Заметим, что это очень
похоже на функцию потенциала из анализа методом физика в
Разделе~\ref{sc:6.4.3}. Поскольку этот общий размер ограничен числом
$2n$, вся коллекция содержит только $O(n)$ невыполненных задержек, а
следовательно, \lstinline!sort! выполняется в худшем случае за время
$O(n)$.

\section{Примечания}
\label{sc:7.5}

\noindent
\textbf{Избавление от амортизации}
Дитц и Раман \cite{DietzRaman1991, DietzRaman1993, Raman1992}
разработали методику избавления от амортизации на основе
\term{игр с камнями}{pebble games}, где порождаемые алгоритмы с
жёсткими ограничениями соответствуют выигрышным стратегиям в некоторой
игре. Другие исследователи использовали частные методы, похожие на
расписание, для избавления от амортизации в конкретных структурах
данных, например, в \term{неявных биномиальных кучах}{implicit
  binomial queues} \cite{CarlssonMunroPoblete1988} и
\term{расслабленных кучах}{relaxed heaps}
\cite{Driscoll-etal1988}. Расписания, подобные описанным в этой главе,
впервые были применены к очередям в \cite{Okasaki1995c}, а затем
обобщены в \cite{Okasaki1996b}.

\noindent
\textbf{Очереди}
Реализация кучи, описанная в Разделе~\ref{sc:7.2}, впервые появилась в
\cite{Okasaki1995c}. Худ и Мелвилл \cite{HoodMelville1981} представили
первую чисто функциональную реализацию очередей реального времени,
на основе метода, известного как \term{глобальная
  перестройка}{global rebuilding} \cite{Overmars1983}, который будет
обсуждаться в следующей главе. Их реализация сложнее нашей и не использует ленивое
вычисление.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pfds"
%%% End: