chapter06.tex

\chapter{Сочетание амортизации и устойчивости через ленивое
  вычисление}
\label{ch:6}

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

\section{Трассировка вычисления и логическое время}
\label{sc:6.1}

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

Мы моделируем логическое время при помощи \term{трассировок
  вычисления}{execution traces}, которые представляют абстракцию
истории выполнения программы. Трассировка вычисления представляет собой
направленный граф, вершины которого соответствуют операциям, которые
нас интересуют; как правило, это только операции модификации над
рассматриваемым типом данных. Дуга от вершины $v$ к вершине $v'$
означает, что операция $v'$ использует результат операции
$v$. \term{Логической историей}{logical history} операции $v$
(обозначается $\hat{v}$) называется
множество всех операций, от которых зависит её результат (включая и
саму операцию $v$). Другими словами, $\hat{v}$~--- множество вершин
$w$, таких, что существует путь (возможно, длины 0) от $w$ до $v$.
\term{Логическим будущим}{logical future} вершины $v$ называется любой
путь от $v$ до конечной вершины (т.~е., вершины с числом исходящих дуг
0). Если таких путей больше одного, значит, вершина $v$ имеет
несколько логических будущих. Иногда мы говорим о логической истории
или логическом будущем объекта, имея при этом в виду логическую
историю или будущее операции, создавшей этот объект.

\begin{exercise}\label{ex:6.1}
  Нарисуйте трассировку вычисления для следующей последовательности
  операций. Пометьте каждую вершину в графе количеством её логических
  будущих.
  \begin{lstlisting}
    val a = snoc (empty, 0)
    val b = snoc (a, 1)
    val c = tail b
    val d = snoc (b, 2)
    val e = c $\concat$ d
    val f = tail c
    val g = snoc (d, 3)
  \end{lstlisting}
\end{exercise}
Понятие трассировки вычисления обобщает \term{графы версий}{version
  graphs} \cite{Driscoll-etal1989}, часто используемые для
моделирования историй устойчивых структур данных. В графе версий
вершины представляют различные версии единой устойчивой структуры, а
дуги соответствуют зависимостям между этими версиями.  Таким образом,
графы версий моделируют результаты операций, а трассировки
вычисления~--- операции сами по себе. Трассировки вычисления часто
оказываются удобнее, если надо совместить истории нескольких
устойчивых объектов (возможно, даже разных типов), а также для
рассуждений об операциях, не изменяющих версию объекта (например, о
запросах) либо возвращающих несколько результатов (скажем, разбивающих
список на два подсписка).

Для эфемерных структур данных, как правило, число исходящих дуг в
графе версий или в трассировке вычисления должно быть не более
единицы; это отражает ограничение, что каждая структура может
модифицироваться не более одного раза.  Для моделирования различных
вариантов устойчивости графы версий могут позволять числу исходящих
дуг вершины быть каким угодно, но вводить другие
ограничения. Например, часто требуют, чтобы графы версий были
деревьями (или лесами), говоря, что число входящих дуг для каждой
вершины не может превышать 1. Или же разрешается больше одной входящей
дуги у вершины, но запрещаются циклы, и таким образом, граф
оказывается направленным ациклическим графом. Мы никаких таких
ограничений для трассировок выполнения устойчивых структур данных не
накладываем. Вершины с числом входящих дуг более одной соответствуют
операциям, принимающим более одного аргумента, например, конкатенации
списков или объединению множеств. Циклы возникают для рекурсивно
определенных объектов, которые поддерживаются во многих ленивых
языках. Разрешено даже иметь несколько дуг между одними и теми же
вершинами, например, когда список конкатенируется сам с собой.

Трассировки вычисления будут использоваться в Разделе~\ref{sc:6.3.1},
где мы расширяем метод банкира для работы с устойчивыми структурами.

\section{Сочетание амортизации и устойчивости}
\label{sc:6.2}

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

\subsection{Роль ленивого вычисления}
\label{sc:6.2.1}

Напомним, что \term{дорогой}{expensive} называется операция, чья
реальная стоимость превышает её (желательную) амортизированную
стоимость. Предположим, к примеру, что некоторый вызов функции
\lstinline!f x!
является дорогим. При наличии устойчивости вредоносный противник может
вызывать \lstinline!f x! сколь угодно часто. (Заметим, что каждый
такой вызов образует новое логическое будущее \lstinline!x!.) Если
каждая такая операция занимает одно и то же время, амортизированные
ограничения на время вычисления деградируют до наихудших
ограничений. Следовательно, нам надо добиться того, чтобы даже если
первое вычисление \lstinline!f x! окажется дорогим, последующие вызовы
таковыми не были.

При программировании без побочных эффектов такая цель недостижима ни
при вызове по значению (т.~е., при аппликативном порядке вычислений),
ни при вызове по имени (т.~е., при ленивом вычислении без мемоизации),
поскольку всякое применение функции \lstinline!f! к аргументу
\lstinline!x! занимает одно и то же время. Следовательно, амортизацию
невозможно выгодно совместить с устойчивостью в языках, поддерживающих
только эти два порядка вычисления.

Однако рассмотрим теперь вызов по необходимости (т.~е., ленивое
вычисление с мемоизацией). Если \lstinline!x! содержит задержанный
компонент, необходимый для вычисления \lstinline!f!, первое применение
\lstinline!f! к \lstinline!x! вынудит (возможно, дорогое) вычисление
этого компонента и запомнит результат. Последующие операции смогут
обращаться к результату напрямую. Ровно это нам и требовалось!

\begin{remark}
  Будучи однажды обнаруженной, связь ленивого вычисления и амортизации
  кажется естественной. Ленивое вычисление можно рассматривать как
  разновидность самомодификации, а самомодификация часто используется
  при амортизации \cite{SleatorTarjan1985, SleatorTarjan1986b}. Однако
  ленивое вычисление является особым образом ограниченной
  разновидностью самомодификации~--- не все виды самомодификации,
  используемые в амортизированных эфемерных структурах данных, могут
  быть выражены при помощи ленивого вычисления. В частности,
  расширяющиеся деревья, по-видимому, этому методу неподвластны.
\end{remark}
\subsection{Общая методика анализа ленивых структур данных}
\label{sc:6.2.2}

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

Стоимость каждой операции мы разбиваем на несколько категорий. Во-первых,
\term{нераздельная}{unshared} стоимость операции~--- это время,
требуемое операции в предположении, что все задержки в системе уже
вынуждены и мемоизированы ко времени её начала (т.~е., в
предположении, что \lstinline!force! всегда занимает время $O(1)$, за
исключением тех задержек, которые создаются и вынуждаются в процессе
выполнения самой операции). \term{Разделяемая}{shared} стоимость
операции~--- это время, требуемое для выполнения всех задержек,
создаваемых, но не вынуждаемых операцией (при тех же предположениях,
что и раньше). Наконец, \term{полная}{complete} стоимость операции
есть сумма её нераздельной и разделяемой стоимости. Заметим, что
полная стоимость операции равна её стоимости, если бы ленивое
вычисление было заменено на аппликативное.

Кроме того, мы разбиваем разделяемую стоимость последовательности
операций на реализованную и
нереализованную. \term{Реализованная}{realized} стоимость есть
стоимость задержек, которые вынуждаются в процессе полного
вычисления. \term{Нереализованная}{unrealized} стоимость~--- стоимость
задержек, которые так и остаются невыполненными. \term{Общая
  реальная}{total actual} стоимость последовательности операций
равняется сумме общей нераздельной стоимости и реализованной
разделяемой стоимости~--- нереализованные вычисления не влияют на
общую стоимость. Заметим, что доля каждой операции в общей реальной
стоимости не меньше её нераздельной стоимости и не больше её полной
стоимости, в зависимости от того, какая доля разделяемой стоимости
реализуется.

Мы будем учитывать разделяемую стоимость с помощью понятия
\term{текущего долга}{accumulated debt}.  В начале вычисления долг
равен нулю, но каждый раз, когда создается задержка, он увеличивается
на разделяемую стоимость этой задержки (а также вложенных в неё
задержек). Впоследствии каждая операция выплачивает часть текущего
долга. \term{Амортизированная стоимость}{amortized cost} операции
равна сумме её нераздельной стоимости и количества выплаченного этой
операцией долга. Нам запрещается вынуждать задержку, прежде чем
полностью выплачен связанный с ней долг.

\begin{remark}
  Амортизационный анализ на основе понятия текущего долга во многом
  работает как \term{отложенная покупка}{layaway plan}. В случае
  отложенной покупки вы находите в магазине некоторый товар~---
  например, кольцо с бриллиантом,~--- который вы не можете позволить себе
  немедленно. Вы договариваетесь с магазином о цене и просите персонал
  отложить для вас кольцо. Затем вы производите регулярные платежи, и
  получаете кольцо только тогда, когда его цена полностью выплачена.

  При анализе ленивой структуры данных вы имеете вычисление, которое
  пока что не можете позволить себе немедленно. Вы создаете для этого
  вычисления задержку и присваиваете ей размер долга, пропорциональный
  её разделяемой стоимости. Затем вы выплачиваете долг небольшими
  порциями. Наконец, когда долг полностью выплачен, вам позволено
  произвести вычисление задержки.
\end{remark}

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

Одна из наиболее трудных проблем при анализе времени выполнения
ленивых программ~--- взаимодействие множественных логических
будущих. Мы избегаем этой проблемы, рассуждая о каждом из этих будущих
\emph{как если бы оно было единственным}. С точки зрения операции,
создающей задержку, каждое логическое будущее, эту задержку
вынуждающее, обязано само её оплатить. Если два логических будущих
желают вынудить одну и ту же задержку, каждое из них платит за неё по
отдельности. Сговориться и выплатить долг по частям не
разрешается. Альтернативный взгляд на это ограничение состоит в том,
что задержку разрешается вынуждать \emph{только тогда, когда ее
  стоимость оплачена в рамках логической истории текущей операции}.
При использовании этого метода иногда мы будем выплачивать долг более
одного раза, и следовательно, переоценивать общее время, необходимое
для некоторых вычислений. Однако такая переоценка безвредна, и её цена
невелика по сравнению с простотой получаемого анализа.

\section{Метод банкира}
\label{sc:6.3}

Чтобы приспособить метод банкира к использованию понятия текущего
долга вместо текущих накоплений, мы заменяем кредит дебетом. Каждая
единица долга представляет определенное количество отложенной
работы. Когда мы вначале задерживаем какое-то вычисление, мы создаём
дебет, равный разделяемой стоимости этого вычисления, и распределяем
долг по узлам созданного объекта.  Выбор места, с которым связывается
каждая единица долга, зависит от природы вычисления. Если оно
\term{монолитно}{monolithic} (то есть, будучи однажды запущено,
сработает до завершения), обычно весь долг присваивается корневому
узлу результата. С другой стороны, если мы имеем дело с
\term{пошаговым}{incremental} вычислением (то есть, оно разбивается
на фрагменты, которые можно выполнить независимо друг от друга), то
долг может распределяться по корневым узлам частичных результатов.

Амортизированная стоимость операции равна её нераздельной стоимости
плюс количество единиц долга, освобождаемых этой операцией. Обратите
внимание, что единицы долга, создаваемые операцией, в ее
амортизированную стоимость \emph{не включаются}. Порядок, в котором
высвобождаются единицы долга, зависит от того, как предполагается в
будущем обращаться к узлам объекта; долг на тех узлах, к которым мы
обратимся раньше, следует выплачивать в первую очередь. Чтобы
доказать ограничение амортизированной стоимости операции, нам нужно
показать, что всякий раз, как мы обращаемся к некоторой ячейке
(возможно, при этом вынуждая некоторую задержку), все единицы долга,
привязанные к этой ячейке, уже высвобождены (а следовательно,
задержанная операция полностью оплачена). Таким образом, мы
гарантируем, что общее количество долга, высвобожденное
последовательностью операций, является верхней границей реализованной
разделяемой стоимости этих операций. Следовательно, общая
амортизированная стоимость является верхней границей общей реальной
стоимости. Долг, сохраняющийся в конце вычислений, соответствует
нереализованной разделяемой стоимости, и не влияет на общую реальную
стоимость.

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

\subsection{Обоснование метода банкира}
\label{sc:6.3.1}

В этом разделе мы доказываем утверждение, что общая амортизированная
стоимость является верхней границей общей реальной стоимости. Общая
амортизированная стоимость равна сумме общей нераздельной стоимости и
общего количества высвобожденного долга (включая повторные
высвобождения); общая реальная стоимость равна общей нераздельной
стоимости плюс реализованная разделяемая стоимость. Следовательно, нам
надо показать, что общее количество высвобожденного долга является
верхней границей для реализованной разделяемой стоимости.

Можно абстрактно рассматривать метод банкира как задачу разметки графа
трассировки вычисления из Раздела~\ref{sc:6.1}. Задача состоит в том,
чтобы каждую вершину графа пометить тремя (мульти)множествами $s(v)$,
$a(v)$ и $r(v)$, так что
$$
\begin{array}{cl}
  (I) & v \ne v' \Rightarrow s(v) \cap s(v') = \emptyset \\
  (II) & a(v) \subseteq \bigcup_{w \in \hat{v}} s(w) \\
  (III) & r(v) \subseteq \bigcup_{w \in \hat{v}} a(w) \\
\end{array}
$$
$s(v)$ является множеством, но $a(v)$ и $r(v)$ могут быть
мультимножествами (т.~е., могут содержать повторения). Условия II и
III не учитывают эти повторения.

$s(v)$~--- это множество дебетов, выделяемых операцией $v$. Условие I
утверждает, что никакая единица долга не выделяется более одного
раза. $a(v)$~--- множество дебетов, высвобождаемых операцией
$v$. Условие II требует, чтобы всякая высвобождаемая единица долга
была заранее выделена; точнее, операция может высвобождать только
единицы долга, которые были выделены в её логической
истории. Наконец, $r(v)$~--- это единицы долга,
\term{реализуемые}{realized} операцией $v$, то есть, мультимножество
единиц долга, соответствующее задержкам, которые вынуждаются операцией
$v$. Условие III требует, чтобы всякая единица долга была
высвобождена, прежде чем она реализована, или, точнее, что нельзя
реализовать единицу долга, если она не высвобождена в логической
истории текущей операции.

Почему $a(v)$ и $r(v)$ являются не просто множествами, а
мультимножествами? Потому что одна и та же операция может высвободить
одни и те же единицы долга более одного раза или реализовать их более
одного раза (многократно вынудив одни и те же задержки). Несмотря на
то, что мы никогда не имеем намерения высвободить одни и те же единицы долга
многократно, при сочетании объекта с самим собой это может произойти.
Предположим, например, что в анализе функции конкатенации списков мы
высвобождаем какое-то количество единиц долга из первого аргумента и
какое-то из второго. Если мы будем строить конкатенацию списка с самим
собой, возможно, одни и те же единицы долга окажутся высвобожденными
дважды.

При таком абстрактном взгляде на метод банкира мы легко можем измерить
различные показатели стоимости вычисления. Пусть $V$ будет множество
всех вершин в трассировке вычисления. В таком случае общая разделяемая
стоимость равна $\sum_{v \in V}|s(v)|$, а общее количество
высвобожденного долга равно $\sum_{v \in V}|a(v)|$. Поскольку имеется
мемоизация, реализованная разделяемая стоимость равна не
$\sum_{v \in V}|r(v)|$, а $\bigcup_{v \in V}|r(v)|$, где операция $\bigcup$
отбрасывает повторения. Таким образом, многократно вынужденная
задержка участвует в реальной стоимости только один раз. Согласно
Условию III, мы знаем, что
$\bigcup_{v \in V}r(v) \subseteq \bigcup_{v \in V}
a(v)$. Следовательно,
$$
|\bigcup_{v \in V} r(v)| \le |\bigcup_{v \in V} a(v)| \le \sum_{v \in V} |a(v)|
$$
Таким образом, реализованная разделяемая стоимость ограничена сверху
общим количеством высвобожденного долга, а общая реальная стоимость
ограничена общей амортизированной стоимостью, что и требовалось
доказать.

\begin{remark}
  В этом рассуждении ещё раз подчеркивается важность мемоизации. Без
  мемоизации (то есть, при вызове по имени вместо вызова по
  необходимости) общая реализованная стоимость была бы равна
  $\sum_{v \in V} |r(v)|$, и не было бы никаких причин считать, что
  она меньше, чем $\sum_{v \in V} |a(v)|$.
\end{remark}

\subsection{Пример: очереди}
\label{sc:6.3.2}

В этом подразделе мы разрабатываем эффективную устойчивую реализацию
очередей и доказываем методом банкира, что все операции занимают амортизированное время
$O(1)$.

Как видно из обсуждения в предыдущем разделе, мы должны каким-то
образом внести в устройство нашей структуры данных ленивое вычисление,
так что мы заменяем пару списков из простых очередей
(Раздел~\ref{sc:5.2}) на пару потоков\footnote{Было
  бы достаточно заменить потоком только список-голову, однако для
  простоты мы заменяем оба списка.%
}.
Для упрощения дальнейшей работы мы также явно отслеживаем длину обоих
этих потоков.
\begin{lstlisting}
  type $\alpha$ Queue = int $\times$ $\alpha$ Stream $\times$ int  $\times$ $\alpha$ Stream
\end{lstlisting}
Первое целое число здесь~--- длина головного потока, а второе~---
длина хвостового потока. Заметим, что, в качестве приятного побочного
эффекта, благодаря явному хранению информации о длине мы тривиальным
образом можем
поддержать функцию \lstinline!size! (размер) с константным временем выполнения.

Если мы будем, прежде чем обратить хвостовой список, ждать, пока
головной опустеет, у нас не окажется достаточно времени, чтобы
заплатить за обращение. Вместо этого мы периодически
\term{проворачиваем}{rotate} очередь, заменяя \lstinline!f! на
\lstinline!f $\concat$ reverse r!, и делая хвостовой поток
пустым. Заметим, что это преобразование не меняет относительный порядок
элементов.

Когда следует проворачивать очередь? Напомним, что функция
\lstinline!reverse! монолитна. Следовательно, её вычисление должно
быть спланировано достаточно сильно заранее, чтобы ко времени, когда
оно понадобится, весь её долг был высвобожден. Вычисление
\lstinline!reverse! занимает $|r|$ шагов, так что, чтобы учесть её
цену, мы выделяем $|r|$ единиц долга (пока что игнорируя цену
операции $\concat$). Задержка \lstinline!reverse! может быть вынуждена
самое раннее после $|f|$ применений \lstinline!tail!, так что, если мы
провернем очередь в момент, когда $|r| \approx |f|$ и высвободим по
одной единице долга на каждое применение \lstinline!tail!, ко времени
исполнения \lstinline!reverse! долг будет выплачен.  Так что мы
проворачиваем очередь, когда $r$ становится на единицу длиннее $f$, и
поддерживаем инвариант $|f| > |r|$. Между прочим, это гарантирует нам,
что $f$ может быть пустым только при пустом $r$, как и в простых
очередях из Раздела~\ref{sc:5.2}. Основные функции работы с очередями
теперь записываются так:
\begin{lstlisting}
  fun snoc ((lenf, f, lenr, r), x) = check (lenf, f, lenr+1, $\$$Cons (x, r))
  fun head (lenf, $\$$Cons (x, f'), lenr, r) = x
  fun tail (lenf, $\$$Cons (x, f'), lenr, r) = check (lenf-1, f', lenr, r)
\end{lstlisting}
где вспомогательная функция \lstinline!check! обеспечивает $|f| \ge |r|$.
\begin{lstlisting}
  fun check (q as (lenf, f, lenr, r) =
        if lenr $\le$ lenf then q else (lenf+lenr, f $\concat$ reverse r, 0, $\$$Nil)
\end{lstlisting}
Полный программный код этой реализации приведен на Рис.~\ref{fig:6.1}.
\begin{figure}
  \centering

  \caption{Амортизированные очереди с использованием метода банкира.}
  \label{fig:6.1}
\end{figure}

Чтобы лучше объяснить, как эта реализация эффективно справляется с
устойчивостью, рассмотрим следующий сценарий. Пусть имеется очередь
$q_0$, чьи головной и хвостовой потоки каждый имеют длину $m$, и пусть
$q_i = \lstinline!tail! q_{i-1}$ для $0 < i \le m+1$. Очередь
проворачивается при первом вызове \lstinline!tail!, а задержка
\lstinline!reverse!, созданная при провороте, вынуждается при последнем
вызове \lstinline!tail!. Обращение занимает $m$ шагов, и его стоимость
амортизируется по цепочке $q_1\ldots q_m$. (Пока что мы заботимся
только о стоимости \lstinline!reverse! и игнорируем стоимость
$\concat$.)

Выберем теперь какую-нибудь точку ветвления $k$ и повторим вычисление
от $q_k$ до $q_{m+1}$. (Заметим, что $q$ используется как устойчивая
структура.) Сделаем это $d$ раз. Как часто выполняется
\lstinline!reverse!? Зависит от того, находится ли точка ветвления $k$
до или после проворачивания очереди. Допустим, $k$ расположена после
проворота. Допустим даже, что $k = m$, так что каждая из повторяющихся
ветвей представляет собой простое взятие хвоста очереди. Каждая из
ветвей выполнения вынуждает задержку \lstinline!reverse!, но все они
вынуждают \emph{одну и ту же} задержку, так что функция
\lstinline!reverse! выполняется только один раз. Здесь ключевую роль
играет мемоизация~--- без неё вычисление \lstinline!reverse!
повторялось бы каждый раз, и общая стоимость составила бы $m(d+1)$
шагов, при том, что для её амортизации у нас есть всего лишь $m + 1 +
d$ операций. При большом $d$ получилась бы амортизированная стоимость
операции $O(1)$, но мемоизация дает нам амортизированную стоимость
операции всего лишь $O(1)$.

Возможна, однако, и ситуация, когда вычисление \lstinline!reverse!
будет повторяться. Надо только взять $k = 0$ (т.~е., расположить точку
ветвления прямо перед проворотом очереди.) В этом случае первый вызов
\lstinline!tail! на каждой ветке выполнения повторяет проворот и
создает новую задержку \lstinline!reverse!. Эта новая задержка
вынуждается при последнем вызове \lstinline!tail! на каждой ветке, и
функция \lstinline!reverse! вычисляется заново. Поскольку все задержки
различны, мемоизация здесь не приносит никакой пользы. Полная
стоимость всех обращений равна \lstinline!m $\cdot$ d!, но теперь у нас
для амортизации этой стоимости есть $(m + 1)(d + 1)$ операций, и опять
амортизированная стоимость каждой операции получается $O(1)$. Главное,
что здесь следует заметить~--- это
 что мы повторяем работу только в том
случае, если повторяем и последовательность операций, по которым мы
распределяем амортизированную стоимость этой работы.

Это неформальное рассуждение показывает, что наши очереди требуют
амортизированное время $O(1)$ на каждую операцию, даже если они
используются как устойчивая структура. Мы переводим это рассуждение в
формальное доказательство с помощью метода банкира.

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

Пусть размер долга на $i$-ом узле головного списка будет $d(i)$, и
пусть $D(i) = \sum_{j=0}^i d(j)$~--- кумулятивный размер долга на
узлах от начала очереди до $i$ включительно. Мы будем соблюдать
следующий \emph{инвариант долга}:
$$
D(i) \le \min(2i, |f| - |r|)
$$
Подвыражение $2i$ гарантирует нам, что весь долг на первом узле
головного потока уже высвобожден (поскольку $d(0) = D(0) \le 2 \cdot 0
= 0$), так что этот узел можно спокойно вынуждать (операциями
\lstinline!head! или \lstinline!tail!). Подвыражение $|f| - |r|$
гарантирует, что весь долг во всей очереди высвобожден к моменту,
когда потоки имеют одинаковую длину, что бывает перед следующим
проворотом очереди.

\begin{theorem}\label{th:6.1}
  Операции \lstinline!snoc! и \lstinline!tail! сохраняют инвариант
  долга, высвобождая, соответственно, одну и две единицы.

  \noindent
  \textit{Доказательство.} Операция \lstinline!snoc!, не вызывающая
  проворот, просто добавляет один элемент к хвостовому потоку, и таким
  образом, увеличивает на один величину $|r|$ и уменьшает на один $|f|
  - |r|$. При этом инвариант оказывается нарушен в узлах, где до сих
  пор мы имели $D(i) = |f| - |r|$. Мы можем восстановить этот
  инвариант, высвободив первую единицу долга в очереди; при этом
  кумулятивный долг на всех последующих узлах уменьшится на единицу.
  Подобным образом, если операция \lstinline!tail! не вызывает
  проворота очереди, она просто отбрасывает элемент из головного
  потока. При этом $|f|$ уменьшается на единицу (а следовательно, и
  $|f| - |r|$), однако, что более важно, индекс $i$ всех остающихся
  узлов уменьшается на один, а следовательно, $2i$ уменьшается на
  два. Высвобождение первых двух единиц долга в очереди
  восстанавливает инвариант. Наконец, рассмотрим операцию
  \lstinline!snoc! или \lstinline!tail!, которая вызывает проворот
  очереди. Перед самым проворотом мы знаем, что весь долг в очереди
  высвобожден, так что после него единственные невысвобожденные
  единицы долга порождены самим этим проворотом. Если на момент
  проворота $|f| = m$ и $|r| = m+1$, то мы создаём $m$ единиц долга
  для конкатенации и $m+1$ для операции \lstinline!reverse!.
  Конкатенация~--- пошаговая операция, так что мы распределяем ее
  долг по единице на каждый из первых $m$ узлов. С другой стороны,
  функция \lstinline!reverse! монолитна, так что все её $m+1$ единиц
  долга мы помещаем в узел $m$, первый узел обращенного потока. Таким
  образом, долг теперь распределен так, что
  $$
  \begin{array}{lcl}
    d(i) = \left\{
    \begin{array}[c]{ll}
      1 & \mbox{если $i < m$}\\
      m+1 & \mbox{если $i = m$}\\
      0 & \mbox{если $i > m$}\\
    \end{array}
    \right.
    & \mbox{и} &
    D(i) = \left\{
      \begin{array}[c]{ll}
        i+1 & \mbox{если $i < m$} \\
        2m+1 & \mbox{если $i \ge m$} \\
      \end{array}
    \right.
  \end{array}
  $$
  Это распределение нарушает инвариант в узлах 0 и $m$. Однако после
  высвобождения единицы долга в узле 0 инвариант в обоих этих узлах
  оказывается восстановлен.
\end{theorem}

Это рассуждение имеет стандартную структуру. Единицы долга
распределяются по нескольким узлам для пошаговых функций и
концентрируются в одном узле для монолитных. Инварианты долга
измеряют не только количество его единиц в каждой конкретной вершине,
но и размер долга на пути от корневого узла к этой вершине. Это
отражает наблюдение, что для доступа к любому узлу мы должны сначала
пройти через всех его предков. Следовательно, к этому времени долг на
всех этих узлах тоже должен быть равен нулю.

Эта структура данных демонстрирует также тонкую деталь, касающуюся
вложенных задержек: долг для вложенной задержки может быть выделен и
даже высвобожден прежде, чем задержка физически создается. Рассмотрим,
например, как работает операция $\concat$. Задержка для второго узла
потока физически создается только при вынуждении первого. Однако из-за
мемоизации задержка для второго узла будет разделяться между ветвями
вычисления всегда, когда разделяется задержка для
первого. Следовательно, мы считаем, что неявно вложенная задержка
создается тогда, когда создается задержка, в которую она вложена.
Более того, когда мы рассуждаем о долге или вообще о структуре
объекта, нас не интересует, создан ли узел физически или нет. Мы
рассуждаем так, будто бы все узлы были созданы в своем
окончательном виде, т.~е., как будто все задержки в объекте уже были
вынуждены.

\begin{exercise}\label{ex:6.2}
  Допустим, мы изменим инвариант очереди с формулы $|f| > |r|$ на $2|f| >
  |r|$.
  \begin{enumerate}
  \item Докажите, что амортизированные ограничения $O(1)$ по-прежнему
    выполняются.
  \item Сравните производительность двух реализаций при
    последовательной вставке ста элементов через \lstinline!snoc!, а
    затем их последовательном удалении через \lstinline!tail!.
  \end{enumerate}
\end{exercise}

\subsection{Наследование долга}
\label{sc:6.3.3}

Часто мы создаём задержки, чьи тела вынуждают другие, существующие
задержки. В таких случаях мы говорим, что новая задержка
\term{зависит}{depends} от старой. В примере с очередью задержка,
создаваемая операцией \lstinline!reverse r!, зависит от \lstinline!r!,
а задержка, создаваемая \lstinline!f $\concat$ reverse r!, зависит от
\lstinline!f!.  Каждый раз, когда мы вынуждаем задержку, следует быть
уверенными, что высвобожден не только долг, относящийся к ней самой,
но и долг всех задержек, от которых она зависит. В примере с очередью
инвариант долга гарантирует, что мы создаём задержки через $\concat$ и
\lstinline!reverse! только в случаях, когда ранее существующие
задержки уже полностью оплачены. Однако так будет не всегда.

Когда мы создаём задержку, зависящую от существующей задержки с
невысвобожденным долгом, мы переносим этот долг на новую задержку и
говорим, что новая задержка \term{наследует}{inherits} долги
старой. Мы не имеем права вынуждать новую задержку, пока мы не
высвободили как её собственные долги, так и унаследованные от старой
задержки. В методе банкира не делается никакого различия между этими
двумя разновидностями долга; считается, что весь долг принадлежит
новой задержке. Наследование долга будет применяться при анализе
структур данных из Глав~\ref{ch:9}, \ref{ch:10} и \ref{ch:11}.

\begin{remark}
  Наследование долга предполагает, что не существует способа доступа к
  более старой задержке внутри текущего объекта в обход новой. К
  примеру, наследование долга нельзя использовать при анализе следующей
  функции, применяемой к паре потоков:
  \begin{lstlisting}
    fun reverseSnd (xs, ys) = (reverse ys, ys)
  \end{lstlisting}
  Здесь \lstinline!ys! может быть вынуждена как через первый компонент
  пары, так и через второй. В таких случаях мы либо удваиваем долг,
  связанный с \lstinline!ys!, и новая задержка наследует копию долга,
  либо сохраняем одну копию каждой единицы долга и отслеживаем
  зависимости явно.
\end{remark}

\section{Метод физика}
\label{sc:6.4}

Подобно методу банкира, метод физика тоже можно адаптировать для работы
с понятием текущего долга вместо текущих накоплений.  В традиционном
методе физика описывается функция потенциала $\Phi$, представляющая
нижнюю границу текущих накоплений. Чтобы работать с долгом вместо
накоплений, мы заменяем $\Phi$ на функцию $\Psi$, которая сопоставляет
объектам потенциалы, представляющие верхнюю границу текущего долга
(или, по крайней мере, долю общего долга, относящуюся к
рассматриваемому объекту).  Грубо говоря, после этого амортизированная
стоимость операции определяется как её полная стоимость (т.~е.,
разделенная стоимость плюс нераздельная) минус изменение
потенциала. Напомним, что простейший способ рассчитать полную
стоимость операции~--- притвориться, что все вычисление работает
аппликативно.

Всякое изменение текущего долга отражается в изменении потенциала.
Если операция не выплачивает никакую долю разделенной стоимости, то
изменение потенциала равно её разделенной стоимости, и, следовательно,
амортизированная стоимость операции равна её нераздельной стоимости. С
другой стороны, если операция выплачивает часть своей разделяемой
стоимости, или разделяемой стоимости предыдущих операций, тогда
изменение потенциала будет меньше, чем её разделяемая стоимость
(т.~е., текущий долг увеличивается меньше, чем на её разделяемую
стоимость), и амортизированная стоимость операции окажется больше, чем
нераздельная. Однако амортизированная стоимость операции не может быть
меньше, чем её нераздельная стоимость, так что мы не позволяем
потенциалу изменяться больше, чем на разделяемую стоимость операции.

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

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

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

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

\subsection{Пример: биномиальные кучи}
\label{sc:6.4.1}

В Главе~\ref{ch:5} мы показали, что биномиальные кучи из
Раздела~\ref{sc:3.2} поддерживают операцию \lstinline!insert! за
амортизированное время $O(1)$. Однако если кучи используются как
устойчивая структура, этот показатель для худшего случая деградирует
до $O(\log n)$.  С помощью ленивого вычисления мы можем восстановить
амортизированное ограничение по времени $O(1)$ вне зависимости от
того, используются ли кучи как устойчивая структура.

Основная идея состоит в том, чтобы заменить в представлении кучи
список деревьев на задержанный список деревьев.
\begin{lstlisting}
  type Heap = Tree list susp
\end{lstlisting}
При этом мы можем переписать \lstinline!insert! в виде
\begin{lstlisting}
  fun lazy insert (x, $\$$ts) = $\$$insTree (Node (0, x, []), ts)
\end{lstlisting}
или, эквивалентным образом, в виде
\begin{lstlisting}
  fun insert (x, h) = $\$$insTree (Node (0, x, []), force h)
\end{lstlisting}
Остальные функции столь же просты в написании; они показаны на
Рис.~\ref{fig:6.2}.

\begin{figure}
  \centering

  \caption{Ленивые биномиальные кучи.}
  \label{fig:6.2}
\end{figure}

Проанализируем амортизированное время работы
\lstinline!insert!. Поскольку это монолитная операция, мы можем
использовать метод физика. Сначала определяем функцию потенциала как
$\Psi(h) = Z(|h|)$, где $Z(n)$~--- число нулей в двоичном
представлении $n$ (минимальной длины). Затем мы покажем, что
амортизированная стоимость вставки элемента в биномиальную кучу
размера $n$ равна двум.  Допустим, что $k$ младших разрядов в двоичном
представлении $n$ равны единице. Тогда полная стоимость операции
\lstinline!insert! пропорциональна $k + 1$, поскольку включает $k$
вызовов операции \lstinline!link!.  Рассмотрим теперь изменение
потенциала. Младшие $k$ разрядов изменяются с единиц на нули, а одна
следующая цифра изменяется с нуля на единицу, так что изменение
потенциала равно $k - 1$. Амортизированная стоимость получается
$(k + 1)  - (k - 1) = 2$.

\begin{remark}
  Заметим, что наше доказательство двойственно по отношению к
  доказательству из Раздела~\ref{sc:5.3}. Тогда
  потенциал равнялся количеству единиц в двоичном представлении $n$,
  теперь это количество нулей. Такая зеркальность отражает двойственность
  между понятиями текущих накоплений и текущего долга.
\end{remark}

\begin{exercise}\label{ex:6.3}
  Докажите, что \lstinline!findMin!, \lstinline!deleteMin! и
  \lstinline!merge! также выполняются за амортизированное время
  $O(\log n)$.
\end{exercise}

\begin{exercise}\label{ex:6.4}
  Допустим, мы уберем ключевое слово \lstinline!lazy! из определений
  функций \lstinline!merge! и \lstinline!deleteMin!, так что эти
  функции будут вычислять свои аргументы немедленно. Покажите, что обе
  они по-прежнему выполняются за время $O(\log n)$.
\end{exercise}

\begin{exercise}\label{ex:6.5}
  Задержка списка деревьев имеет неприятное последствие: время работы
  \lstinline!isEmpty! деградирует от $O(1)$ в худшем случае до
  амортизированного $O(\log n)$. Восстановите время работы $O(1)$ для
  \lstinline!isEmpty! путем явного хранения размера каждой
  кучи.  Вместо того, чтобы явно модифицировать нашу теперешнюю
  реализацию, напишите функтор \lstinline!SizedHeap!, подобный
  \lstinline!ExplicitMin! из Упражнения~\ref{ex:3.7}. Он должен
  преобразовывать произвольную реализацию кучи в реализацию, которая
  явно хранит размер.
\end{exercise}

\subsection{Пример: очереди}
\label{sc:6.4.2}

В этом разделе мы приспосабливаем под метод физика нашу реализацию
очередей. Как и раньше, мы показываем, что все операции занимают
амортизированное время $O(1)$.

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

Поскольку головной список задержан, мы не можем получить доступ к его
первому элементу, не выполнив всю задержку целиком.  Поэтому для
ответов на запросы \lstinline!head! мы держим рабочую копию некоторого
префикса головного списка. Ради эффективности доступа эта рабочая
копия хранится в виде обычного списка. Если головной список непуст,
эта копия также непуста. Итоговый тип выглядит так:
\begin{lstlisting}
  type $\alpha$ Queue = $\alpha$ list $\times$ int $\times$ $\alpha$ list $\times$ int $\times$ $\alpha$ list
\end{lstlisting}
Теперь мы можем записать основные функции над очередями:
\begin{lstlisting}
  fun snoc ((w, lenf, f, lenr, r), x) = check (w, lenf, f, lenr+1, x :: r)
  fun head (x :: w, lenf, f, lenr, r) = x
  fun tail (x :: w, lenf, f, lenr, r) = check (w, lenf-1, $\$$tl (force f), lenr, r)
\end{lstlisting}
Вспомогательная функция \lstinline!check! обеспечивает два инварианта:
что \lstinline!r! не может быть длиннее, чем \lstinline!f!, и что при
непустом \lstinline!f! не может быть пуст \lstinline!w!.
\begin{lstlisting}
  fun checkw ([], lenf, f, lenr, r) = (force f, lenf, f, lenr, r)
    | checkw q = q
  fun check (q as (w, lenf, f, lenr, r)) =
        if lenr $\le$ lenf then checkw q
        else let val f' = force f
             in checkw (f', lenf+lenr, $\$$(f' @ rev r), 0, []) end
\end{lstlisting}
Полная реализация очередей приведена на Рис.~\ref{fig:6.3}.

\begin{figure}
  \centering

  \caption{Амортизированные кучи с использованием метода физика.}
  \label{fig:6.3}
\end{figure}

Для анализа очередей методом физика мы выбираем функцию потенциала
$\Psi$ так, чтобы при вынуждении задержанного списка потенциал всегда был
равен нулю. Такое может произойти в двух ситуациях: когда
\lstinline!w! оказывается пустым, и когда \lstinline!r! оказывается
длиннее \lstinline!f!. Поэтому мы выбираем такое $\Psi$:
$$
\Psi(\lstinline!q!) = \min(2|\lstinline!w!|, |\lstinline!f!| - |\lstinline!r!|)
$$
\begin{theorem}\label{th:6.2}
  Амортизированная стоимость операций \lstinline!snoc! и
  \lstinline!tail! равна, соответственно, двум и четырем.

  \emph{Доказательство.} \lstinline!snoc!, не вызывающий проворота,
  просто добавляет новый элемент к хвостовому списку. При этом
  $|\lstinline!r!|$ увеличивается на единицу, а $|\lstinline!f!| -
  |\lstinline!r!|$ уменьшается на единицу. Полная стоимость
  \lstinline!snoc! равна одному, а уменьшение потенциала не больше
  одного, так что амортизированная стоимость равна максимум $1 - (-1)
  = 2$. Вызов \lstinline!tail!, не приводящий к провороту очереди,
  убирает элемент из рабочего списка и лениво убирает тот же самый
  элемент из головного списка. При этом $|\lstinline!w!|$ уменьшается
  на единицу, и на столько же уменьшается $|\lstinline!f!| -
  |\lstinline!r!|$, так что потенциал уменьшается максимум на два.
  Полная стоимость \lstinline!tail! равна двум~--- один как
  нераздельная стоимость (включая отбрасывание первого элемента
  \lstinline!w!) и один как разделяемая стоимость ленивого
  отбрасывания головы \lstinline!f!. Амортизированная стоимость
  получается $2 - (-2) = 4$.

  Наконец, рассмотрим вызов \lstinline!snoc! или \lstinline!tail!,
  приводящий к провороту очереди. В начале операции $|\lstinline!f!|
  = |\lstinline!r!|$, так что $\Psi = 0$. Перед самым проворотом
  $|\lstinline!f!| = m$, а $|\lstinline!r!| = m+1$. Разделяемая
  стоимость проворота равна $2m+1$, а потенциал получающейся очереди
  $2m$. Таким образом, амортизированная стоимость \lstinline!snoc!
  равна $1 + (2m + 1) - 2m = 2$. Амортизированная стоимость
  \lstinline!tail!  равна $2 + (2m + 1) - 2m = 3$. (Разница получается
  потому, что в случае \lstinline!tail! нам нужно ещё учесть стоимость
  удаления первого элемента \lstinline!f!.)
\end{theorem}

\begin{exercise}\label{ex:6.6}
  Покажите, почему каждая из следующих <<оптимизаций>> уничтожает
  амортизированное ограничение времени $O(1)$. Эти примеры показывают
  типичные ошибки при проектировании устойчивых амортизированных
  структур данных.
  \begin{enumerate}
  \item Заметим, что \lstinline!check! при провороте вынуждает
    \lstinline!f!, а затем записывает результат в \lstinline!w!. Разве не
    было бы более ленивым поведением, а следовательно, более выгодным,
    не вынуждать \lstinline!f!, пока \lstinline!w! не окажется пустым?
  \item Заметим, что во время операции \lstinline!tail! мы заменяем
    \lstinline!f! на \lstinline!$\$$tl (force f)!. Создание и
    вынуждение задержек приводит к заметным расходам, которые, хотя и
    сохраняют стоимость константной, могут сделать константу слишком
    большой. Разве не было бы ленивее, а следовательно, лучше, не изменять
    \lstinline!f!, а просто уменьшать \lstinline!lenf!, показывая
    таким образом, что элемент удален?
  \end{enumerate}
\end{exercise}

\subsection{Сортировка слиянием снизу вверх с совместным
  использованием}
\label{sc:6.4.3}

Большинство примеров в оставшихся главах использует метод банкира, а
не физика. Поэтому здесь мы приводим ещё один пример на метод физика.

Допустим, что вы хотите отсортировать несколько похожих списков,
например, \lstinline!x! и \lstinline!x :: xs!, или \lstinline!xs @ zs! и
\lstinline!ys @ zs!. Из соображений эффективности вам хотелось бы
использовать то, что хвосты списков совпадают, чтобы не повторять
работу по сортировке хвостов.  Назовем абстрактный тип данных для
решения этой задачи \term{сортируемая коллекция}{sortable
  collection}. Сигнатура сортируемых коллекций приведена на
Рис.~\ref{fig:6.4}.

\begin{figure}
  \centering

  \caption{Сигнатура сортируемых коллекций.}
  \label{fig:6.4}
\end{figure}

Теперь если мы из списка \lstinline!xs! сделаем сортируемую коллекцию
\lstinline!xs'!, добавив к пустой коллекции все элементы
\lstinline!xs! по очереди, то сможем отсортировать \lstinline!xs! и
\lstinline!x :: xs!, вызвав, соответственно, \lstinline!sort xs'! и
\lstinline!sort (add (x, xs'))!.

Сортируемые коллекции можно реализовать как сбалансированные двоичные
деревья поиска. Тогда \lstinline!add! и \lstinline!sort! будут иметь,
соответственно, ограничения по времени в худшем случае $O(\log n)$ и
$O(n)$. Здесь мы достигаем тех же самых ограничений, но только
амортизированных, используя \term{сортировку слиянием снизу
  вверх}{bottom-up mergesort}.

Сортировка слиянием снизу вверх сначала разбивает список на $n$
упорядоченных сегментов (на первом этапе каждый сегмент содержит по
одному элементу). Затем она попарно сливает сегменты одинакового
размера, пока для каждого размера не останется только один. Наконец,
сливаются сегменты неодинакового размера.

Возьмем состояние данных непосредственно перед последним
шагом. Размеры сегментов в этот момент равны степеням двойки,
соответствующим единичным битам в $n$.  Именно это представление мы
будем использовать для наших сортируемых коллекций.  Похожие коллекции
будут совместно использовать работу сортировки снизу вверх с точностью
до последней фазы, когда сливаются сегменты разного размера.
Полностью данные будут представлены в виде задержанного списка
сегментов, каждый из которых является списком элементов, плюс целое
число~--- размер коллекции.
\begin{lstlisting}
  type Sortable = int $\times$ Elem.T list list susp
\end{lstlisting}
Отдельные сегменты хранятся в порядке возрастания размера, а элементы
каждого сегмента хранятся в порядке возрастания согласно функциям
сравнения структуры \lstinline!Elem!.

Основная операция над сегментами~--- слияние двух упорядоченных
списков, \lstinline{mrg}.
\begin{lstlisting}
  fun mrg ([], ys) = ys
    | mrg (xs, []) = xs
    | mrg (xs as x :: xs', ys as y :: ys') =
       if Elem.leq (x, y) then x :: mrg (xs', ys) else y :: mrg (xs, ys')
\end{lstlisting}
При добавлении нового элемента мы создаём одноэлементный сегмент. Если
наименьший из существующих сегментов тоже одноэлементен, мы эти два
сегмента сливаем, и продолжаем слияние до тех пор, пока новый сегмент
не окажется меньше наименьшего существующего. Это слияние управляется
битами в поле размера. Если младший бит \lstinline!size! равен нулю, то
мы просто прицепляем новый сегмент к списку сегментов. Если бит равен
единице, мы сливаем два сегмента и повторяем операцию. Разумеется, все
это происходит в ленивом режиме.
\begin{lstlisting}
  fun add (x, (size, segs)) =
       let fun addSeg (seg, segs, size) =
                if size mod 2 = 0 then seg :: segs
                else addSeg (mrg (seg, hd segs), tl segs, size div 2)
       in (size+1, $\$$addSeg([x], force segs, size)) end
\end{lstlisting}
Наконец, чтобы отсортировать коллекцию, мы сливаем сегменты от
меньшего к большему.
\begin{lstlisting}
  fun sort (size, segs) =
       let fun mrgAll (xs, []) = xs
             | mrgAll (xs, seg :: segs) = mrgAll (mrg (xs, seg), segs)
       in mrgAll ([], force segs) end
\end{lstlisting}

\begin{remark}
  Можно рассматривать \lstinline!mrgAll! как вычисление
  $$
  [] \bowtie s_1 \bowtie \ldots \bowtie s_m
  $$
  где $s_i$~--- $i$-й сегмент, а $\bowtie$~--- инфиксное
  лево-ассоциативное обозначение для операции \lstinline!mrg!. Это частный случай весьма
  распространенного программного шаблона, который можно записать как
  $$
  c \oplus x_1 \oplus \ldots \oplus x_m
  $$
  для любого $c$ и лево-ассоциативной $\oplus$. В качестве других
  примеров этого шаблона можно привести суммирование списка целых ($c
  = 0$ и $\oplus = +$) или нахождение максимума в списке натуральных
  чисел ($c = 0$ и $\oplus = \max$). Одна из самых сильных черт
  функциональных языков~--- способность определять шаблоны подобного
  рода в виде \term{функций высших порядков}{higher-order functions}
  (т.~е., функций, которые принимают другие функции в качестве
  аргументов или возвращают функции как результат). Например,
  вышеприведенный шаблон можно записать как
  \begin{lstlisting}
    fun foldl (f, c, []) = c
      | foldl (f, c, x :: xs) = foldl (f, f (c, x), xs)
  \end{lstlisting}
  Тогда \lstinline!sort! выглядит как
  \begin{lstlisting}
    fun sort (size, segs) = foldl (mrg, [], force segs)
  \end{lstlisting}
\end{remark}
Полный программный код к нашей реализации сортируемых коллекций
приведен на Рис.~\ref{fig:6.5}.

\begin{figure}
  \centering

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

Покажем, используя метод физика, что операция \lstinline!add! занимает
амортизированное время $O(\log n)$, а операция \lstinline!sort!
амортизированное время $O(n)$.  Вначале зададим функцию потенциала
$\Psi$, которая полностью определяется размером коллекции.
$$
\Psi(n) = 2n - 2 \sum_{i=0}^{\infty} b_i (n \mod 2^i+1)
$$
где $b_i$~--- $i$-й бит $n$. Заметим, что $\Psi(n)$ ограничен сверху
величиной $2n$, и что $\Psi(n) = 0$ в точности тогда, когда $n = 2^k -
1$ для некоторого $k$.

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

Сначала вычислим полную стоимость операции \lstinline!add!. Её
нераздельная стоимость равна единице, а разделяемая равна
стоимости слияний, проводимых внутри \lstinline!addSeg!. Допустим, что
младшие $k$ бит числа $n$ равны единице (т.~е., $b_i =1$ для $i < k$ и
$b_k = 0$). В этом случае \lstinline!addSeg! проводит $k$ слияний.
Первое из них сливает два списка длиной 1, второе два списка длиной 2,
и так далее. Поскольку слияние двух списков размера $m$ занимает $2m$
шагов, \lstinline!addSeg! занимает
$$
(1+1) + (2+2) + \cdots + (2^{k-1} + 2^{k-1}) = 2(\sum_{i=0}^{k-1} 2^i)
= 2 (2^k - 1)
$$
шагов. Следовательно, полная стоимость \lstinline!add! равна $2(2^k -
1) + 1 = 2^{k+1} - 1$.

Вычислим теперь изменение потенциала. Пусть $n' = n+1$, а $b'_i$~---
$i$-й бит числа $n'$. Тогда
$$
\begin{array}{l}
\Psi(n') - \Psi(n) \\
= 2n' - 2\sum_{i=0}^\infty b'_i (n \mod 2^i + 1) - (2n - 2\sum_{i=0}^\infty (n \mod 2^i + 1) \\
= 2 + 2\sum_{i=0}^\infty (b_i(n \mod 2^i + 1) - b'_i(n' \mod 2^i + 1)) \\
= 2 + 2\sum_{i=0}^\infty \delta(i)
\end{array}
$$
где $\delta(i) = b_i(n \mod 2^i + 1) - b'_i(n \mod 2^i +
1)$. Рассмотрим три случая: $i < k$, $i = k$ и $i > k$.
\begin{itemize}
\item $(i < k)$: поскольку $b_i = 1$, а $b'_i = 0$, $\delta(i) = n
  \mod 2^i + 1$. Но $n \mod 2^i = 2^i - 1$, так что $\delta(i) - 2^i$.
\item $(i = k)$: поскольку $b_k = 0$, а $b'_k = 1$, $\delta(k) = -(n'
  \mod 2^k + 1)$. Но $n' \mod 2^k = 0$, так что $\delta(k) = -1 = -b'_k$.
\item $(i > k)$: поскольку $b'_i = b_i$, $\delta(i) = b'_i (n \mod 2^i
  - n' \mod 2^i)$. Но $n' \mod 2^i = (n+1) \mod 2^i = n \mod 2^i + 1$,
  так что $\delta(i) = b'_i(-1) = -b'_i$.
\end{itemize}
Следовательно,
$$
\begin{array}{lcl}
\Psi(n') - \Psi(n) & = & 2 + 2\sum_{i=0}^\infty \delta(i) \\
& = & 2 + 2\sum_{i=0}^{k-1} 2^i + 2 \sum_{i=k}^\infty (-b'_i) \\
& = & 2 + 2(2^k - 1) - 2\sum_{i=k}^\infty b'_i \\
& = & 2^{k+1} - 2B'
\end{array}
$$
где $B'$~--- число единичных битов в $n'$. Тогда амортизированная
стоимость операции \lstinline!add! равна
$$
(2^{k+1} - 1) - (2^{k+1} - 2B') = 2B' -1
$$
Поскольку $B'$ пропорционален $O(\log n)$, такую же оценку имеет и
амортизированная стоимость \lstinline!add!.

Наконец, вычисляем амортизированную стоимость операции
\lstinline!sort!. Первое её действие~--- вынудить задержанный список
сегментов.  Поскольку потенциал не обязательно равен нулю, это
добавляет $\Psi(n)$ к амортизированной стоимости операции. Затем
\lstinline!sort! сливает сегменты, двигаясь от меньших к большим. В
худшем случае $n = 2^k -1$, так что есть по сегменту каждого размера
от 1 до $2^{k-1}$. Слияние сегментов занимает в общей сложности
$$
\begin{array}{l}
(1+2) + (1+2+4) + (1+2+4+8) + \cdots + (1 + 2 + \cdots + 2^{k-1}) \\
= \sum_{i=1}^{k-1}\sum_{j=0}^i 2^j = \sum_{i=1}^{k-1}(2^{i+1} - 1)
= (2^{k+1} - 4) - (k - 1) = 2n - k - 1
\end{array}
$$
шагов. Следовательно, амортизированная стоимость равна
$O(n) + \Psi(n) = O(n)$.

\begin{exercise}\label{ex:6.7}
Замените в нашей реализации задержанный список списков на список
потоков.
\begin{enumerate}
\item докажите ограничения стоимости для \lstinline!add! и
  \lstinline!sort! с помощью метода банкира.
\item Напишите функцию для извлечения наименьших $k$ элементов из
  сортируемой коллекции. Докажите, что ваша функция работает за
  амортизированное время не хуже $O(k \log n)$.
\end{enumerate}
\end{exercise}

\section{Ленивые парные кучи}
\label{sc:6.5}

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

Напомним, что в предыдущей реализации парных куч дети каждого узла
представлялись как список структур \lstinline!Heap!. При уничтожении
минимального элемента корень отбрасывался, а затем дети сливались
попарно при помощи функции
\begin{lstlisting}
  fun mergePairs [] = E
    | mergePairs [h] = h
    | mergePairs (h$_1$ :: h$_2$ :: hs) = merge (merge (h$_1$, h$_2$), mergePairs hs)
\end{lstlisting}
Если уничтожить корневой элемент одной и той же кучи дважды,
\lstinline!mergePairs!  будет также вызвана дважды. При этом работа
будет повторяться, а всякая надежда на эффективное амортизированное
использование будет потеряна. Чтобы справиться с задачей устойчивости,
нужно предотвратить повторение этой работы.  Очередной раз мы
используем для этого ленивое вычисление. Вместо списка куч
\lstinline!Heap list!, мы представляем детей узла как задержанную кучу
\lstinline!Heap susp!. Значение этой задержки равно
\lstinline!$\$$mergePairs cs!. Поскольку \lstinline!mergePairs!
работает с парами элементов списка детей, мы будем расширять нашу
задержку двумя элементами сразу. Следовательно, нам понадобится
дополнительное поле типа \lstinline!Heap! в каждом узле для хранения
непарных потомков. Если непарных потомков нет (т.~е., число детей
чётно), это дополнительное поле будет пустым. Поскольку это поле
используется только тогда, когда число детей нечетно, мы будем
называть его \term{нечётным полем}{odd field}. Таким образом, наш
новый тип данных имеет вид
\begin{lstlisting}
  datatype Heap = E | T of Elem.T $\times$ Heap $\times$ Heap susp
\end{lstlisting}
Операции \lstinline!insert! и \lstinline!findMin! почти не требуют
изменений.
\begin{lstlisting}
  fun insert (x, a) = merge (T (x, E, $\$$E), a)
  fun findMin (T (x, a, m)) = x
\end{lstlisting}
Раньше у нас операция \lstinline!merge! была простой, а операция
\lstinline!deleteMin!~--- сложной. Теперь ситуация обратная~--- вся
сложность функции \lstinline!mergePairs! оказалась перенесена в
\lstinline!merge!, которая устанавливает все необходимые
задержки. Функция \lstinline!deleteMin! просто вынуждает задержку кучи
и сливает её с нечётным полем.
\begin{lstlisting}
  fun deleteMin (T (x, a, $\$$b)) = merge (a, b)
\end{lstlisting}
Функцию \lstinline!merge! мы определяем в два шага. Первый шаг
проверяет, что аргументы непусты, и если это так, выясняет, у которого
из двух аргументов меньше корневой элемент.
\begin{lstlisting}
  fun merge (a, E) = a
    | merge (E, a) = a
    | merge (a as T (x, _, _), b as T (y, _, _)) =
        if Elem.leq (x, y) then link (a, b) else link (b, a)
\end{lstlisting}
Второй шаг, воплощенный во вспомогательной функции \lstinline!link!,
добавляет к куче новый элемент. Если нечётное поле пусто, новый
ребёнок добавляется туда.
\begin{lstlisting}
  fun link (T (x, E, m), a) = T (x, a, m)
\end{lstlisting}
В противном случае новый ребёнок спаривается с ребёнком из нечётного
поля, и оба они добавляются к задержке. Другими словами, мы превращаем
задержку \lstinline!m = $\$$mergePairs cs! в
\lstinline!$\$$mergePairs (a :: b :: cs)!. Заметим, что
\begin{lstlisting}
  $\$$mergePairs (a :: b :: cs)
    $\equiv$ $\$$merge (merge (a, b), mergePairs cs)
    $\equiv$ $\$$merge (merge (a, b), force ($\$$mergePairs cs))
    $\equiv$ $\$$merge (merge (a, b), force m)
\end{lstlisting}
так что, вторую ветвь функции \lstinline!link! можно записать как
\begin{lstlisting}
  fun link (T (x, b, m), a) = T (x, E, $\$$merge (merge (a, b), force m))
\end{lstlisting}
Полный код этой реализации приведен на Рис.~\ref{fig:6.6}.

\begin{figure}
  \centering

  \caption{Устойчивые парные кучи с использованием ленивого вычисления.}
  \label{fig:6.6}
\end{figure}

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

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

\noindent
\textbf{Долг} Некоторые разновидности анализа с использованием
традиционного метода банкира, например, анализ сжатия путей Тарьяном
\cite{Tarjan1983}, работают и с понятием кредита, и с понятием
дебета.  Когда операции требуется кредит больше, чем имеется в данный
момент, она создает пару кредит-дебет и немедленно тратит
кредит. Дебет остается как обязательство, подлежащее исполнению. Позже
избыток кредита можно использовать для выплаты долга\footnote{Здесь
  напрашивается явная аналогия со спонтанным порождением и
  аннигиляцией пар частица-античастица в физике. В сущности, для этого
  дебета более подходящим названием было бы <<антикредит>>.
}.
Дебет, остающийся в конце вычисления, добавляется к общей реальной
стоимости. Несмотря на некоторое сходство между двумя понятиями долга,
есть и явные различия. Например, долг, как он введен в этой главе,
оставшийся в конце вычисления, тихо уничтожается.

Интересно заметить, что дебет введен Тарьяном при анализе сжатия
путей; ведь сжатие путей, в сущности, является применением мемоизации
к функции поиска.

\noindent
\textbf{Амортизация и устойчивость} До публикации этой работы
считалось, что амортизация несовместима с устойчивостью.  Несколько
исследователей \cite{DriscollSleatorTarjan1994, Raman1992} замечали,
что амортизированные структуры невозможно сделать эффективно
устойчивыми с помощью существующих методик добавления устойчивости к
эфемерным структурам данных, подобных описанным в
\cite{Driscoll-etal1989, Dietz1989}, по причинам вроде указанных нами в
Разделе~\ref{sc:5.6}. Интересно, что эти методики порождают структуры
с амортизированными показателями производительности, при том, что
показатели нижележащей структуры должны быть жёсткими. (У этих методик
есть и другие ограничения. Прежде всего, они не работают для структур
данных, имеющих функции, применимые более, чем к одной
версии. Примерами таких запретных операций являются конкатенация
списков и объединение множеств.)

Идея, что ленивое вычисление может помирить амортизацию и устойчивость,
впервые, в рудиментарной форме, появилась в
\cite{Okasaki1995c}. Теория и практика этого подхода были развиты в
\cite{Okasaki1995a, Okasaki1996b}.

\noindent
\textbf{Амортизация и функциональные структуры данных} Схунмакерс
\cite{Schoenmakers1993} в своей диссертации исследует амортизированные
структуры данных в аппликативном функциональном языке, в основном
исследуя формальный вывод амортизированных ограничений с помощью
метода физика. Он избегает проблем устойчивости, настаивая, чтобы все
структуры данных использовались только в однопоточном режиме.

\noindent
\textbf{Очереди и биномиальные кучи} Очереди из
Раздела~\ref{sc:6.3.2} и ленивые биномиальные кучи из
Раздела~\ref{sc:6.4.1} впервые появились в \cite{Okasaki1996b}. Анализ
ленивых биномиальных куч применим также к реализации Кинга
\cite{King1994}.

\noindent
\textbf{Анализ времени выполнения ленивых программ} Существует несколько
теоретических формализмов для анализа временного поведения ленивых
программ \cite{BjernerHolmstrom1989, Sands1990, Sands1995,
  Wadler1988}. Однако эти формализмы недостаточно пока разработаны,
чтобы быть применимыми на практике. Одна из сложностей состоит в том,
что они, в некотором смысле, чрезмерно общие. В каждой из этих систем
стоимость программы вычисляется по отношению к некоторому контексту,
который представляет собой описание, как результат программы будет
использоваться. Однако этот подход часто неприменим в методологии
разработки программ, где структуры данных проектируются как
абстрактные типы, чье поведение, включая сложность операций,
описывается в изоляции. В противоположность этим подходам наш способ
анализа дает независимые от контекста результаты (т.~е., они верны
безотносительно того, как структуры данных будут использоваться).

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