chapter08.tex

\chapter{Ленивая перестройка}
\label{ch:8}

В оставшихся четырех главах мы описываем общие методы проектирования
функциональных структур данных.  Первый из них, рассматриваемый в этой
главе~--- \term{ленивая перестройка}{lazy rebuilding}, разновидность
\term{глобальной перестройки}{global rebuilding} \cite{Overmars1983}.

\section{Порционная перестройка}

Во многих структурах данных соблюдаются инварианты баланса, благодаря
которым гарантируется эффективный доступ. Каноническим примером могут
служить сбалансированные деревья поиска, улучшающие время работы в
худшем случае для многих операций с $O(n)$ у несбалансированных
деревьев до $O(\log n)$. Один из подходов к соблюдению инварианта
баланса~--- перебалансировка структуры после каждой её
модификации. Для большинства сбалансированных структур существует
понятие \term{идеального баланса}{perfect balance}, то есть,
конфигурация, минимизирующая стоимость последующих действий. Однако,
поскольку, как правило, восстанавливать идеальный баланс после
каждого изменения оказывается слишком дорого, в большинстве реализаций
считается достаточным поддерживать некоторое приближение к нему,
ухудшающее показатели не более чем на константный множитель. Примерами
такого подхода являются AVL-деревья \cite{AdelsonVelskiiLandis1962}
и красно-чёрные деревья \cite{GuibasSedgewick1978}.

Однако если каждое отдельное обновление не слишком сильно влияет на
баланс, привлекательным альтернативным подходом будет отложить
перестройку, пока не пройдёт некоторая серия операций, а затем
перебалансировать всю структуру и восстановить идеальный
баланс. Назовем этот подход \term{порционной перестройкой}{batched
  rebuilding}. Порционная перестройка дает хорошие амортизированные
ограничения, если выполняются два условия: (1) глобальная структура
перестраивается не слишком часто, и (2) отдельные модифицирующие
действия ухудшают показатели последующих операций не слишком
сильно. Выражаясь более точно, условие (1) говорит, что, если мы
надеемся достичь амортизированного показателя $O(f(n))$ на операцию, а
преобразование перебалансировки занимает время $O(g(n))$, запускать
это преобразование нельзя чаще, чем раз в $c \cdot g(n) / f(n)$
операций, для некоторой константы $c$. Рассмотрим, например, двоичные
деревья поиска. Перестройка дерева с полной балансировкой занимает
время $O(n)$, так что, если мы хотим, чтобы наши операции занимали
амортизированное время не больше $O(n)$, структуру данных нельзя
перестраивать чаще, чем раз в $c \cdot n / \log n$ операций, для
некоторой константы $c$.

Допустим, что структура данных будет перестраиваться раз в $c \cdot
g(n) / f(n)$ операций, и что отдельная операция над перестроенной
структурой отнимает время $O(f(n))$ (ограничение может быть жёстким
или амортизированным). В этом случае условие (2) утверждает, что,
сделав не более $c \cdot g(n) / f(n)$ обновлений непосредственно после
перестройки, мы по-прежнему будем тратить время не более
$O(f(n))$. Другими словами, стоимость каждой отдельной операции должна
ухудшиться максимум на константный множитель. Функции обновления,
удовлетворяющие условию (2), называются \term{операциями слабого
  обновления}{weak updates}.

Рассмотрим, например, следующий подход к реализации функции
\lstinline!delete! на двоичных деревьях поиска. Вместо того, чтобы
физически уничтожать указанный узел дерева, оставляем его в дереве с
пометкой <<стёрто>>. Затем, когда стёртыми оказываются половина
узлов, делаем глобальный проход, уничтожая стёртые узлы и
восстанавливая идеальный баланс.  Удовлетворяет ли этот подход нашим
двум условиям, если мы хотим, чтобы уничтожение элемента занимало
амортизированное время $O(\log n)$?

Допустим, дерево содержит $n$ узлов, из которых не более половины
помечено как стёртые. Уничтожение стёртых узлов и восстановление
идеального баланса в дереве занимает время $O(n)$. Мы выполняем это
преобразование раз в $\frac{1}{2}n$ операций уничтожения, так что
условие (1) выполнено. На самом деле, условие (1) позволяет нам
перестраивать структуру даже чаще, раз в $c \cdot n / \log n$
операций.  Наивный алгоритм уничтожения ищет нужный узел и помечает его
как стёртый. Это отнимает время $O(\log n)$, даже если половина
узлов уже помечена как стёртые, так что условие (2) выполнено.
Заметим, что даже если половина узлов в дереве помечена, средняя
глубина активного узла больше всего на единицу по сравнению со
случаем, когда они физически уничтожены. Дополнительная глубина
ухудшает стоимость операции всего лишь на аддитивную константу, в то
время как условие (2) позволяет времени каждой операции ухудшаться на
константный множитель. Следовательно, условие (2) позволяет нам
перестраивать нашу структуру данных даже ещё реже.

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

\begin{exercise}\label{ex:8.1}
  Добавьте к красно-чёрным деревьям из Раздела~\ref{sc:3.3} функцию
  \lstinline!delete! на основе описанного здесь подхода. Добавьте к
  конструктору \lstinline!T! булевское поле, и поддерживайте
  счётчики-оценки числа
  активных и неактивных элементов в дереве. Для этих счётчиков
  предполагайте, что каждая вставка создает новый элемент, а каждая
  операция уничтожения делает какой-то активный элемент
  неактивным. Обновляйте значение этих счётчиков при перестройке.  Для
  перестройки воспользуйтесь решением Упражнения~\ref{ex:3.9}.
\end{exercise}

В качестве второго примера порционной перестройки рассмотрим
порционные очереди из Раздела~\ref{sc:5.2}. Преобразование перестройки
переносит обращённый хвостовой список в головной, и очередь переходит
в идеально сбалансированное состояние, когда все элементы содержатся в
головном списке.  Как мы уже видели, порционные очереди имеют хорошие
показатели эффективности, но только при эфемерном использовании. Если
их использовать как устойчивую структуру, амортизированные характеристики
деградируют до стоимости операции перестройки, поскольку эта операция
может срабатывать сколь угодно часто. Это наблюдение верно для всех
структур с порционной перестройкой.

\section{Глобальная перестройка}
\label{sc:8.2}

Овермарс \cite{Overmars1983} описывает метод избавления от амортизации,
основанный на порционной перестройке. Он называет этот метод
\term{глобальная перестройка}{global rebuilding}. Основная идея
состоит в том, чтобы проводить трансформацию перестройки постепенно,
по несколько шагов при каждой нормальной операции. Полезно
рассматривать это как выполнение преобразования в
сопрограмме. Сложность в том, чтобы запустить сопрограмму достаточно
рано, чтобы она завершилась ко времени, когда понадобится
перестроенная структура.

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

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

Глобальную перестройку можно реализовать в чисто функциональном стиле,
и несколько таких реализаций существуют. Например, очереди реального
времени Худа и Мелвилла \cite{HoodMelville1981} основаны именно на
этом методе. В отличие от порционной перестройки, при глобальной
перестройке не возникает проблем с устойчивостью. Поскольку ни одна из
операций не является особенно дорогой, произвольное повторение
операций не влияет на временные характеристики.  К сожалению, часто
глобальная перестройка дает очень сложные структуры. В частности,
представление вторичной копии, которое сводится к хранению
промежуточного состояния сопрограммы, может быть довольно неприятным.

\subsection{Пример: очереди реального времени по Худу-Мелвиллу}
\label{sc:8.2.1}

Реализация очередей реального времени Худа и Мелвилла
\cite{HoodMelville1981} во многом похожа на очереди реального времени
из Раздела~\ref{sc:7.2}. В обеих реализациях поддерживается два
списка, представляющие головную и хвостовую части очереди
соответственно, и ведется пошаговый процесс переноса элементов из
хвостового списка в головной, начиная с того момента, когда хвостовой
список становится на единицу длиннее, чем головной.  Разница состоит в
деталях этого пошагового проворота.

Рассмотрим сначала, как можно провести пошаговое обращение списка
путем хранения двух списков и постепенного переноса элементов из
одного в другой.
\begin{lstlisting}
  datatype $\alpha$ ReverseState = Working of $\alpha$ list $\times$ $\alpha$ list | Done of $\alpha$ list

  fun startReverse xs = Working (xs, [])

  fun exec (Working (x :: xs, xs')) = Working (xs, x :: xs')
    | exec (Working ([], xs')) = Done xs'
\end{lstlisting}
Чтобы обратить список \lstinline!xs!, мы сначала создаем новое
состояние \lstinline!Working (xs, [])!, а затем многократно вызываем
\lstinline!exec!, пока не получим состояние \lstinline!Done! с
обращенным списком. Всего требуется $n + 1$ вызовов \lstinline!exec!,
где $n$~--- длина исходного списка \lstinline!xs!.

Можно провести пошаговую конкатенацию двух списков, применив этот
прием дважды. Сначала мы обращаем \lstinline!xs!, получая
\lstinline!xs'!, а затем обращаем \lstinline!xs'!, добавляя его к
\lstinline!ys!.
\begin{lstlisting}
  datatype $\alpha$ AppendState =
         Reversing of $\alpha$ list $\times$ list $\times$ $\alpha$ list $\times$ $\alpha$ list
       | Appending of $\alpha$ list $\times$ $\alpha$ list
       | Done of $\alpha$ list

  fun startAppend (xs, ys) = Reversing (xs, [], ys)

  fun exec (Reversing (x :: xs, xs', ys)) = Reversing (xs, x :: xs', ys)
    | exec (Reversing ([], xs', ys)) = Appending (xs', ys)
    | exec (Appending (x :: xs', ys)) = Appending (xs', x :: ys)
    | exec (Appending ([], ys)) = Done ys
\end{lstlisting}
Всего требуется $2m + 2$ вызова \lstinline!exec!, если длина исходного
списка \lstinline!xs! равна $m$.

Наконец, чтобы добавить \lstinline!f! к обращенному \lstinline!r!, мы
проводим три обращения. Сначала мы в параллель обращаем \lstinline!f!
и \lstinline!r!, получая \lstinline!f'! и \lstinline!r'!, а затем
приписываем обращенный \lstinline!f'! к \lstinline!r'!. Нижеследующий
код предполагает, что длина \lstinline!r! на единицу больше длины
\lstinline!f!.
\begin{lstlisting}
  datatype $\alpha$ RotationState =
         Reversing of $\alpha$ list $\times$ $\alpha$ list $\times$ $\alpha$ list $\times$ $\alpha$ list
       | Appending of $\alpha$ list $\times$ $\alpha$ list
       | Done of $\alpha$ list

  fun startRotation (f, r) = Reversing (f, [], r, [])

  fun exec (Reversing (x :: f, f', y :: r, r')) = Reversing (f, x :: f', r, y :: r')
    | exec (Reversing ([], f', [y], r')) = Appending (f', y :: r')
    | exec (Appending (x :: f', r')) = Appending (f', x :: r')
    | exec (Appending ([], r') = Done r'
\end{lstlisting}
Как и раньше, процедура завершается после $2m + 2$ вызовов
\lstinline!exec!, где $m$~--- исходная длина списка \lstinline!f!.

К сожалению, у этого способа проворота есть большой недостаток. Если
мы просто зовем \lstinline!exec! по несколько раз
при каждом вызове \lstinline!snoc! или \lstinline!tail!, то ко
времени, когда проворот закончится, ответ может быть уже не тот,
который нам нужен! В частности, если за время проворота было $k$
вызовов \lstinline!tail!, то $k$ первых элементов получившегося списка
уже не актуальны. Эту проблему можно решить двумя основными
способами. Во-первых, можно хранить счетчик устаревших элементов, и
добавить к процедуре проворота третье состояние \lstinline!Deleting!,
которое уничтожает элементы по несколько за раз, пока устаревшие
элементы не кончатся. Этот подход точнее всего соответствует
определению глобальной перестройки. Однако ещё лучше просто не
включать устаревшие элементы в окончательный список. Мы отслеживаем,
сколько живых элементов осталось в \lstinline!f'!, и перестаем
копировать элементы из \lstinline!f'! в \lstinline!r'!, когда счетчик
достигает нуля. Каждый вызов \lstinline!tail! во время проворота
уменьшает число живых элементов.
\begin{lstlisting}
  datatype $\alpha$ RotationState =
         Reversing of int $\times$ $\alpha$ list $\times$ $\alpha$ list $\times$ $\alpha$ list $\times$ $\alpha$ list
       | Appending of int $\times$ $\alpha$ list $\times$ $\alpha$ list
       | Done of $\alpha$ list

  fun startRotation (f, r) = Reversing (0, f, [], r, [])

  fun exec (Reversing (ok, x :: f, f', y :: r, r')) =
        Reversing (ok+1, f, x :: f', r, y :: r')
    | exec (Reversing (ok, [], f', [y], r')) = Appending (ok, f', y :: r')
    | exec (Appending (0, f', r')) = Done r'
    | exec (Appending (ok, x :: f', r')) = Appending (ok-1, f', x ::
    r')

  fun invalidate (Reversing (ok, f, f', r, r')) = Reversing (ok-1, f, f', r, r')
    | invalidate (Appending (0, f', x :: r')) = Done r'
    | invalidate (Appending (ok, f', r')) = Appending (ok-1, f', r')
\end{lstlisting}
Этот процесс завершается после $2m + 2$ обращений к \lstinline!exec! или
\lstinline!invalidate!, где $m$~--- исходная длина \lstinline!f!.

Требуется рассмотреть ещё три нетривиальных мелких вопроса. Во-первых,
во время проворота несколько начальных элементов очереди оказываются в
конце поля \lstinline!f'! структуры-состояния проворота. Как нам при
этом отвечать на запрос \lstinline!head!? Решение этой дилеммы состоит
в том, чтобы хранить рабочую копию старого головного списка. Нужно
только добиться того, чтобы новая копия головного списка оказалась
готова к тому времени, как исчерпается старая. Во время проворота поле
\lstinline!lenf! измеряет длину создаваемого списка, а не рабочей
копии \lstinline!f!. Однако между проворотами поле \lstinline!lenf!
содержит длину \lstinline!f!.

Во-вторых, надо решить, сколько именно обращений к \lstinline!exec!
надо делать при каждом вызове \lstinline!snoc! и \lstinline!tail!,
чтобы гарантировать, что проворот закончится к тому времени, когда либо
нужно будет начать следующий проворот, либо будет израсходована рабочая
копия головного списка.  Допустим, что в начале проворота длина списка
\lstinline!f! равна $m$, а длина списка \lstinline!r! равна
$m+1$. Тогда следующий проворот начнется после $2m+2$ вставок или
извлечений (в любом соотношении), однако рабочая копия головного
списка окажется израсходованной уже через $m$ извлечений. Всего
проворот заканчивается через $2m+2$ шагов. Если при каждой операции мы
зовем \lstinline!exec! два раза, включая операцию, которая запускает
проворот, то проворот завершится самое большее через $m$ операций после
своего начала.

В-третьих, поскольку каждый проворот заканчивается задолго до того, как
начинается следующий, требуется добавить к типу
\lstinline!RotationState! состояние \lstinline!Idle! (неактивное), так
что \lstinline!exec Idle = Idle!. После этого мы можем спокойно звать
\lstinline!exec!, не заботясь о том, находимся мы в процессе проворота
или нет.

Оставшиеся детали должны уже быть знакомы читателю. Полная реализация
приведена на Рис.~\ref{fig:8.1}.

\begin{figure}
  \centering

  \caption{Очереди реального времени на основе глобальной перестройки.}
  \label{fig:8.1}
\end{figure}

\begin{exercise}\label{ex:8.2}
  Докажите, что если звать \lstinline!exec! дважды при начале
  каждого проворота и один раз при каждой вставке или извлечении
  элемента, этого будет достаточно, чтобы проворот завершался
  вовремя. Соответствующим образом измените код.
\end{exercise}

\begin{exercise}\label{ex:8.3}
  Замените поля \lstinline!lenf! и \lstinline!lenr! одним полем
  \lstinline!diff!, которое хранит разницу между длинами списков
  \lstinline!f! и \lstinline!r!. Поле \lstinline!diff! не обязательно
  должно хранить точное значение в процессе проворота, но к концу проворота
  должно быть точным.
\end{exercise}

\section{Ленивая перестройка}
\label{sc:8.3}

Реализация очередей по методу физика из Раздела~\ref{sc:6.4.2} очень
похожа на версию с глобальной перестройкой, но имеется и существенное
различие. Как и при глобальной перестройке, в этой реализации
поддерживаются две копии головного списка, рабочая копия \lstinline!w!
и вторичная копия \lstinline!f!, причем все запросы обращаются к
рабочей копии. Операции обновления \lstinline!f! (т.~е., операции
\lstinline!tail!) буферизуются и выполняются по окончании проворота
через выражение
\begin{lstlisting}
  $\$$tl (force f)
\end{lstlisting}
Кроме того, эта реализация заботится о том, чтобы начать
(или, по крайней мере, спланировать) проворот задолго до того, как
понадобится его результат. Однако, в отличие от глобальной
перестройки, эта реализация не занимается \emph{выполнением}
преобразования перестройки (т.~е., проворота) в параллель с нормальными
операциями; вместо этого она \emph{оплачивает} преобразование
перестройки одновременно с нормальными операциями, но затем, когда вся
стоимость преобразования выплачена, оно выполняется целиком. В
сущности, мы заменили сложности явного или неявного переноса
перестройки в сопрограмму более простым механизмом ленивого
вычисления. Этот вариант глобальной перестройки мы называем
\term{ленивой перестройкой}{lazy rebuilding}.

Реализация очередей по методу банкира из Раздела~\ref{sc:6.3.2}
показывает ещё одно упрощение, доступное нам при использовании ленивой
перестройки. Внося вложенные задержки в исходную структуру данных~---
например, используя потоки вместо списков,~--- мы часто можем
уничтожить различие между рабочей и вторичной копиями, и использовать
единую структуру, обладающую свойствами их обеих. <<Рабочая>> часть
этой структуры~--- это та часть, которая уже оплачена, а
<<вторичная>>~--- та, за которую выплата ещё не произведена.

У глобальной перестройки есть два преимущества перед
порционной: она годится для реализации устойчивых структур данных, а
также соблюдает жёсткие ограничения вместо амортизированных. Ленивая
перестройка также обладает первым из этих преимуществ, однако, по
крайней мере, в простейшей своей форме дает амортизированные
ограничения. Но если это требуется, часто можно восстановить
жёсткие ограничения, используя расписания по методам из
Главы~\ref{ch:7}. Например, очереди реального времени из
Раздела~\ref{sc:7.2} сочетают ленивую перестройку с расписанием, и
получают в итоге реализацию с жёсткими характеристиками. В сущности,
сочетание ленивой перестройки с расписаниями можно рассматривать как
разновидность глобальной перестройки, где сопрограммы реифицированы
особенно простым образом через ленивое вычисление.

\section{Двусторонние очереди}
\label{sc:8.4}

В качестве дальнейших примеров глобальной перестройки мы приведем
несколько реализаций двусторонних очередей, или
\term{деков}{deques}. Деки отличаются от очередей FIFO тем, что
элементы могут как добавляться, так и изыматься с любого конца
очереди. Сигнатура для деков приведена на Рис.~\ref{fig:8.2}. Эта
сигнатура расширяет сигнатуру очередей тремя новыми функциями:
\lstinline!cons! (добавить элемент к началу очереди), \lstinline!last!
(вернуть последний элемент) и \lstinline!init! (изъять последний
элемент).

\begin{figure}
  \centering

  \caption{Сигнатура для двусторонних очередей.}
  \label{fig:8.2}
\end{figure}

\begin{remark}
  Заметим, что сигнатура очередей является строгим подмножеством
  сигнатуры для деков~--- для типа и аналогичных функций были выбраны
  совпадающие имена. Поскольку деки являются строгим расширением
  очередей, Стандартный ML позволит нам использовать дек везде, где
  ожидается модуль, реализующий очередь.
\end{remark}

\subsection{Деки с ограниченным выходом}
\label{sc:8.4.1}

Сначала заметим, что реализации очередей из Глав~\ref{ch:6} и
\ref{ch:7} можно тривиально расширить, добавив в дополнение к операции
\lstinline!snoc! операцию \lstinline!cons!. Очередь, поддерживающая
добавление элементов с обоих концов, но удаление только с одного,
называется \term{дек с ограниченным выходом}{output-restricted deque}.

Например, можно реализовать \lstinline!cons! в очередях по методу
банкира из Раздела~\ref{sc:6.3.2} следующим образом:
\begin{lstlisting}
  fun cons (x, (lrnf, f, lenr, r)) = (lenf+1, $\$$Cons (x, f), lenr, r)
\end{lstlisting}
Заметим, что нет никакой необходимости звать вспомогательную функцию
\lstinline!check!, поскольку добавление элемента к \lstinline!f! никак
не может сделать \lstinline!f! короче, чем \lstinline!r!.

Подобным же образом легко реализовать функцию \lstinline!cons! для
очередей реального времени из Раздела~\ref{sc:7.2}.
\begin{lstlisting}
  fun cons (x, (f, r,s)) = ($\$$Cons (x, f), r, $\$$Cons (x, s))
\end{lstlisting}
Мы добавлякм \lstinline!x! к \lstinline!s! только для того, чтобы
поддержать инвариант $|\lstinline!s!| = |\lstinline!f!| - |\lstinline!r!$|.

\begin{exercise}\label{ex:8.4}
  К сожалению, очереди реального времени по Худу-Мелвиллу не так легко
  расширяются функцией \lstinline!cons!, поскольку нет простого
  способа вставить элемент в структуру-состояние проворота. Напишите
  вместо этого функтор, который расширяет \emph{любую} реализацию
  очередей функцией \lstinline!cons!, работающей за константное время,
  с использованием типа
  \begin{lstlisting}
    type $\alpha$ Queue = $\alpha$ list $\times$ $\alpha$ Q.Queue
  \end{lstlisting}
  где \lstinline!Q!~--- параметр функтора. \lstinline!cons! должен
  вставлять элементы в новый список, а \lstinline!head! и
  \lstinline!tail! должны удалять элементы из нового списка, когда он
  непуст.
  %% !!!! head не должен !!!
\end{exercise}

\subsection{Деки по методу банкира}
\label{sc:8.4.2}

Деки можно представлять так же, как очереди, в виде двух потоков (или списков),
\lstinline!f! и \lstinline!r!, плюс некоторая дополнительная
информация, помогающая поддерживать баланс. Для очередей идеально
сбалансированная ситуация~--- когда все элементы находятся в головном
потоке. Для деков идеально сбалансированное состояние~--- когда
элементы поделены поровну между головным и хвостовым
потоками. Поскольку мы не можем себе позволить восстанавливать
идеальный баланс после каждой операции, мы удовольствуемся гарантией,
что ни один из потоков не может быть длиннее другого более чем в $c$
раз, для некоторой константы $c > 1$. А именно, мы поддерживаем
следующий инвариант баланса:
$$
  |\lstinline!f!| \le c |\lstinline!r!| + 1 \quad \land \quad
  |\lstinline!r!| \le c |\lstinline!f!| + 1
$$
Подвыражение <<$+1$>> в каждом из термов позволяет единственному
элементу одноэлементного дека находиться в любом из двух
потоков. Заметим, что если дек состоит по крайней мере из двух
элементов, оба потока должны быть непусты. Каждый раз, когда инвариант
грозит оказаться нарушенным, мы возвращаем дек в идеально
сбалансированное состояние, перенося элементы из более длинного потока
в более короткий, пока их длины не уравниваются.

На основе этих идей мы можем адаптировать либо очереди по методу
банкира из Раздела~\ref{sc:6.3.2}, либо очереди по методу физика из
Раздела~\ref{sc:6.4.2}, и получить дек, поддерживающий каждую операцию за
амортизированное время $O(1)$. Поскольку банковские очереди немного
проще, мы решили работать именно с ними.

Тип банковских деков в точности такой же, как у банковских очередей.
\begin{lstlisting}
  type $\alpha$ Queue = int $\times$ $\alpha$ Stream $\times$ int $\times$ $\alpha$ Stream
\end{lstlisting}
Функции, работающие с первым элементом, определены так:
\begin{lstlisting}
  fun cons (x, (lenf, f, lenr, r)) = check (lenf+1, $\$$Cons (x, f), lenr, r)
  fun head (lenf, $\$$Nil, lenr, $\$$Cons (x, _)) = x
    | head (lenf, $\$$Cons (x, f'), lenr, r) = x
  fun tail (lenf, $\$$Nil, lenr, $\$$Cons (x, _)) = empty
    | tail (lenf, $\\$Cons (x, f'), lenr, r) = check (lenf-1, f', lenr, r)
\end{lstlisting}
Первые варианты в определениях \lstinline!head! и \lstinline!tail!
обрабатывают одноэлементные деки, чей единственный элемент хранится в
хвостовом потоке. Функции, работающие с последним элементом~---
\lstinline!snoc!, \lstinline!last! и \lstinline!init!,~---
определяются симметричным образом.

Все интересное в этой реализации деков происходит во вспомогательной
функции \lstinline!check!, которая восстанавливает в деке идеальный
баланс, когда один из потоков оказывается чрезмерно длинным, сначала
обрезая более длинный поток так, чтобы его длина равнялась половине
суммарной длины двух списков, а затем перенося оставшиеся элементы
более длинного потока в конец более короткого. Например, если
$|\lstinline!f!| > c|\lstinline!r!| + 1$, то \lstinline!check!
заменяет \lstinline!f! на \lstinline!take (i, f)!, а \lstinline!r! на
\lstinline!r $\concat$ reverse (drop (i, f))!, где
$\lstinline!i! = \lfloor (|\lstinline!f!| + |\lstinline!r!|) /2 \rfloor$. Полное определение \lstinline!check! выглядит так:
\begin{lstlisting}
  fun check (q as (lenf, f, lenr, r)) =
       if lenf > c*lenr + 1 then
           let val i = (lenf + lenr) div 2	val j = lenf + lenr - i
               val f' = take (i, f) 		val r' = r $\concat$ reverse (drop (i, f))
           in (i, f', j, r') end
       else if lenr > c*lenf + 1 then
           let val j = (lenf + lenr) div 2	val i = lenf + lenr - j
               val r' = take (j, r)	        val f' = f $\concat$ reverse (drop (j, r))
           in (i, f', j, r') end
       else q
\end{lstlisting}
Полностью эта реализация приведена на Рис.~\ref{fig:8.3}.

\begin{figure}
  \centering

  \caption{Реализация деков, основанная на ленивой перестройке и методе банкира.}
  \label{fig:8.3}
\end{figure}

\begin{remark}
  Поскольку наша реализация симметрична, мы можем обратить дек за
  время $O(1)$, попросту поменяв \lstinline!f! и \lstinline!r! ролями.
  \begin{lstlisting}
    fun reverse (lenf, f, lenr, r) = (lenr, r, lenf, f)
  \end{lstlisting}
  Это свойство разделяют многие другие реализации деков
  \cite{Hoogerwoord1992, ChuangGoldberg1993}. Вместо того, чтобы
  повторять весь код для функций над первым и последним элементами,
  можно определить функции для последнего элемента через
  \lstinline!reverse! и функции для первого элемента. Например,
  \lstinline!init! можно реализовать как
  \begin{lstlisting}
    fun init q = reverse (tail (reverse q))
  \end{lstlisting}
  Разумеется, будучи реализована напрямую, \lstinline!init! немного быстрее.
\end{remark}

Для анализа наших деков мы снова обращаемся к методу банкира. Как для
головного, так и для хвостового потока, пусть $d(i)$ будет число
единиц долга, приписанных к $i$-му элементу потока, и пусть
$D(i) = \sum_{j=0}^i d(j)$. Будем поддерживать инвариант, что как для
головного, так и для хвостового потока
$$
D(i) \le \min(ci + i, cs + 1 - t)
$$
где $s = \min(|\lstinline!f!|,|\lstinline!r!|)$, а
$t = \max(|\lstinline!f!|, |\lstinline!r!|)$. Поскольку $d(0) = 0$,
головные элементы обоих потоков не имеют долга, и к ним всегда
можно обращаться функциями \lstinline!head! и \lstinline!last!.
\begin{theorem}\label{th:8.1}
  \lstinline!cons! и \lstinline!tail! (и, симметрично к ним,
  \lstinline!snoc! и \lstinline!init!) поддерживают инвариант долга
  как на головном, так и на хвостовом потоке, высвобождая,
  соответственно, не более 1 и $c+1$ единиц долга на поток.

  \emph{Доказательство.} Подобно доказательству Теоремы~\ref{th:6.1}
  на стр.~\pageref{th:6.1}.
\end{theorem}

Как теперь легко убедиться, у каждой операции нераздельная стоимость
равна $O(1)$, и, по Теореме~\ref{th:8.1}, каждая операция высвобождает
не более $O(1)$ единиц долга. Следовательно, все операции работают за
амортизированное время $O(1)$.

\begin{exercise}\label{ex:8.5}
  Докажите Теорему~\ref{th:8.1}.
\end{exercise}

\begin{exercise}\label{ex:8.6}
  Рассмотрите достоинства и недостатки при выборе различных значений
  константы $c$. Постройте последовательность операций, которая при $c
  = 4$ будет работать значительно быстрее, чем при $c = 2$. Затем
  постройте последовательность операций, которая будет значительно
  быстрее при $c = 2$, чем при $c = 4$.
\end{exercise}

\subsection{Деки реального времени}
\label{sc:8.4.3}

\term{Дек реального времени}{real-time deque} все операции выполняет
за $O(1)$ в худшем случае. Мы получаем деки реального времени на
основе деков из предыдущего раздела, снабжая головной и хвостовой
потоки расписаниями.

Как всегда, первый шаг в применении метода расписаний состоит в том,
чтобы преобразовать все монолитные функции в пошаговые. В предыдущей
нашей реализации трансформация перестройки заменяла \lstinline!f! и
\lstinline!r! на
\lstinline!f $\concat$ reverse (drop (j, r))! и
\lstinline!take (j, r)! (или наоборот). Функции \lstinline!take! и
$\concat$ уже являются пошаговыми, но \lstinline!reverse! и
\lstinline!drop! монолитны. Поэтому мы переписываем
\lstinline!f $\concat$ reverse (drop (j, r))! как
\lstinline!rotateDrop (f, j, r)!. \lstinline!rotateDrop! проводит $c$
шагов операции \lstinline!drop! на каждый шаг $\concat$, а в конце
зовет \lstinline!rotateRev!, которая, в свою очередь, выполняет $c$
шагов \lstinline!reverse! на каждый остающийся шаг
$\concat$. \lstinline!rotateDrop! можно реализовать как
\begin{lstlisting}
  fun rotateDrop (f, j, r) =
        if j < c then rotateRev (f, drop (j, r), $\$$Nil)
        else let val ($\$$Cons (x, xf')) = f
             in $\$$Cons (x, rotateDrop (f', j - c, drop (c, r))) end
\end{lstlisting}
Вначале $|\lstinline!r!| = c|\lstinline!f!| + 1 + k$, где $1 \le k \le
c$. При каждом вызове \lstinline!rotateDrop!, кроме последнего, мы отбрасываем $c$
элементов \lstinline!r! и обрабатываем один элемент \lstinline!f!. При
последнем вызове мы отбрасываем $j \mod c$ элементов \lstinline!r!, а
\lstinline!f! оставляем неизменным. Следовательно, при первом вызове
\lstinline!rotateRev! мы имеем $|\lstinline!r!| = c|\lstinline!f!| + 1
+ k - (j \mod c)$. Удобно будет, если $|\lstinline!r!|
\ge c|\lstinline!f!|$, так что мы требуем, чтобы $1 + k - (j \mod c)
\ge 0$. Это гарантировано только при $c < 4$. Поскольку $c$ должно
быть больше единицы, в качестве разрешённых значений $c$ остаются
только 2 и 3. Теперь мы можем реализовать \lstinline!rotateRev! как
\begin{lstlisting}
  fun rotateRev ($\$$Nil, r, a) = reverse r $\concat$ a
    | rotateRev ($\$$Cons (x, f), r, a) =
        $\$$Cons (x, rotateRev (f, drop (c, r), reverse (take (c, r)) $\concat$ a))
\end{lstlisting}
Заметим, что \lstinline!rotateDrop! и \lstinline!rotateRev! часто
вызывают \lstinline!drop! и \lstinline!reverse!~--- те самые функции,
которых мы хотели избежать. Однако теперь \lstinline!drop! и
\lstinline!reverse! всегда зовутся с аргументами ограниченного
размера, а следовательно, выполняются за $O(1)$ шагов.

После того, как монолитные функции преобразованы в пошаговые,
следующим шагом мы устанавливаем расписания для задержек внутри
\lstinline!f! и \lstinline!r!. Для каждого из этих потоков мы
поддерживаем отдельное расписание, и на каждом шаге выполняем по
несколько задержек из каждого расписания. Как и в очередях реального
времени из Раздела~\ref{sc:7.2}, наша цель состоит в том, чтобы оба
расписания были полностью выполнены ко времени следующего проворота,
чтобы задержки, вынуждаемые внутри \lstinline!rotateDrop! и
\lstinline!rotateRev!, были уже с гарантией мемоизированы.

\begin{exercise}\label{ex:8.7}
  Покажите, что если выполнять по одной задержке на каждую вставку и
  по две задержки на каждое изъятие элемента, то мы можем
  гарантировать, что оба расписания будут полностью выполнены ко
  времени следующего проворота.
\end{exercise}

Реализация полностью приведена на Рис.~\ref{fig:8.4}.

\begin{figure}
  \centering

  \caption{Деки реального времени с ленивой перестройкой и расписаниями.}
  \label{fig:8.4}
\end{figure}

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

\noindent
\textbf{Глобальная перестройка} Глобальная перестройка была впервые
предложена Овермарсом \cite{Overmars1983}. С тех пор она
использовалась во многих ситуациях, включая очереди реального времени
\cite{HoodMelville1981}, деки реального времени \cite{Hood1982,
  GajewskaTarjan1986, Sarnak1986, ChuangGoldberg1993}, деки с
конкатенацией \cite{BuchsbaumTarjan1995} и в задаче поддержания
порядка \cite{DietzSleator1987}.

\noindent
\textbf{Деки} Первым, кто адаптировал очереди реального времени из
\cite{HoodMelville1981} и получил деки реального времени, был Худ
\cite{Hood1982}. Эта работа была повторена ещё несколькими
исследователями \cite{GajewskaTarjan1986, Sarnak1986,
  ChuangGoldberg1993}. Все эти реализации похожи на методы,
используемые для эмуляции машин Тьюринга с несколькими головками
\cite{Stoss1970, FischerMeyerRosenberg1972,
  LeongSeiferas1981}. Хогерворд \cite{Hoogerwoord1992} предложил
амортизированные деки на основе порционной перестройки, однако, как и
всегда при порционной перестройке, его реализация
неэффективна, будучи использованной в качестве устойчивой структуры. Деки
реального времени с Рис.~\ref{fig:8.4} впервые появились в
\cite{Okasaki1995c}.

\noindent
\textbf{Сопрограммы и ленивое вычисление} Потоки (и другие ленивые
структуры данных) часто использовались для реализации сопрограмм между
источником данных в потоке и потребителем этих данных. Ландин
\cite{Landin1965} был первым, кто указал на связь между потоками и
сопрограммами. Некоторые убедительные примеры использования этой
конструкции можно найти у Хьюза \cite{Hughes1989}.

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