chapter09.tex

\chapter{Числовые представления}
\label{ch:9}

Рассмотрим обыкновенные представления списков и натуральных чисел, а
также несколько типичных функций над этими типами данных.
\begin{lstlisting}
  datatype $\alpha$ List =                   datatype Nat =
       Nil                                Zero
     | Cons of $\alpha$ $\times$ $\alpha$ List                  | Succ of Nat

  fun tail (Cons (x, xs)) = xs       fun pred (Succ n) = n

  fun append (Nil, ys) = ys          fun plus (Zero, n) = n
    | append (Cons (x, xs), ys) =      | plus (Succ m, n) =
       Cons (x, append (xs, ys))          Succ (plus (m, n))
\end{lstlisting}
Помимо того, что списки содержат элементы, а натуральные числа нет,
эти две реализации практически совпадают. Подобным же образом
соотносятся биномиальные кучи и двоичные числа. Эти примеры наводят на
сильную аналогию между представлениями числа $n$ и представлениями
объектов-контейнеров размером $n$. Функции, работающие с контейнерами,
полностью аналогичны арифметическим функциям, работающим с
числами. Например, добавление нового элемента похоже на увеличение
числа на единицу, удаление элемента похоже на уменьшение числа на
единицу, а слияние двух контейнеров похоже на сложение двух
чисел. Можно использовать эту аналогию для проектирования новых
представлений абстракций контейнеров~--- достаточно выбрать
представление натуральных чисел, обладающее заданными свойствами, и
соответствующим образом определить функции над
объектами-контейнерами. Назовем реализацию, спроектированную при помощи
этого приёма, \term{числовым представлением}{numerical representation}.

В этой главе мы исследуем несколько числовых представлений для двух
различных абстракций: \term{куч}{heaps} и \term{списков со свободным
  доступом}{random-access lists} (известных также как \term{гибкие массивы}{flexible
arrays}). Эти две абстракции подчёркивают различные наборы
арифметических операций. Для куч требуются эффективные функции
увеличения на единицу и сложения, а для списков со свободным доступом
требуются эффективные функции увеличения и уменьшения на единицу.

\section{Позиционные системы счисления}
\label{sc:9.1}

\term{Позиционная система счисления}{positional number system}
\cite{Knuth1973b}~--- способ записи числа в виде последовательности
цифр $b_0\ldots b_{m-1}$. Цифра $b_0$ называется \term{младшим разрядом}{least
  significant digit}, а цифра $b_{m-1}$ \term{старшим разрядом}{most
  significant digit}. Кроме обычных десятичных чисел, мы всегда будем
записывать последовательности цифр в порядке от младшего разряда к старшему.

Каждый разряд $b_i$ имеет вес $w_i$, так что значение
последовательности $b_0\ldots b_{m-1}$ равно $\sum_{i=0}^{m-1}
b_iw_i$. Для каждой конкретной позиционной системы счисления
последовательность весов фиксирована, и фиксирован набор цифр $D_i$,
из которых выбирается каждая $b_i$. Для единичных чисел $w_i = 1$ и
$D_i = \{\mathtt{1}\}$ для всех $i$, а для двоичных чисел $w_i = 2^i$,
а $D_i = \{\mathtt{0}, \mathtt{1}\}$. (Мы принимаем соглашение, по
которому все цифры, кроме обычных десятичных, изображаются
машинописным шрифтом.)
Говорится, что число записано по основанию $B$, если $w_i =
B^i$, а $D_i = \{\mathtt{0}, \ldots, B-1\}$. Чаще всего, но не всегда,
веса разрядов представляют собой увеличивающуюся степенную
последовательность, а множество $D_i$ во всех разрядах одинаково.

Система счисления называется \term{избыточной}{redundant}, если
некоторые числа могут быть представлены более, чем одним способом.
Например, можно получить избыточную систему двоичного счисления, взяв
$w_i = 2^i$ и $D_i = \{\mathtt{0}, \mathtt{1}, \mathtt{2}\}$. Тогда
десятичное число 13 можно будет записать как \texttt{1011},
\texttt{1201} или \texttt{122}. Мы запрещаем нули в конце числа,
поскольку иначе почти все системы счисления будут тривиально
избыточны.

Компьютерные представления позиционных систем счисления могут быть
\term{плотными}{dense} или \term{разреженными}{sparse}. Плотное
представление~--- это просто список (или какая-то другая
последовательность) цифр, включая нули. Напротив, при разреженном
представлении нули пропускаются. В таком случае требуется хранить
информацию либо о ранге (т.~е., индексе), либо о весе каждой ненулевой
цифры.  На Рис.~\ref{fig:9.1} показаны два разных представления
двоичных чисел в Стандартном ML, одно из которых плотное, второе
разреженное, а также функции увеличения на единицу, уменьшения на
единицу и сложения для каждого из них. Среди уже виденных нами
числовых представлений биномиальные кучи с расписаниями
(Раздел~\ref{sc:7.3}) используют плотное представление, а биномиальные
кучи (Раздел~\ref{sc:3.2}) и ленивые биномиальные кучи
(Раздел~\ref{sc:6.4.1})~--- разреженное представление.

\begin{figure}
  \centering

  \mbox{возрастающий порядок по старшинству}\\
  \mbox{перенос}\\
  \mbox{занятие}\\
  \mbox{перенос}\\
  \mbox{возрастающий порядок весов, каждый из которых степень двойки}\\

  \caption{Два представления двоичных чисел.}
  \label{fig:9.1}
\end{figure}

\section{Двоичные числа}
\label{sc:9.2}

Имея позиционную систему счисления, мы можем реализовать числовое
представление на её основе в виде последовательности
деревьев. Количество и размеры деревьев, представляющих коллекцию
размера $n$, определяются положением $n$ в позиционной системе
счисления. Для каждого веса $w_i$ имеются $b_i$ деревьев
соответствующего размера. Например, двоичное представление числа 73
выглядит как \texttt{1001001}, так что коллекция размера 73 в двоичном
числовом представлении будет содержать три дерева размеров 1, 8 и 64.

Как правило, деревья в числовых представлениях обладают весьма
регулярной структурой. Например, в двоичных числовых представлениях
все деревья имеют размер-степень двойки. Три часто встречающихся типа
деревьев с такой структурой~--- \term{полные двоичные листовые
  деревья}{complete binary leaf trees} \cite{KaldewaijDielissen1996}, \term{биномиальные
  деревья}{binomial trees} \cite{Vuillemin1978} и
\term{подвешенные деревья}{pennants} \cite{SackStrothotte1990}.

\begin{definition}
  \textbf{(Полные двоичные листовые деревья)} Полное двоичное листовое
  дерево ранга 0~--- это лист; полное двоичное листовое дерево ранга
  $r > 0$ представляет собой узел с двумя поддеревьями, каждое из
  которых является полным двоичным листовым деревом ранга $r -
  1$. Листовое дерево~--- это дерево, хранящее элементы только в
  листовых узлах, в отличие от обычных деревьев, где элементы
  содержатся в каждом узле. Полное двоичное дерево ранга $r$ содержит
  $2^{r+1} - 1$ узлов, но только $2^r$ листьев. Следовательно, полное
  двоичное листовое дерево ранга $r$ содержит $2^r$ элементов.
\end{definition}

\begin{definition}
  \textbf{(Биномиальные деревья)} Биномиальное дерево ранга $r$
  представляет собой узел с $r$ дочерними деревьями $c_1 \ldots c_r$,
  где каждое $c_i$ является биномиальным деревом ранга $r -
  i$. Можно также определить биномиальное дерево ранга $r > 0$ как
  биномиальное дерево ранга $r - 1$, к которому в качестве самого
  левого поддерева добавлено другое биномиальное дерево ранга $r -
  1$. Из второго определения легко видеть, что биномиальное дерево
  ранга $r$ содержит $2^r$ узлов.
\end{definition}

\begin{definition}
  \textbf{(Подвешенные деревья)} Подвешенное дерево ранга 0 представляет собой один узел, а
  подвешенное дерево ранга $r > 0$ представляет собой узел с единственным
  поддеревом~--- полным двоичным деревом ранга $r - 1$. Полное
  двоичное дерево содержит $2^r - 1$ элементов, так что подвешенное дерево
  содержит $2^r$ элементов.
\end{definition}

\begin{figure}
  \begin{subfigure}[b]{0.3\textwidth}
    \centering
    \input{figures/fig.9.2a.tex}\par\vspace{0.2cm}
    (a)
  \end{subfigure}
  \begin{subfigure}[b]{0.3\textwidth}
    \centering
    \input{figures/fig.9.2b.tex}\par\vspace{0.2cm}
    (b)
  \end{subfigure}
  \begin{subfigure}[b]{0.3\textwidth}
    \centering
    \input{figures/fig.9.2c.tex}\par\vspace{0.2cm}
    (c)
  \end{subfigure}
  \caption{Три дерева ранга 3: (a) полное двоичное листовое дерево,
    (b) биномиальное дерево и (c) подвешенное дерево.}
  \label{fig:9.2}
\end{figure}

Три этих разновидности деревьев показаны на
Рис.~\ref{fig:9.2}. Выбор разновидности для каждой структуры данных
зависит от свойств, которыми эта структура должна обладать, например,
от порядка, в котором требуется хранить элементы в деревьях. Важным
вопросом при оценке соответствия разновидности деревьев для конкретной
структуры данных будет то, насколько хорошо данная разновидность
поддерживает функции, аналогичные переносу и занятию в двоичной
арифметике. При имитации переноса мы \term{связываем}{link} два дерева
ранга $r$ и получаем дерево ранга $r+1$. Аналогично, при имитации
занятия мы \term{развязываем}{unlink} дерево ранга $r > 0$ и получаем
два дерева ранга $r-1$. На Рис.~\ref{fig:9.3} показана операция
связывания (обозначенная $\oplus$)
для каждой из трех разновидностей деревьев. Если мы предполагаем, что
элементы не переупорядочиваются, любая из разновидностей может быть
связана или развязана за время $O(1)$.

\begin{figure}
  \centering
  \begin{subfigure}[b]{0.45\textwidth}
    \centering
    \input{figures/fig.9.3a.tex}\par\vspace{0.2cm}
    (a)
  \end{subfigure}
  \begin{subfigure}[b]{0.45\textwidth}
    \centering
    \input{figures/fig.9.3b.tex}\par\vspace{0.2cm}
    (b)
  \end{subfigure}\par\vspace{0.2cm}
  \begin{subfigure}[b]{1\textwidth}
    \centering
    \input{figures/fig.9.3c.tex}\par\vspace{0.2cm}
    (c)
  \end{subfigure}

  \caption{Связывание двух деревьев ранга $r$ в дерево ранга $r+1$ для
    (a) полных двоичных листовых деревьев, (b) биномиальных деревьев и
    (c) подвешенных деревьев.}
  \label{fig:9.3}
\end{figure}

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

\subsection{Двоичные списки с произвольным доступом}
\label{sc:9.2.1}

\term{Список с произвольным доступом}{random access list}, называемый
также односторонним гибким массивом~--- это структура данных,
поддерживающая, подобно массиву, функции доступа и модификации любого
элемента, а также обыкновенные функции для списков: \lstinline!cons!,
\lstinline!head! и \lstinline!tail!. Сигнатура списков с произвольным
доступом приведена на Рис.~\ref{fig:9.4}.

\begin{figure}
  \centering

  \caption{Сигнатура списков с произвольным доступом.}
  \label{fig:9.4}
\end{figure}

Мы реализуем списки с произвольным доступом, используя двоичное
числовое представление. Двоичный список с произвольным доступом
размера $n$ содержит по дереву на каждую единицу в двоичном
представлении $n$. Ранг каждого дерева соответствует рангу
соответствующей цифры; если $i$-й бит $n$ равен единице, то список с
произвольным доступом содержит дерево размера $2^i$. Мы можем
использовать любую из трех разновидностей деревьев и либо плотное,
либо разреженное представление. Для этого примера мы используем
простейшее сочетание: полные двоичные листовые деревья и плотное
представление. Таким образом, тип \lstinline!RList! выглядит так:
\begin{lstlisting}
  datatype $\alpha$ Tree = Leaf of $\alpha$ | Node of int $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree
  datatype $\alpha$ Digit = Zero | One of $\alpha$ Tree
  datatype $\alpha$ RList = $\alpha$ Digit list
\end{lstlisting}
Целое число в каждой вершине~--- это размер дерева. Это число
избыточно, поскольку размер каждого дерева полностью определяется
размером его родителя или позицией в списке цифр, но мы всё равно его
храним ради удобства. Деревья хранятся в порядке возрастания размера,
а порядок элементов~--- слева направо, как внутри, так и между
деревьями. Таким образом, головой списка с произвольным доступом
является самый левый лист наименьшего дерева. На Рис.~\ref{fig:9.5}
показан двоичный список с произвольным доступом размера 7. Заметим,
что максимальное число деревьев в списке размера $n$ равно
$\lfloor \log (n+1) \rfloor$, а максимальная глубина дерева равна
$\lfloor \log n \rfloor$.

\begin{figure}
  \centering
  \input{figures/fig.9.5.tex}
  \caption{Двоичный список с произвольным доступом, содержащий элементы 0\ldots 6.}
  \label{fig:9.5}
\end{figure}

Вставка элемента в двоичный список с произвольным доступом (при помощи
\lstinline!cons!) аналогична увеличению двоичного числа на
единицу. Напомним функцию увеличения для двоичных чисел:
\begin{lstlisting}
  fun inc [] = [One]
    | inc (Zero :: ds) = One :: ds
    | inc (One :: ds) = Zero :: inc ds
\end{lstlisting}
Чтобы добавить новый элемент к началу списка, мы сначала преобразуем
его в лист, а затем вставляем его в список деревьев с помощью
вспомогательной функции \lstinline!consTree!, которая следует образцу
\lstinline!inc!.
\begin{lstlisting}
  fun cons (x, ts) = consTree (Leaf x, ts)

  fun consTree (t, []) = [One t]
    | consTree (t, Zero :: ts) = One t :: ts
    | consTree (t$_1$, One t$_2$ :: ts) = Zero :: consTree (link (t$_1$, t$_2$), ts)
\end{lstlisting}
Вспомогательная функция \lstinline!link! порождает новое дерево из двух
поддеревьев одинакового размера и автоматически вычисляет его размер.

Уничтожение элемента в двоичном списке с произвольным доступом (при
помощи \lstinline!tail!) аналогично уменьшению двоичного числа на
единицу. Напомним функцию уменьшения для плотных двоичных чисел:
\begin{lstlisting}
  fun dec [One] = []
    | dec (One :: ds) = Zero :: ds
    | dec (Zero :: ds) = One :: dec ds
\end{lstlisting}
Соответствующая функция для списков деревьев называется
\lstinline!unconsTree!. Будучи примененной к списку, чья первая цифра
имеет ранг $r$, \lstinline!unconsTree! возвращает пару, состоящую из
дерева ранга $r$ и нового списка без этого дерева.
\begin{lstlisting}
  fun unconsTree [One t] = (t, [])
    | unconsTree (One t :: ts) = (t, Zero :: ts)
    | unconsTree (Zero :: ts) =
       let val (Node (_, t$_1$, t$_2$), ts') = unconsTree ts
       in (t$_1$, One t$_2$ :: ts') end
\end{lstlisting}
Функции \lstinline!head! и \lstinline!tail!  удаляют самый левый
элемент при помощи \lstinline!unconsTree!, а затем, соответственно,
либо возвращают этот элемент, либо отбрасывают.
\begin{lstlisting}
  fun head ts = let val (Leaf x, _) = unconsTree ts in x end
  fun tail ts = let val (_, ts') = unconsTree ts in ts' end
\end{lstlisting}

Функции \lstinline!lookup! и \lstinline!update! не соответствуют
никаким арифметическим операциям. Они просто пользуются организацией
двоичных списков произвольного доступа в виде списков логарифмической
длины, состоящих из деревьев логарифмической глубины. Поиск элемента
состоит из двух этапов. Сначала в списке мы ищем нужное дерево, а
затем в этом дереве ищем требуемый элемент. Вспомогательная функция
\lstinline!lookupTree! использует поле размера в каждом узле, чтобы
определить, находится ли $i$-й элемент в левом или правом
поддереве.
\begin{lstlisting}
  fun lookup (i, Zero :: ts) = lookup (i, ts)
    | lookup (i, One t :: ts) =
       if i < size t then lookupTree (i, t) else lookup (i - size t, ts)

  fun lookupTree (0, Leaf x) = x
    | lookupTree (i, Node (w, t$_1$, t$_2$)) =
       if i < w div 2 then lookupTree (i, t$_1$
       else lookupTree (i - w div 2, t$_2$)
\end{lstlisting}
\lstinline!update! действует аналогично, но вдобавок копирует путь от
корня до обновляемого листа.
\begin{lstlisting}
  fun update (i, y, Zero::ts) = Zero :: update (i, y, ts)
    | update (i, y, One t :: ts) =
       if i < size t then One (updateTree (i, y, t)) :: ts
       else One t :: update (i - size t, y, ts)

  fun updateTree (0, y, Leaf x) = Leaf y
    | updateTree (i, y, Node (w, t$_1$, t$_2$)) =
       if i < w div 2 then Node (w, updateTree (i, y, t$_1$), t$_2$)
       else Node (w, t$_1$, updateTree (i - w div 2, y, t$_2$))
\end{lstlisting}
Полный код этой реализации приведен на Рис.~\ref{fig:9.6}.

\begin{figure}
  \centering

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

Функции \lstinline!cons!, \lstinline!head! и \lstinline!tail!
производят не более $O(1)$ работы на цифру, так что общее время их
работы $O(\log n)$ в худшем случае. \lstinline!lookup! и
\lstinline!update! требуют не более $O(\log n)$ времени на поиск
нужного дерева, а затем не более $O(\log n)$ времени на поиск нужного
элемента в этом дереве, так что общее время их работы также $O(\log
n)$ в худшем случае.

\begin{exercise}\label{ex:9.1}
  Напишите функцию \lstinline!drop! типа
  \lstinline!int $\times$ $\alpha$ RList $\to$ $\alpha$ RList!, уничтожающую первые $k$
  элементов двоичного списка с произвольным доступом. Функция должна
  работать за время $O(\log n)$.
\end{exercise}

\begin{exercise}\label{ex:9.2}
  Напишите функцию \lstinline!create! типа
  \lstinline!int $\times$ $\alpha$ $\to$ $\alpha$ RList!, которая создает
  двоичный список с произвольным доступом, содержащий $n$ копий
  некоторого значения $x$. Функция также должна работать за время
  $O(\log n)$. (Может оказаться полезным вспомнить Упражнение~\ref{ex:2.5}.)
\end{exercise}

\begin{exercise}\label{ex:9.3}
  Реализуйте \lstinline!BinaryRandomAccessList! заново, используя
  разреженное представление
  \begin{lstlisting}
    datatype $\alpha$ Tree = Leaf of $\alpha$ | Node of int $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree
    type $\alpha$ RList = $\alpha$ Tree list
  \end{lstlisting}
\end{exercise}

\subsection{Безнулевые представления}
\label{sc:9.2.2}

В двоичных списках с произвольным доступом разочаровывает то, что
списковые функции \lstinline!cons!, \lstinline!head! и
\lstinline!tail! требуют $O(\log n)$ времени вместо $O(1)$. В
следующих трех подразделах мы исследуем варианты двоичных чисел,
улучшающие время работы всех трех функций до $O(1)$. В этом подразделе
мы начинаем с функции \lstinline!head!.

\begin{remark}
  Очевидное решение, позволяющее \lstinline!head! выполняться за время
  $O(1)$~--- хранить первый элемент отдельно от остального списка,
  подобно функтору \lstinline!ExplicitMin! из
  Упражнения~\ref{ex:3.7}. Другое решение~--- использовать разреженное
  представление и либо биномиальные деревья, либо подвешенные деревья, так что
  головой списка будет корень первого дерева. Решение, которое мы
  исследуем в этом подразделе, хорошо тем, что оно также немного
  улучшает время работы \lstinline!lookup! и \lstinline!update!.
\end{remark}

Сейчас \lstinline!head! у нас реализована через вызов
\lstinline!unconsTree!, которая выделяет первый элемент, а также
перестраивает список без этого элемента. При таком подходе мы получаем
компактный код, поскольку \lstinline!unconsTree! поддерживает как
\lstinline!head!, так и \lstinline!tail!, но теряется время
на построение списков, не используемых функцией
\lstinline!head!. Ради большей эффективности имеет смысл реализовать
\lstinline!head! напрямую. В качестве особого случая, легко заставить
\lstinline!head! работать за время $O(1)$, когда первая цифра не ноль.
\begin{lstlisting}
  fun head (One (Leaf x) :: _) = x
\end{lstlisting}
Вдохновленные этим правилом, мы хотели бы устроить так, чтобы первая
цифра \emph{никогда} не была нулем. Есть множество простых трюков,
достигающих именно этого, но более красивым решением будет
использовать \term{безнулевое}{zeroless} представление, где ни одна
цифра не равна нулю.

Безнулевые двоичные числа строятся из единиц и двоек, а не из единиц и
нулей. Вес $i$-й цифры по-прежнему равен $2^i$. Так, например,
десятичное число 16 можно записать как \texttt{2111} вместо
\texttt{00001}. Функция добавления единицы на безнулевых двоичных
числах реализуется так:
\begin{lstlisting}
  datatype Digit = One | Two
  type Nat = Digit list

  fun inc [] = [One]
    | inc (One :: ds) = Two :: ds
    | inc (Two :: ds) = One :: inc ds
\end{lstlisting}

\begin{exercise}\label{ex:9.4}
  Напишите функции уменьшения на единицу и сложения для безнулевых
  двоичных чисел. Заметим, что переноситься при сложении может как
  единица, так и двойка.
\end{exercise}

Теперь если мы заменим тип цифр в двоичных списках с произвольным
доступом на
\begin{lstlisting}
  datatype $\alpha$ Digit = One of $\alpha$ Tree | Two of $\alpha$ Tree $\times$ $\alpha$ Tree
\end{lstlisting}
то можем реализовать \lstinline!head! как
\begin{lstlisting}
  fun head (One (Leaf x) :: _) = x
    | head (Two (Leaf x, Leaf y) :: _) = x
\end{lstlisting}
Ясно, что эта функция работает за время $O(1)$.

\begin{exercise}\label{ex:9.5}
  Реализуйте оставшиеся функции для этого типа.
\end{exercise}

\begin{exercise}\label{ex:9.6}
  Покажите, что теперь функции \lstinline!lookup! и
  \lstinline!update!, примененные к элементу $i$, работают за время
  $O(\log i)$.
\end{exercise}

\begin{exercise}\label{ex:9.7}
  При некоторых дополнительных условиях красно-черные деревья
  (Раздел~\ref{sc:3.3}) можно рассматривать как числовое
  представление. Сопоставьте безнулевые двоичные списки с произвольным
  доступом и красно-черные деревья, в которых вставка разрешена только
  в самую левую позицию. Обратите особое внимание на функции
  \lstinline!cons! и \lstinline!insert!, а также на инварианты формы
  структур, порождаемых этими функциями.
\end{exercise}

\subsection{Ленивые представления}
\label{sc:9.2.3}

Допустим, мы представляем двоичные числа как потоки цифр, а не
списки. Тогда функция увеличения на единицу получает вид
\begin{lstlisting}
  fun lazy inc ($\$$Nil) = $\$$Cons (One, $\$$Nil)
         | inc ($\$$Cons (Zero, ds)) = $\$$Cons (One, ds)
         | inc ($\$$Cons (One, ds)) = $\$$Cons (Zero, inc ds)
\end{lstlisting}
Заметим, что функция эта пошаговая.

В Разделе~\ref{sc:6.4.1} мы видели, как с помощью ленивого вычисления
можно заставить вставку в биномиальные кучи работать за
амортизированное время $O(1)$, так что нас не должно удивлять, что
наша новая версия \lstinline!inc! также работает за амортизированное
время $O(1)$. Мы доказываем это по методу банкира.

\emph{Доказательство.} Пусть каждая цифра ноль несет одну единицу долга, а
цифра единица~--- ноль единиц долга. Допустим, \lstinline!ds!
начинается с $k$ единиц (\lstinline!One!), а затем имеет ноль
(\lstinline!Zero!). Тогда \lstinline!inc ds! заменяет все эти \lstinline!One!
на \lstinline!Zero!, а \lstinline!Zero! на \lstinline!One!.
Выделим по одной единице долга на каждый
из этих шагов. Теперь у каждого элемента \lstinline!Zero! есть одна
единица долга, а у \lstinline!One! две: одна, унаследованная от
исходной задержки в этом месте, и одна, созданная только
что. Высвобождение этих двух единиц долга восстанавливает
инвариант. Поскольку амортизированная стоимость функции равна ее
нераздельной стоимости (здесь это $O(1)$) плюс число высвобождаемых
единиц долга (здесь две), \lstinline!inc! работает за амортизированное
время $O(1)$.

Рассмотрим теперь функцию уменьшения.
\begin{lstlisting}
  fun lazy dec ($\$$Cons (One, $\$$Nil)) = $\$$Nil
         | dec ($\$$Cons (One, ds)) = $\$$Cons (Zero, ds)
         | dec ($\$$Cons (Zero, ds)) = $\$$Cons (One, dec ds)
\end{lstlisting}
Поскольку эта функция подобна \lstinline!inc!, но
со сменой ролей цифр, можно ожидать, что при помощи подобного
доказательства мы получим такое же ограничение. Так оно и есть, если
мы не используем \emph{обе} функции. Однако если используются как
\lstinline!inc!, так и \lstinline!dec!, по крайней мере одной из них
приходится приписывать амортизированное время $O(\log n)$. Чтобы понять,
почему, представим последовательность увеличений и уменьшений,
циклически переходящих от $2^k - 1$ к $2^k$ и обратно. Каждая операция
при этом затрагивает каждую цифру, и общее время получается $O(\log
n)$.

Но разве мы не доказали, что амортизированное время каждой из функций
$O(1)$? Что здесь неверно? Проблема в том, что эти два доказательства
требуют конфликтующих инвариантов долга. Чтобы доказать, что
\lstinline!inc! работает за амортизированное время $O(1)$, мы
требовали, чтобы каждому \lstinline!Zero! приписывалась одна единица
долга, а каждому \lstinline!One! ноль единиц. При доказательстве, что
\lstinline!dec! работает за амортизированное время $O(1)$, мы
приписывали одну единицу долга каждому \lstinline!One! и ноль единиц
каждому \lstinline!Zero!.

Главное свойство, которое как \lstinline!inc!, так и \lstinline!dec!
по отдельности имеют, состоит в том, что по крайней мере половина
операций, достигших какой-то позиции, на этой позиции
останавливаются. А именно, каждый вызов \lstinline!inc! или
\lstinline!dec! обрабатывает первую цифру, но только один вызов из
двух затрагивает вторую. Третью цифру обрабатывает один вызов из
четырех, и так далее. На интуитивном уровне, амортизированная
стоимость каждой операции получается
$$
O(1 + 1/2 + 1/4 + 1/8 + \ldots) = O(1)
$$
Разделим возможные цифры-заполнители каждой позиции на
\term{безопасные}{safe} и \term{опасные}{dangerous}: функция,
достигшая безопасной цифры, всегда на ней и завершается, а функция,
добравшаяся до опасной цифры, может проследовать к следующей
позиции. Чтобы доказать, что из двух последовательных операций никогда
обе не добираются до следующей позиции, нам нужно показать, что каждый
раз, когда операция обрабатывает опасную цифру, она заменяет её на
безопасную. Тогда следующая операция, которая доберется до данной
позиции, на ней и остановится. Формально мы доказываем, что каждая
операция работает за амортизированное время $O(1)$, устанавливая
инвариант долга, где каждой безопасной цифре приписывается одна
единица долга, а опасной ноль.

Функция увеличения требует считать опасной самую большую цифру, а
функция уменьшения считает опасной самую маленькую цифру. Чтобы
поддержать их обе, нам нужна третья безопасная цифра. Таким образом,
мы переключаемся на \term{избыточные}{redundant} двоичные числа, где
каждая цифра может быть нулем, единицей или двойкой. Тогда
\lstinline!inc! и \lstinline!dec! реализуются следующим образом:
\begin{lstlisting}
  datatype Digit = Zero | One | Two
  type Nat = Digit Stream

  fun lazy inc ($\$$Nil) = $\$$Cons (One, $\$$Nil)
         | inc ($\$$Cons (Zero, ds)) = $\$$Cons (One, ds)
         | inc ($\$$Cons (One, ds)) = $\$$Cons (Two, ds)
         | inc ($\$$Cons (Two, ds)) = $\$$Cons (One, inc ds)

  fun lazy dec ($\$$Cons (One, $\$$Nil) = $\$$Nil
         | dec ($\$$Cons (One, ds)) = $\$$Cons (Zero, ds)
         | dec ($\$$Cons (Two, ds)) = $\$$Cons (One, ds)
         | dec ($\$$Cons (Zero, ds)) = $\$$Cons (One, dec ds)
\end{lstlisting}
Обратите внимание, что рекурсивные предложения в \lstinline!inc! и
\lstinline!dec!~--- для \lstinline!Two! (двойки) и \lstinline!Zero! (ноля),
соответственно~--- оба порождают \lstinline!One! (единицу). При этом
\lstinline!One!~--- безопасная цифра, а \lstinline!Zero! и
\lstinline!Two!~--- опасные. Чтобы увидеть, как нам здесь помогает
избыточность, рассмотрим, как работает увеличение на единицу двоичного
числа \texttt{222222}, дающее \texttt{1111111}. Для этой операции
требуется семь шагов. Однако уменьшение этого значения не дает снова
\texttt{222222}, Вместо этого мы всего за один шаг получаем
\texttt{0111111}. Таким образом, чередование увеличений и уменьшений
больше не является проблемой.

Ленивые двоичные числа могут служить моделью для построения многих других
структур данных. В Главе~\ref{ch:11} мы обобщим эту модель и получим
метод проектирования под названием \term{неявное рекурсивное
  замедление}{implicit recursive slowdown}.

\begin{exercise}\label{ex:9.8}
  Докажите, что как \lstinline!inc!, так и \lstinline!dec! работают за
  амортизированное время $O(1)$ с помощью инварианта долга,
  присваивающего одну единицу долга цифре \lstinline!One! и ноль цифрам
  \lstinline!Zero! и \lstinline!Two!.
\end{exercise}

\begin{exercise}\label{ex:9.9}
  Реализуйте \lstinline!cons!, \lstinline!head! и \lstinline!tail! для
  списков с произвольным доступом на основе безнулевых избыточных
  двоичных чисел, используя тип
  \begin{lstlisting}
    datatype $\alpha$ Digit =
           One of $\alpha$ Tree
         | Two of $\alpha$ Tree $\times$ $\alpha$ Tree
         | Three of $\alpha$ Tree $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree
    type $\alpha$ RList = Digit Stream
  \end{lstlisting}
  Покажите, что все три функции работают за время $O(1)$.
\end{exercise}

\begin{exercise}\label{ex:9.10}
  Как показано в Разделе~\ref{sc:7.3} на биномиальных кучах с
  расписаниями, можно снабдить ленивые двоичные числа расписаниями и
  получить ограничение $O(1)$ в худшем случае. Заново реализуйте
  \lstinline!cons!, \lstinline!head! и \lstinline!tail! из предыдущего
  упражнения, так, чтобы они работали за время $O(1)$ в худшем
  случае. Может оказаться полезным иметь два различных конструктора
  для цифры <<два>> (скажем, \lstinline!Two! и \lstinline!Two'!),
  чтобы различать рекурсивные и нерекурсивные варианты вызова \lstinline!cons!
  и \lstinline!tail!.
\end{exercise}

\subsection{Сегментированные представления}
\label{sc:9.2.4}

Ещё одна разновидность двоичных чисел, дающая показатели $O(1)$ в
худшем случае~--- \term{сегментированные}{segmented} двоичные
числа. Проблема с обычными двоичными числами состоит в том, что
переносы и занятия могут происходить каскадом. Например, увеличение
$2^k - 1$ приводит в двоичной арифметике к $k$ переносам. Аналогично,
уменьшение $2^k$ ведет к $k$ занятиям. Сегментированные двоичные числа
решают эту проблему, позволяя нескольким переносам или занятиям
выполняться за один шаг.

Заметим, что увеличение двоичного числа требует $k$ шагов, когда число
начинается с последовательности в $k$ единиц. Подобным образом,
уменьшение двоичного числа требует $k$ шагов, когда число начинается
с $k$ нулей. Сегментированные двоичные числа объединяют непрерывные
последовательности одинаковых цифр в блоки, так что мы можем применить
перенос или занятие к целому блоку за один шаг. Мы представляем
сегментированные двоичные числа как список чередующихся блоков из
единиц и нулей согласно следующему объявлению типа:
\begin{lstlisting}
  datatype DigitBlock = Zeros of int | Ones of int
  type Nat = DigitBlock list
\end{lstlisting}
Целое число в каждом DigitBlock представляет длину блока.

Мы добавляем новые блоки к началу списка блоков с помощью
вспомогательных функций
\lstinline!zeros! (нули) и \lstinline!ones! (единицы). Эти функции
сливают идущие подряд блоки одинаковых цифр и отбрасывают
пустые блоки.  Кроме того, \lstinline!zeros! отбрасывает нули в конце
записи числа.
\begin{lstlisting}
  fun zeros (i, []) = []
    | zeros (0, blks) = blks
    | zeros (i, Zeros j :: blks) = Zeros (i+j) :: blks
    | zeros (i, blks) = Zeros i :: blks

  fun ones (0, blks) = blks
    | ones (i, Ones j :: blks) = Ones (i+j) :: blks
    | ones (i, blks) = Ones i :: blks
\end{lstlisting}
Теперь при увеличении сегментированного двоичного числа мы смотрим на
первый блок цифр (если он вообще есть). Если первый блок содержит
нули, то мы заменяем первый из этих нулей на единицу, создавая новый
единичный блок единиц, а длину блока нулей уменьшая на один. Если же
первый блок содержит $i$ единиц, то мы за один шаг проделываем $i$
переносов, заменяя единицы на нули и увеличивая следующую цифру.
\begin{lstlisting}
  fun inc [] = [Ones 1]
    | inc (Zeros i :: blks) = ones (1, zeros (i-1, blks))
    | inc (Ones i :: blks) = Zeros i :: inc blks
\end{lstlisting}
В третьей строке функции мы знаем, что рекурсивный вызов
\lstinline!inc! не зациклится, поскольку если следующий блок
присутствует, он будет содержать нули. Во второй строке
вспомогательная функция позаботится об особом случае, когда первый
блок содержит единственный ноль.

Уменьшение сегментированного двоичного числа выглядит почти точно так
же, только роли единиц и нулей меняются.
\begin{lstlisting}
  fun dec (Ones i :: blks) = zeros (1, ones (i-1, blks))
    | dec (Zeros i :: blks) = Ones i :: dec blks
\end{lstlisting}
Здесь мы тоже знаем, что рекурсивный вызов не зациклится, потому что в
следующем блоке должны быть единицы.

К сожалению, несмотря на то, что сегментированные двоичные числа
поддерживают операции \lstinline!inc! и \lstinline!dec! за время
$O(1)$ в худшем случае, числовые представления, основанные на них,
оказываются слишком сложными, чтобы иметь какое-либо практическое
значение. Проблема заключается в том, что понятие перевода целого
блока единиц в нули и наоборот плохо переводится на язык операций с
деревьями. Более практичные решения, однако, можно получить, если
сочетать сегментацию с избыточными двоичными числами. При этом мы
можем снова обрабатывать цифры (а следовательно, и деревья) по
одной. Сегментация позволяет нам обрабатывать цифры в середине
последовательности, а не только в начале.

Рассмотрим, например, избыточное представление, в котором блоки единиц
рассматриваются как единый сегмент.
\begin{lstlisting}
  datatype Digits = Zero | Ones of int | Two
  type Nat = Digits list
\end{lstlisting}
Определяем вспомогательную функцию \lstinline!ones!, обрабатывающую
блоки, идущие друг за другом, и уничтожающую пустые блоки.
\begin{lstlisting}
  fun ones (0, ds) = ds
    | ones (i, Ones j :: ds) = Ones (i+j) :: ds
    | ones (i, ds) = Ones i :: ds
\end{lstlisting}
Полезно рассматривать цифру \lstinline!Two! (два) как незаконченный
перенос. Чтобы не было каскадов переносов, нам надо гарантировать, что
две двойки никогда не идут подряд. Будем поддерживать инвариант, что
последняя не равная единице цифра перед каждой двойкой равна
нулю. Этот инвариант можно записать как регулярное выражение
$\mathtt{(0|1|01^*2)^*}$ либо, если ещё учесть отсутствие нулей в
конце, $\mathtt{(0^*1 | 0^+1^*2)^*}$. Заметим, что двойка никогда не
является первой цифрой. Таким образом, мы можем увеличить число на
единицу за время $O(1)$ в худшем случае, просто увеличивая первую
цифру.
\begin{lstlisting}
  fun simpleInc [] = [Ones 1]
    | simpleInc (Zero :: ds) = ones (1, ds)
    | simpleInc (Ones i :: ds) = Two :: ones (i-1, ds)
\end{lstlisting}
В третьей строке инвариант нарушается очевидным образом, поскольку
\lstinline!Two! оказывается в начале. Кроме этого, инвариант может
быть нарушен во второй строке, если первая не равная единице цифра
равна двойке. Мы восстанавливаем инвариант при помощи вспомогательной
функции \lstinline!fixup!, проверяющей, не является ли первая не
равная единице цифра двойкой. Если это так, \lstinline!fixup! заменяет
двойку на ноль и увеличивает следующую цифру, которая, в свою очередь,
двойкой быть не может.
\begin{lstlisting}
  fun fixup (Two :: ds) = Zero :: simpleInc ds
    | fixup (Ones i :: Two :: ds) = Ones i :: Zero :: fixup ds
    | fixup ds = ds
\end{lstlisting}
Во второй строке \lstinline!fixup! мы пользуемся тем, что представление
сегментировано, проскакивая блок единиц, за которыми следует
двойка. Наконец, \lstinline!inc! зовет сначала \lstinline!simpleInc!,
затем \lstinline!fixup!.
\begin{lstlisting}
  fun inc ds = fixup (simpleInc ds)
\end{lstlisting}

Эта реализация может служить образцом для многих других структур
данных. Такая структура представляет собой последовательность уровней,
каждый из которых имеет признак \emph{зелёный}, \emph{жёлтый} или
\emph{красный}. Каждый уровень
соответствует цифре в вышеописанной реализации. Зелёный соответствует
нулю-\lstinline!Zero!, жёлтый единице-\lstinline!One!, а красный
двойке-\lstinline!Two!. Операция над любым объектом может перекрасить
первый уровень из зеленого в жёлтый или из жёлтого в красный, но
никогда из зелёного в красный. Инвариант состоит в том, что первый
не-жёлтый уровень перед красным всегда зелёный. Процедура
восстановления инварианта проверяет, не является ли первый не-жёлтый
уровень красным и, если да, переводит этот уровень из красного в
зелёный и, возможно, ухудшает цвет следующего уровня из зелёного в
жёлтый или из жёлтого в красный. Последовательные жёлтые уровни
собираются в блок, чтобы облегчить доступ к первому не-жёлтому. Каплан
и Тарьян \cite{KaplanTarjan1995} называют эту общую методику
\term{рекурсивное замедление}{recursive slowdown}.

\begin{exercise}\label{ex:9.11}
  Добавьте сегментацию к биномиальным кучам, чтобы операция
  \lstinline!insert! работала за время $O(1)$ в худшем
  случае. Используйте тип
  \begin{lstlisting}
    datatype Tree = Node of Elem.T $\times$ Tree list
    datatype Digit = Zero | Ones of Tree list | Two of Tree $\times$ Tree
    type Heap = Digit list
  \end{lstlisting}
  Восстанавливайте инвариант после слияния куч, уничтожая все цифры \lstinline!Two!.
\end{exercise}

\begin{exercise}\label{ex:9.12}
  Пример реализации двоичных чисел на основе рекурсивного замедления
  поддерживает операцию \lstinline!inc! за время $O(1)$ в худшем
  случае, но для \lstinline!dec! может потребоваться $O(\log
  n)$. Реализуйте сегментированные избыточные двоичные числа,
  поддерживающие как \lstinline!inc!, так и \lstinline!dec! за время
  $O(1)$ в худшем случае, с цифрами \texttt{0}, \texttt{1},
  \texttt{2}, \texttt{3} и \texttt{4}, причем \texttt{0} и \texttt{4}
  красные, \texttt{1} и \texttt{3} жёлтые, а \texttt{2} зелёная.
\end{exercise}

\begin{exercise}\label{ex:9.13}
  Реализуйте \lstinline!cons!, \lstinline!head!, \lstinline!tail! и
  \lstinline!lookup! для числового представления списков с
  произвольным доступом на основе системы счисления из предыдущего
  упражнения. Ваше представление должно поддерживать \lstinline!cons!,
  \lstinline!head! и \lstinline!tail! за время $O(1)$ в худшем случае,
  а \lstinline!lookup! за время $O(\log n)$ в худшем случае.
\end{exercise}

\section{Скошенные двоичные числа}
\label{sc:9.3}

При помощи ленивых двоичных чисел и сегментированных двоичных чисел мы
получили два метода улучшения асимптотического поведения функций
увеличения на единицу и уменьшения на единицу с $O(\log n)$ до
$O(1)$. В этом разделе мы рассмотрим третий метод; на практике он
обычно приводит к более простым и быстрым программам, однако этот
метод связан с более радикальным отходом от обыкновенных двоичных
чисел.

В \term{скошенных двоичных числах}{skew binary numbers}
\cite{Myers1983, Okasaki1995b} вес
$i$-й цифры $w_i$ равен не $2^i$, как в обыкновенных двоичных числах,
а $2^i - 1$. Используются цифры ноль, один и два (т.~е., $D_i =
\{\mathtt{0}, \mathtt{1}, \mathtt{2}\}$). Например, десятичное число
92 можно записать как \texttt{002101} (начиная с наименее значимой
цифры).

Эта система счисления избыточна, однако мы можем вернуть уникальность
представления, если введём дополнительное требование, что лишь
самая младшая ненулевая цифра может быть двойкой.  Будем говорить, что
такое число записано в \term{каноническом виде}{canonical
  form}. Начиная с этого момента, будем предполагать, что все
скошенные двоичные числа записаны в каноническом виде.

\begin{theorem}\label{th:9.1}
  (Майерс \cite{Myers1983}) Каждое натуральное число можно
  единственным образом записать в скошенном двоичном каноническом виде.
\end{theorem}

Напомним, что вес $i$-й цифры равен $2^i - 1$, и заметим, что $1 +
2(2^{i+1} - 1) = 2^{i+2} - 1$. Отсюда следует, что мы можем добавить
единицу к скошенному двоичному числу, чья младшая ненулевая цифра равна двойке,
заменив эту двойку на ноль и увеличив следующую цифру с нуля до
единицы или с единицы до двух. (Следующая цифра не может уже равняться
двойке.) Увеличение на единицу скошенного двоичного числа, которое не
содержит двойки, ещё проще~--- надо только увеличить младшую цифру с
нуля до единицы или с единицы до двойки. В обоих случаях результат
снова оказывается в каноническом виде. Если предположить, что мы можем
найти младшую ненулевую цифру за время $O(1)$, в обоих случаях мы
тратим не более $O(1)$ времени!

Мы не можем использовать для скошенных двоичных чисел плотное
представление, потому что тогда поиск первой ненулевой цифры займет
больше времени, чем $O(1)$. Поэтому мы выбираем разреженное
представление и всегда имеем непосредственный доступ к младшей
ненулевой цифре.
\begin{lstlisting}
  type Nat = int list
\end{lstlisting}
Целые числа представляют либо ранг, либо вес ненулевых цифр. Мы пока
что используем веса. Веса хранятся в порядке возрастания, но два
наименьших веса могут быть одинаковы, показывая, что младшая ненулевая
цифра равна двум. При таком представлении мы реализуем \lstinline!inc!
следующим образом:
\begin{lstlisting}
  fun inc (ws as w$_1$ :: w$_2$ :: rest) =
        if w$_1$ = w$_2$ then (1 + w$_1$ + w$_2$) :: rest else 1 :: ws
    | inc ws = 1 :: ws
\end{lstlisting}
Первый вариант проверяет два первых веса на равенство, и либо сливает
их в следующий больший вес (увеличивая таким образом следующую цифру),
либо добавляет новый вес 1 (увеличивая самую младшую цифру). Второй
вариант обрабатывает случай, когда список \lstinline!ws! пуст или
содержит только один вес. Ясно, что эта процедура работает за время
$O(1)$ в худшем случае.

Уменьшение скошенного двоичного числа на единицу столь же просто, как
увеличение. Если младшая цифра не равна нулю, мы просто уменьшаем эту
цифру с двух до единицы или с единицы до нуля. В противном случае мы
уменьшаем самую младшую ненулевую цифру, а предыдущий ноль заменяем
двойкой. Это реализуется так:
\begin{lstlisting}
  fun dec (1 :: ws) = ws
    | dec (w :: ws) = (w div 2) :: (w div 2) :: ws
\end{lstlisting}
Во второй строке нужно учитывать, что если $w = 2^{k+1} - 1$, то
$\lfloor w/2 \rfloor = 2^k - 1$. Ясно, что \lstinline!dec! также
работает за время $O(1)$ в худшем случае.

\subsection{Скошенные двоичные списки с произвольным доступом}
\label{sc:9.3.1}

Теперь мы разработаем числовое представление для списков с
произвольным доступом на основе скошенных двоичных чисел.  Основа
представления данных~--- список деревьев, одно дерево для каждой
единицы и два дерева для каждой двойки. Деревья хранятся в порядке
возрастания размера, но если младшая ненулевая цифра двойка, то два
первых дерева будут одинакового размера.

Размеры деревьев соответствуют весам цифр в скошенных двоичных числах,
так что дерево, представляющее $i$-ю цифру, имеет размер $2^{i+1} -
1$. До сих пор мы в основном рассматривали деревья размером степень
двойки, но встречались и деревья нужного нам сейчас размера: полные
двоичные деревья. Таким образом, мы представляем скошенные двоичные
списки с произвольным доступом в виде списков полных двоичных
деревьев.

Чтобы эффективно поддержать операцию \lstinline!head!, мы должны
сделать первый элемент списка с произвольным доступом вершиной первого
дерева, так что элементы внутри каждого дерева мы будем хранить в
предпорядке слева направо; элементы каждого дерева предшествуют
элементам следующего дерева.

В предыдущих примерах мы хранили в каждой вершине её размер или ранг,
даже когда эта информация была избыточна. В этом примере мы используем
более реалистичный подход и храним размер только вместе с вершиной
каждого дерева, а не для всех поддеревьев. Следовательно, тип данных
для скошенных двоичных списков с произвольным доступом получается
\begin{lstlisting}
  datatype $\alpha$ Tree = Leaf of $\alpha$ | Node of $\alpha$ $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree
  type $\alpha$ RList = (int $\times$ $\alpha$ Tree) list
\end{lstlisting}
Теперь можно определить \lstinline!cons! по аналогии с
\lstinline!inc!.
\begin{lstlisting}
  fun cons (x, ts as (w$_1$, t$_1$) :: (w$_2$, t$_2$) :: rest) =
        if w$_1$ = w$_2$ then (1+w$_1$+w$_2$, Node (x, t$_1$, t$_2$) :: rest)
        else (1, Leaf x) :: ts
    | cons (x, ts) = (1, Leaf x) :: ts
\end{lstlisting}
Функции \lstinline!head! и \lstinline!tail! работают с корнем первого
дерева. \lstinline!tail! возвращает дочерние узлы этого дерева (если
они есть) обратно в начало списка, где они будут представлять новую
цифру-двойку.
\begin{lstlisting}
  fun head ((1, Leaf x) :: ts) = x
    | head ((w, Node (x, t$_1$, t$_2$)) :: ts) = x
  fun tail ((1, Leaf x) :: ts) = ts
    | tail ((w, Node (x, t$_1$, t$_2$)) :: ts) = (w div 2, t$_1$) :: (w div 2, t$_2$) :: ts
\end{lstlisting}
Чтобы найти элемент, мы сначала ищем нужное дерево, а затем нужный
элемент в этом дереве. При поиске внутри дерева мы отслеживаем размер
текущего дерева.
\begin{lstlisting}
  fun lookup (i, (w, t) :: ts) =
        if i < w then lookupTree (w, i ,t)
        else lookup (i-w, ts)

  fun lookupTree (1, 0, Leaf x) = x
    | lookupTree (w, 0, Node (x, t$_1$, t$_2$)) = x
    | lookupTree (w, i, Node (x, t$_1$, t$_2$)) =
        if i < w div 2 then lookupTree (w div 2, i-1, t$_1$)
        else lookupTree (w div 2, i - 1 - w div 2, t$_2$)
\end{lstlisting}
Заметим, что в предпоследней строке мы отнимаем единицу от \lstinline!i!,
поскольку перескакиваем через \lstinline!x!. В последней строке мы
отнимаем $1 + \lfloor \lstinline!w!/2 \rfloor$ от \lstinline!i!,
поскольку перескакиваем через \lstinline!x! и через все элементы
\lstinline!t$_1$!. Функции \lstinline!update! и \lstinline!updateTree!
определяются подобным же образом. Они приведены на Рис.~\ref{fig:9.7}
наряду со всеми остальными деталями реализации.

\begin{figure}
  \centering

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

Нетрудно убедиться, что \lstinline!cons!, \lstinline!head! и
\lstinline!tail! работают за время $O(1)$ в худшем случае. Подобно
двоичным спискам с произвольным доступом, скошенные двоичные списки с
произвольным доступом представляют собой списки логарифмической длины,
состоящие из деревьев логарифмической глубины, так что
\lstinline!lookup! и \lstinline!update! работают за время $O(\log n)$
в худшем случае. На самом деле каждый неудачный шаг \lstinline!lookup!
или \lstinline!update! отбрасывает по крайней мере один элемент, так
что можно немного улучшить оценку до $O(\min(i, \log n))$.

\begin{hint}
  Скошенные двоичные списки с произвольным доступом являются хорошим
  выбором для приложений, активно использующих как спископодобные, так
  и массивоподобные функции в списках с произвольным
  доступом. Существуют более производительные реализации списков и
  более производительные реализации (устойчивых) массивов, но ни одна
  реализация не превосходит нашу в обеих классах функций \cite{Okasaki1995b}.
\end{hint}

\begin{exercise}\label{ex:9.14}
  Перепишите структуру \lstinline!HoodMelvilleQueue! из
  Раздела~\ref{sc:8.2.1}, чтобы она вместо обычных списков
  использовала скошенные двоичные списки с произвольным
  доступом. Реализуйте на получившейся структуре операции
  \lstinline!lookup! и \lstinline!update!.
\end{exercise}

\subsection{Скошенные биномиальные кучи}
\label{sc:9.3.2}

Наконец, рассмотрим гибридное числовое представление для куч,
основанное как на скошенных двоичных числах, так и на обыкновенных
двоичных числах. Реализация скошенного двоичного числа проста и
быстра, и отлично подходит как образец для функции
\lstinline!insert!. К сожалению, сложение двух скошенных двоичных
чисел весьма неудобно. Поэтому функцию \lstinline!merge! мы порождаем
на основе сложения обыкновенных двоичных чисел, а не сложения
скошенных чисел.

\term{Скошенное биномиальное дерево}{skew binomial tree} представляет
собой биномиальное дерево, в котором к каждому узлу приписан список
длиной до $r$ элементов, где $r$~--- ранг рассматриваемого узла.
\begin{lstlisting}
  datatype Tree = Node of int $\times$ Elem.T $\times$ Elem.T list $\times$ Tree list
\end{lstlisting}
В отличие от обыкновенных биномиальных деревьев, размер скошенного
биномиального дерева не полностью определяется его рангом; ранг
определяет диапазон возможных размеров.

\begin{lemma}
  \label{lm:9.2}
  Если $t$~--- скошенное биномиальное дерево ранга $r$, то $2^r \le
  |t| \le 2^{r+1} - 1$
  \begin{exercise}\label{ex:9.15}
    Докажите Лемму~\ref{lm:9.2}
  \end{exercise}
\end{lemma}

Над скошенными биномиальными деревьями можно производить операцию
\term{связывания}{linking} и \term{скошенного связывания}{skew linking}.
Функция связывания \lstinline!link! сочетает два дерева ранга $r$ и
получает одно дерево ранга $r+1$, делая дерево с большим корнем
ребенком дерева с меньшим корнем.
\begin{lstlisting}
  fun link (t$_1$ as Node (r, x$_1$, xs$_1$, c$_1$), t$_2$ as Node (_, x$_2$, xs$_2$, c$_2$) =
        if Elem.leq (x$_1$, x$_2$) then Node (r+1, x$_1$, xs$_1$, t$_2$ :: c$_1$)
        else Node (r+1, x$_2$, xs$_2$, t$_1$ :: c$_2$)
\end{lstlisting}
Функция скошенного связывания \lstinline!skewLink! сочетает два дерева
ранга $r$ и дополнительный элемент, получая дерево ранга
$r+1$. Сначала она связывает два дерева, а затем сравнивает корень
получившегося дерева с дополнительным элементом. Меньший из этих двух
элементов становится корнем, а больший добавляется к дополнительному
списку элементов.
\begin{lstlisting}
  fun skewLink (x, t$_1$, t$_2$) =
        let val Node (r, y, ys, c) = link (t$_1$, t$_2$)
        in
            if Elem.leq (x, y) then Node (r, x, y :: ys, c)
            else Node (r, y, x :: ys, c)
        end
\end{lstlisting}

Скошенная биномиальная куча представляет собой список скошенных
биномиальных деревьев, упорядоченных в порядке кучи, отсортированных
по возрастанию ранга, и только два первых дерева могут иметь
одинаковый ранг. Поскольку скошенные биномиальные деревья одного ранга
могут иметь различный размер, здесь уже нет прямого соответствия между
деревьями в куче и цифрами скошенного двоичного числа. представляющего
размер кучи.  Например, хотя скошенное двоичное представление числа 4
равно \texttt{11}, скошенная биномиальная куча размера 4 может
содержать либо одно дерево ранга 2 размера 4, либо два дерева ранга 1
размером 2, либо дерево ранга 1 размером 3 и дерево ранга 0, либо
дерево ранга 1 размером 2 и два дерева ранга 0. Однако максимальное
число деревьев в куче по-прежнему равно $O(\log n)$.

Большое преимущество скошенных биномиальных куч состоит в том, что
новый элемент вставляется за время $O(1)$. Сначала мы сравниваем ранги
двух наименьших деревьев. Если они совпадают, мы производим скошенное
связывание нового элемента с этими деревьями. В противном случае мы
создаем новое одноэлементное дерево и добавляем его к началу списка.
\begin{lstlisting}
  fun insert (x, ts as t$_1$ :: t$_2$ :: rest) =
        if rank t$_1$ = rank t$_2$ then skewLink (x, t$_1$, t$_2$) :: rest
        else Node (0, x, [], []) :: ts
    | insert (x, ts) = Node (0, x, [], []) :: ts
\end{lstlisting}

Оставшиеся функции почти такие же, как соответствующие функции
обыкновенных биномиальных куч. Мы изменяем имя старой функции
\lstinline!merge! на \lstinline!mergeTrees!. Она по-прежнему проходит
оба списка деревьев, проводя связывание (не скошенное связывание!)
каждый раз, когда видит два дерева одного ранга. Поскольку и
\lstinline!mergeTrees!, и её вспомогательная функция
\lstinline!insTree! ожидают списки деревьев строго возрастающего
ранга, функция \lstinline!merge! нормализует оба своих аргумента,
убирая дубликаты из начала списков, прежде чем позвать
\lstinline!mergeTrees!.
\begin{lstlisting}
  fun normalize [] = []
    | normalize (t :: ts) = insTree (t, ts)
  fun merge (ts$_1$, ts$_2$) = mergeTrees (normalize ts$_1$, normalize ts$_2$)
\end{lstlisting}
На функции \lstinline!findMin! и \lstinline!removeMinTree!
переключение на скошенные биномиальные кучи никак не влияет, поскольку
обе эти функции не заботятся о рангах, рассматривая только корень
каждого дерева. Функция \lstinline!deleteMin! изменяется лишь
ненамного. Как и раньше, изымается дерево с минимальным корнем, список
его детей обращается, и обращенный список детей сливается с
оставшимися деревьями.  Однако затем заново вставляются элементы
дополнительного списка, прикрепленного к уничтоженному корню.
\begin{lstlisting}
  fun deleteMin ts =
        let val (Node (_, x, xs, ts$_1$), ts$_2$) = removeMinTree ts
            fun insertAll ([], ts) = ts
              | insertAll (x :: xs, ts) = insertAll (xs, insert (x,
              ts))
        in insertAll (xs, merge (rev ts$_1$, ts$_2$)) end
\end{lstlisting}
На Рис.~\ref{fig:9.8} приведена полная реализация скошенных
биномиальных куч.

\begin{figure}
  \centering

  \caption{Скошенные биномиальные кучи.}
  \label{fig:9.8}
\end{figure}

Функция \lstinline!insert! работает за время $O(1)$ в худшем случае, а
\lstinline!merge!, \lstinline!findMin! и \lstinline!deleteMin!
работают за то же время, что и соответствующие функции для
обыкновенных биномиальных куч, то есть, за $O(\log n)$ в худшем
случае. Заметим, что каждая из различных фаз функции \lstinline!deleteMin!~---
поиск дерева с минимальным корнем, обращение его детей, слияние детей
с оставшимися деревьями и вставка дополнительных элементов,~---
занимает по $O(\log n)$.

Если нужно, мы можем улучшить время работы \lstinline!findMin! до
$O(1)$ при помощи функтора \lstinline!ExplicitMin! из
Упражнения~\ref{ex:3.7}. В Разделе~\ref{sc:10.2.2} мы увидим, как
улучшить также и время операции \lstinline!merge! до $O(1)$.

\begin{exercise}\label{ex:9.16}
  Допустим, нам нужна функция \lstinline!delete! типа
  \lstinline!Elem.T $\times$ Heap $\to$ Heap!.
  Напишите функтор, берущий реализацию куч \lstinline!H! и порождающий
  реализацию куч, поддерживающую наряду с обычными операциями над
  кучей функцию \lstinline!delete!. Используйте тип
  \begin{lstlisting}
    type Heap = H.Heap $\times$ H.Heap
  \end{lstlisting}
  где одна из элементарных куч представляет положительные вхождения
  элементов, а вторая~--- отрицательные вхождения. Отрицательное
  вхождение элемента в кучу означает, что этот элемент был уже
  уничтожен, но физически ещё не удален из кучи.  Положительные и
  отрицательные вхождения одного и того же элемента
  взаимоуничтожаются и физически удаляются из кучи, когда оба
  оказываются минимальными элементами своих куч.  Поддерживайте
  инвариант, что минимальный элемент положительной кучи строго меньше,
  чем минимальный элемент отрицательной кучи. (У этой реализации есть
  забавное свойство: элемент можно уничтожить прежде, чем он
  вставлен в кучу; для многих приложений это свойство безвредно.)
\end{exercise}

\section{Троичные и четверичные числа}
\label{sc:9.4}

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

Вес каждой цифры при основании $k$ равен $k^r$, так что нам нужны
семейства деревьев, имеющих такие размеры. Можно построить обобщения
для каждого из семейств деревьев, используемых в двоичных числовых
представлениях:

\begin{definition}\label{def:9.4}
  \textbf{(Полные $k$-ичные листовые деревья)} \term{Полное $k$-ичное дерево}{complete
    $k$-ary tree} ранга 0 представляет собой лист, а полное $k$-ичное
  дерево ранга $r > 0$ представляет собой узел с $k$ поддеревьями,
  каждое из которых является полным $k$-ичным деревом ранга
  $r-1$. Полное $k$-ичное дерево ранга $r$ содержит $(k^{r+1} - 1) /
  (k - 1)$ узлов и $k^r$ листьев. Полное $k$-ичное листовое дерево~---
  это полное $k$-ичное дерево, где элементы содержатся только в листьях.
\end{definition}
\begin{definition}\label{def:9.5}
  \textbf{($k$-номиальные деревья)} \term{$k$-номиальное
    дерево}{$k$-nomial tree} ранга $r$ представляет собой узел, у
  которого есть для каждого ранга $q$ от $r-1$ до 0 по $k-1$
  поддерева, имеющих ранг $q$. Иначе выражаясь,
  $k$-номиальное дерево ранга $r > 0$ представляет собой
  $k$-номиальное дерево ранга $r-1$, к которому в качестве левых
  поддеревьев присоединены ещё $k-1$ $k$-номиальных дерева ранга
  $r-1$. Из второго определения легко увидеть, что $k$-номиальное
  дерево ранга $r$ содержит $k^r$ узлов.
\end{definition}

\begin{definition}\label{def:9.6}
  \textbf{($k$-ичные подвешенные деревья)} \term{$k$-ичное подвешенное
  дерево}{$k$-ary pennant} ранга 0 представляет собой единственную
вершину, а $k$-ичное подвешенное дерево ранга $r > 0$ представляет
собой вершину с $k-1$ поддеревьями, каждое из которых является полным
$k$-ичным деревом ранга $r-1$. Каждое из этих поддеревьев содержит
$(k^r - 1) / (k - 1)$ узлов, так что всё дерево целиком содержит $k^r$ узлов.
\end{definition}

Преимущество при использовании оснований больше двойки заключается в
том, что для представления каждого числа требуется меньше цифр. В то
время как число по основанию 2 содержит примерно $\log_2 n$ цифр,
число по основанию $k$ содержит приблизительно $\log_k n = \log_2 n /
\log_2 k$ цифр. Например, при основании 4 нужно примерно вдвое меньше
цифр, чем при основании 2. С другой стороны, теперь для каждой цифры
имеется больше возможных значений, так что обработка каждой цифры
может отнимать больше времени. В числовых представлениях обработка
одной цифры по основанию $k$ часто требует примерно $k+1$ шагов, так
что операция, затрагивающая каждую цифру, должна отнимать примерно
$(k+1) \log_k n = \frac{k+1}{\log_2 k} \log n$ шагов. В следующей
таблице приведены значения $(k + 1) / \log_2 k$ для $k = 2, \ldots,
8$.\\
\begin{tabular}{c|ccccccc}
  $k$ & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
$(k + 1) / \log_2 k$ &
   3.00 & 2.52 & 2.50 & 2.58 & 2.71 & 2.85 & 3.0 \\
\end{tabular}
\\
По этой таблице можно заключить, что числовые представления,
основанные на троичных или четверичных числах, могут выигрывать до
16\% у числовых представлений на основе двоичных чисел. Другие
факторы, например, размер кода, часто делают большие основания менее
эффективными при увеличении $k$, так что настолько большие ускорения
редко встречаются на практике. Более того, троичные и четверичные
представления на маленьких объемах данных часто работают хуже, чем
двоичные представления. Однако для больших объемов данных троичные и
четверичные представления часто приносят ускорение от 5 до 10\%.

\begin{exercise}\label{ex:9.17}
  Реализуйте триномиальные кучи, используя тип
  \begin{lstlisting}
    datatype Tree = Node of Elem.T $\times$ (Tree $\times$ Tree) list
    datatype Digit = Zero | One of Tree | Two of Tree $\times$ Tree
    type Heap = Digit list
  \end{lstlisting}
\end{exercise}

\begin{exercise}\label{ex:9.18}
  Реализуйте безнулевые четверичные списки с произвольным доступом на
  основе типа
  \begin{lstlisting}
    datatype $\alpha$ Tree = Leaf of $\alpha$ | Node of $\alpha$ Tree vector.
    datatype $\alpha$ RList = $\alpha$ Tree vector list
  \end{lstlisting}
  где каждый вектор в \lstinline!Node! содержит по четыре дерева, а
  каждый вектор в списке содержит от одного до четырёх деревьев.
\end{exercise}

\begin{exercise}\label{ex:9.19}
  Можно также приспособить к произвольному основанию понятие
  скошенного двоичного числа. В скошенных $k$-ичных числах $i$-я цифра
  имеет вес $(k^{i+1} - 1) / (k - 1)$. Цифры выбираются из набора
  $\{0, \ldots, k-1\}$, плюс младшая ненулевая цифра может равняться
  $k$. Реализуйте скошенные троичные списки с произвольным доступом на
  основе типа
  \begin{lstlisting}
    datatype $\alpha$ Tree = Leaf of $\alpha$ | Node of $\alpha$ $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree $\times$ $\alpha$ Tree
    type $\alpha$ RList = (int $\times$ $\alpha$ Tree) list
  \end{lstlisting}
\end{exercise}

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

Структуры данных, которые можно описать как числовые представления,
встречаются на удивление часто, но явным образом связь с
каким-либо вариантом системы счисления упоминают лишь изредка
\cite{Guibas-etal1977, Myers1983, CarlssonMunroPoblete1988,
  KaplanTarjan1996b}. Скошенные списки с произвольным доступом впервые
появились в \cite{Okasaki1996b}. Скошенные биномиальные кучи
описаны в \cite{BrodalOkasaki1996}.

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