Это разновидность глобальной перестройки {global rebuilding}
## Порционная перестройка
Во многих структурах данных соблюдаются инварианты баланса, благодаря
которым гарантируется эффективный доступ. Каноническим примером могут
служить сбалансированные деревья поиска, улучшающие время работы в
худшем случае для многих операций с `O(n)` у несбалансированных
деревьев до `O(log n)`. Один из подходов к соблюдению инварианта
баланса - перебалансировка структуры после каждой её
модификации. Для большинства сбалансированных структур существует
понятие идеального баланса{perfect balance}, то есть,
конфигурация, минимизирующая стоимость последующих действий. Однако,
поскольку, как правило, восстанавливать идеальный баланс после
каждого изменения оказывается слишком дорого, в большинстве реализаций
считается достаточным поддерживать некоторое приближение к нему,
ухудшающее показатели не более чем на константный множитель. Примерами
такого подхода являются AVL-деревья
Однако если каждое отдельное обновление не слишком сильно влияет на
баланс, привлекательным альтернативным подходом будет отложить
перестройку, пока не пройдёт некоторая серия операций, а затем
перебалансировать всю структуру и восстановить идеальный
баланс. Назовем этот подход \term{порционной перестройкой}{batched
rebuilding}. Порционная перестройка дает хорошие амортизированные
ограничения, если выполняются два условия: (1) глобальная структура
перестраивается не слишком часто, и (2) отдельные модифицирующие
действия ухудшают показатели последующих операций не слишком
сильно. Выражаясь более точно, условие (1) говорит, что, если мы
надеемся достичь амортизированного показателя `O(f(n))` на операцию, а
преобразование перебалансировки занимает время `O(g(n))`, запускать
это преобразование нельзя чаще, чем раз в `c · g(n)/f (n)`
операций, для некоторой константы `c`. Рассмотрим, например, двоичные
деревья поиска. Перестройка дерева с полной балансировкой занимает
время O(n), так что, если мы хотим, чтобы наши операции занимали
амортизированное время не больше O(n), структуру данных нельзя
перестраивать чаще, чем раз в `c · n/ log n` операций, для
некоторой константы `c`.
Допустим, что структура данных будет перестраиваться раз в `c·g(n)/f(n)` операций, и что отдельная операция над перестроенной
структурой отнимает времяO(f(n)) (ограничение может быть жёстким
или амортизированным). В этом случае условие (2) утверждает, что,
сделав не более `c · g(n)/f(n)` обновлений непосредственно после
перестройки, мы по-прежнему будем тратить время не более
`O(f(n))`. Другими словами, стоимость каждой отдельной операции должна
ухудшиться максимум на константный множитель. Функции обновления,
удовлетворяющие условию (2), называются \term{операциями слабого
обновления}{weak updates}.
Рассмотрим, например, следующий подход к реализации функции
`delete` на двоичных деревьях поиска. Вместо того, чтобы
физически уничтожать указанный узел дерева, оставляем его в дереве с
пометкой **стёрто**. Затем, когда стёртыми оказываются половина
узлов, делаем глобальный проход, уничтожая стёртые узлы и
восстанавливая идеальный баланс. Удовлетворяет ли этот подход нашим
двум условиям, если мы хотим, чтобы уничтожение элемента занимало
амортизированное время `O(\log n)`?
Допустим, дерево содержит `n` узлов, из которых не более половины
помечено как стёртые. Уничтожение стёртых узлов и восстановление
идеального баланса в дереве занимает время `O(n)`. Мы выполняем это
преобразование раз в `1/2n` операций уничтожения, так что
условие (1) выполнено. На самом деле, условие (1) позволяет нам
перестраивать структуру даже чаще, раз в `c · n/ log n`
операций. Наивный алгоритм уничтожения ищет нужный узел и помечает его
как стёртый. Это отнимает время O(log n), даже если половина
узлов уже помечена как стёртые, так что условие (2) выполнено.
Заметим, что даже если половина узлов в дереве помечена, средняя
глубина активного узла больше всего на единицу по сравнению со
случаем, когда они физически уничтожены. Дополнительная глубина
ухудшает стоимость операции всего лишь на аддитивную константу, в то
время как условие (2) позволяет времени каждой операции ухудшаться на
константный множитель. Следовательно, условие (2) позволяет нам
перестраивать нашу структуру данных даже ещё реже.
### Глобальная перестройка
Основная идея
состоит в том, чтобы проводить трансформацию перестройки постепенно,
по несколько шагов при каждой нормальной операции. Полезно
рассматривать это как выполнение преобразования в
сопрограмме. Сложность в том, чтобы запустить сопрограмму достаточно
рано, чтобы она завершилась ко времени, когда понадобится
перестроенная структура.
Более конкретно, при глобальной перестройке поддерживаются две копии
каждого объекта. Первичная, или `рабочая копия{working copy}` - это
исходная структура. Вторичная копия - та, которая постепенно
перестраивается. Все запросы и операции обновления обращаются к рабочей
копии. Когда построение вторичной копии завершено, она становится
новой рабочей копией, а старая уничтожается. При этом либо сразу же
запускается новая вторичная копия, либо некоторое время объект может
работать без вторичной структуры, прежде чем начнётся новая фаза
перестройки.
Отдельную сложность представляет обработка обновлений, происходящих,
пока ведется перестройка вторичной копии. Рабочая копия обновляется
обычным образом, но должна быть обновлена и вторичная копия, иначе,
когда она станет рабочей, эффект обновления будет потерян. Однако в
общем случае вторичная копия представлена не в такой форме, которую
можно эффективно обновить. Таким образом, обновления вторичной копии
буферизуются и выполняются, по несколько за раз, после того, как
вторичная копия перестроена, но до того, как она становится рабочей.
Глобальную перестройку можно реализовать в чисто функциональном стиле,
и несколько таких реализаций существуют. Например, очереди реального
времени Худа и Мелвилла основаны именно на
этом методе. В отличие от порционной перестройки, при глобальной
перестройке не возникает проблем с устойчивостью. Поскольку ни одна из
операций не является особенно дорогой, произвольное повторение
операций не влияет на временные характеристики. К сожалению, часто
глобальная перестройка дает очень сложные структуры. В частности,
представление вторичной копии, которое сводится к хранению
промежуточного состояния сопрограммы, может быть довольно неприятным
### Ленивая перестройка
Реализация очередей по методу физика очень похожа на версию с глобальной перестройкой, но имеется и существенное
различие. Как и при глобальной перестройке, в этой реализации
поддерживаются две копии головного списка, рабочая копия \lstinline!w!
и вторичная копия \lstinline!f!, причем все запросы обращаются к
рабочей копии. Операции обновления `f` (т.е., операции
`tail`) буферизуются и выполняются по окончании проворота
через выражение
```
$tl (force f)
```
Кроме того, эта реализация заботится о том, чтобы начать
(или, по крайней мере, спланировать) проворот задолго до того, как
понадобится его результат. Однако, в отличие от глобальной
перестройки, эта реализация не занимается \emph{выполнением}
преобразования перестройки (т.е., проворота) в параллель с нормальными
операциями; вместо этого она оплачивает преобразование
перестройки одновременно с нормальными операциями, но затем, когда вся
стоимость преобразования выплачена, оно выполняется целиком. В
сущности, мы заменили сложности явного или неявного переноса
перестройки в сопрограмму более простым механизмом ленивого
вычисления. Этот вариант глобальной перестройки мы называем
ленивой перестройкой{lazy rebuilding}.
У глобальной перестройки есть два преимущества перед
порционной: она годится для реализации устойчивых структур данных, а
также соблюдает жёсткие ограничения вместо амортизированных. Ленивая
перестройка также обладает первым из этих преимуществ, однако, по
крайней мере, в простейшей своей форме дает амортизированные
ограничения. Но если это требуется, часто можно восстановить
жёсткие ограничения, используя расписания. например, очереди реального времени сочетают ленивую перестройку с расписанием, и
получают в итоге реализацию с жёсткими характеристиками. В сущности,
сочетание ленивой перестройки с расписаниями можно рассматривать как
разновидность глобальной перестройки, где сопрограммы реифицированы
особенно простым образом через ленивое вычисление.
### Двусторонние очереди
В качестве дальнейших примеров глобальной перестройки мы приведем
несколько реализаций двусторонних очередей, или деков{deques}. Деки отличаются от очередей FIFO тем, что элементы могут как добавляться, так и изыматься с любого конца очереди.
#### Деки с ограниченным выходом
Очередь, поддерживающая добавление элементов с обоих концов, но удаление только с одного, называется дек с ограниченным выходом{output-restricted deque}.
#### Деки по методу банкира
Деки можно представлять так же, как очереди, в виде двух потоков (или списков),
f и r, плюс некоторая дополнительная информация, помогающая поддерживать баланс. Для очередей идеально сбалансироанная с
ситуация - когда все элементы находятся в головном
потоке. Для деков идеально сбалансированное состояние - когда
элементы поделены поровну между головным и хвостовым
потоками. Поскольку мы не можем себе позволить восстанавливать
идеальный баланс после каждой операции, мы удовольствуемся гарантией,
что ни один из потоков не может быть длиннее другого более чем в `c`
раз, для некоторой константы `c > 1`. А именно, мы поддерживаем
следующий инвариант баланса:
```
|f|≤c|r|+1 ∧ |r|≤c|f|+1
```
#### Деки реального времени
Дек реального времени}{real-time deque} все операции выполняет
за $O(1)$ в худшем случае. Мы получаем деки реального времени на
основе деков из предыдущего раздела, снабжая головной и хвостовой
потоки расписаниями.
Как всегда, первый шаг в применении метода расписаний состоит в том,
чтобы преобразовать все монолитные функции в пошаговые.