Персистентная очередь

TL;DR

Персистентная очередь (persistent queue) — очередь, сохраняющая все свои версии: каждая операция возвращает новую очередь, а прежние состояния остаются доступными. Простейший способ — копировать очередь целиком — стоит [math]\displaystyle{ \Theta(n) }[/math] на операцию и [math]\displaystyle{ \Theta(n^2) }[/math] суммарно, что неприемлемо. Очередь на двух неизменяемых стеках ([math]\displaystyle{ front }[/math] — голова, [math]\displaystyle{ back }[/math] — хвост) даёт push за [math]\displaystyle{ O(1) }[/math] и разделяет узлы версий, но pop при пустом [math]\displaystyle{ front }[/math] требует разворота [math]\displaystyle{ back }[/math] за [math]\displaystyle{ \Theta(n) }[/math]; хуже того, при ветвлении версий амортизация ломается — одну и ту же дорогую операцию можно повторить из разных версий. Поэтому персистентные очереди строят иначе: банкирская и физическая очереди (Окасаки) дают [math]\displaystyle{ O(1) }[/math] амортизированно с помощью ленивых потоков и кредита/потенциала, а очередь реального времени — [math]\displaystyle{ O(1) }[/math] в худшем случае (реализуется, например, на шести стеках; см. Очередь на шести стеках).

Свойство	Значение
Класс	Очередь (FIFO) с полной персистентностью
Версии	Хранятся все; доступ к любой за [math]\displaystyle{ O(1) }[/math]
Цена версии	от [math]\displaystyle{ \Theta(n) }[/math] (копия или разворот) до [math]\displaystyle{ O(1) }[/math] (ленивые/реальное время)
push	[math]\displaystyle{ O(1) }[/math] (1 новый узел)
pop (two-stack, энергично)	[math]\displaystyle{ O(1) }[/math] или [math]\displaystyle{ \Theta(n) }[/math] при развороте
Амортизация	[math]\displaystyle{ O(1) }[/math] для банкирской/физической; не работает при ветвлении «в лоб»
Худший случай	[math]\displaystyle{ O(1) }[/math] только у очереди реального времени
Приёмы	ленивые потоки, планировщик, кредит (banker's), потенциал (physicist's)
Реализации	два стека; банкирская; физическая; реального времени (6 стеков)
Где встречается	функциональные языки, версионирование, undo, инкрементальные вычисления

Определения

Персистентная очередь — очередь (FIFO), операция над которой порождает новую версию, не разрушая предыдущую. Подробнее об уровнях персистентности — в Персистентный стек: различают частичную (менять можно только последнюю версию), полную (любую) и функциональную (ячейки памяти неизменяемы) персистентность. Персистентная очередь обычно строится как функциональная: узлы и стеки неизменяемы.

Версия очереди — конкретное состояние очереди (последовательность элементов). Операция — это функция, отображающая версию в новую версию.

Разделение (sharing) — переиспользование неизменяемых узлов несколькими версиями. Благодаря ему [math]\displaystyle{ n }[/math] операций push занимают [math]\displaystyle{ O(n) }[/math] памяти, а не [math]\displaystyle{ \Theta(n^2) }[/math].

Представление на двух стеках. Очередь хранится парой неизменяемых стеков: [math]\displaystyle{ front }[/math] содержит голову очереди (верх — самый старый элемент), [math]\displaystyle{ back }[/math] — хвост (верх — самый новый). Логическая последовательность равна [math]\displaystyle{ front }[/math] (сверху вниз) [math]\displaystyle{ \mathbin{+\!\!+} }[/math] [math]\displaystyle{ \mathrm{reverse}(back) }[/math].

Ленивый поток (lazy stream) — последовательность, хвост которой вычисляется не сразу, а по требованию. Невычисленный хвост хранится как thunk (отложенное вычисление). Форсирование thunk — вычисление отложенной части.

Планировщик (scheduler) — механизм, который форсирует отложенную работу маленькими порциями (например, по одному узлу за операцию), чтобы не было отдельных дорогих вызовов.

Банкирская очередь (banker's queue). Персистентная очередь с ленивым разворотом, где каждый элемент несёт кредит, оплачивающий будущие шаги. Даёт [math]\displaystyle{ O(1) }[/math] амортизированно [3][4].

Физическая очередь (physicist's queue). Та же цель, но оплата через потенциал [math]\displaystyle{ \Phi = |back| }[/math] (метод потенциала Тарьяна) [3][5].

Очередь в реальном времени (real-time queue). Персистентная очередь с [math]\displaystyle{ O(1) }[/math] в худшем случае на операцию; планировщик форсирует постоянное число шагов за операцию [1][3].

Обозначения. [math]\displaystyle{ n }[/math] — число элементов/операций; [math]\displaystyle{ |X| }[/math] — размер структуры [math]\displaystyle{ X }[/math]; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Обычная очередь хранит одно состояние: enqueue/dequeue изменяют его на месте (см. Очередь). Если нужны прошлые состояния, приходится либо копировать очередь перед каждым изменением, либо вовсе отказаться от персистентности. Копирование обходится [math]\displaystyle{ \Theta(n) }[/math] на операцию и [math]\displaystyle{ \Theta(n^2) }[/math] на [math]\displaystyle{ n }[/math] версий — это слишком дорого. См. рис. 1.

Рис. 1. Каждая операция создаёт новую версию; старые версии живут, и от любой можно ветвить.

Придумать персистентную очередь сложнее, чем персистентный стек. Стек — это одна цепочка, и push просто добавляет узел в начало (см. Персистентный стек). У очереди два конца, и FIFO приходится восстанавливать разворотом. Первое естественное решение — два неизменяемых стека: push идёт в [math]\displaystyle{ back }[/math] (это дешёвый «стек», поэтому [math]\displaystyle{ O(1) }[/math]), pop берёт из [math]\displaystyle{ front }[/math]; когда [math]\displaystyle{ front }[/math] пуст, стек [math]\displaystyle{ back }[/math] разворачивается в [math]\displaystyle{ front }[/math]. Разворот — это [math]\displaystyle{ \Theta(|back|) }[/math], и вся трудность персистентности в том, как с ним справиться.

Второе ключевое наблюдение — амортизация не переносится на персистентные структуры. В мутирующей очереди один разворот за [math]\displaystyle{ \Theta(n) }[/math] «оплачивается» [math]\displaystyle{ n }[/math] последующими дешёвыми pop: амортизированно [math]\displaystyle{ O(1) }[/math]. В персистентной структуре ту же дорогую операцию можно запустить из разных версий, и каждый раз она выполняется заново — амортизированная граница для отдельной цепочки операций не даёт гарантии. См. рис. 3. Именно поэтому для персистентных очередей указывают либо честную [math]\displaystyle{ O(1) }[/math] в худшем случае, либо используют ленивые вычисления, чтобы амортизация «принадлежала структуре», а не последовательности вызовов.

Ключевая идея в одном абзаце: разворот нужно сделать ленивым и оплачиваемым по частям. Если хвост очереди хранить как ленивый поток, обратный порядок получается бесплатно до момента обращения; а планировщик, форсирующий работу по одному шагу за операцию, устраняет «долгие» вызовы. Это и есть банкирская, физическая и очередь реального времени.

Устройство

Персистентная очередь на двух стеках — это пара неизменяемых стеков и функция, возвращающая новую пару (см. рис. 2). Версии образуют дерево: каждое push/pop добавляет в него узел.

Рис. 2. push идёт в [math]\displaystyle{ back }[/math], pop берёт из [math]\displaystyle{ front }[/math]; при пустом [math]\displaystyle{ front }[/math] стек [math]\displaystyle{ back }[/math] разворачивается.

Основные компоненты и правила:

• [math]\displaystyle{ front }[/math] — головная часть в прямом порядке (верх — самый старый);
• [math]\displaystyle{ back }[/math] — хвостовая часть в обратном порядке (верх — самый новый);
• push(x) — новая версия с [math]\displaystyle{ back.push(x) }[/math]: [math]\displaystyle{ O(1) }[/math], один новый узел;
• pop() — верх [math]\displaystyle{ front }[/math]; если [math]\displaystyle{ front }[/math] пуст, сначала [math]\displaystyle{ front \leftarrow \mathrm{reverse}(back) }[/math], затем [math]\displaystyle{ back \leftarrow \varnothing }[/math];
• empty() — [math]\displaystyle{ front }[/math] и [math]\displaystyle{ back }[/math] пусты.

Логическая инвариантность представления: очередь равна [math]\displaystyle{ front \mathbin{+\!\!+} \mathrm{reverse}(back) }[/math]. Пока [math]\displaystyle{ front }[/math] не пуст, pop дешёвый; дорогой шаг — исключительно разворот [math]\displaystyle{ back }[/math].

Почему не годится «в лоб» (см. рис. 3). Общий для нескольких версий стек [math]\displaystyle{ back }[/math] нельзя развернуть один раз «для всех»: каждая версия, где [math]\displaystyle{ front }[/math] пуст, вынуждена строить свой разворот, то есть платить [math]\displaystyle{ \Theta(n) }[/math]. Значит, наивный энергичный вариант даёт худший случай [math]\displaystyle{ \Theta(n) }[/math] и не спасается амортизацией.

Рис. 3. Общий [math]\displaystyle{ back }[/math] и две ветви: каждая ветвь платит за разворот заново, поэтому одна операция снова может стоить [math]\displaystyle{ \Theta(n) }[/math].

Как исправляют. Два приёма (см. рис. 4):

• Лень (lazy). Хвост хранится как поток, разворот не вычисляется заранее. Обращение к нему форсирует thunk. Это превращает цену разворота в «отложенный долг», который можно оплачивать постепенно.
• Планировщик + кредит/потенциал. Банкирская очередь выдаёт каждому элементу кредит на будущие форсирования; физическая списывает работу с потенциала. Планировщик форсирует по шагу за операцию, и худшего вызова не остаётся.

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

Операции и алгоритмы

Ниже — операции персистентной очереди на двух стеках (энергичный вариант; он корректен, но имеет худший случай [math]\displaystyle{ \Theta(n) }[/math]). Обозначения: [math]\displaystyle{ Q = (F, B) }[/math] — пара стеков; push/pop стеков возвращают новые стеки; [math]\displaystyle{ \mathrm{reverse}(S) }[/math] — разворот.

Операция: Push

Идея. Положить элемент в хвостовой стек [math]\displaystyle{ back }[/math] — это операция над стеком, то есть [math]\displaystyle{ O(1) }[/math] и один новый узел; головной стек не трогаем.

Пошаговое описание:

1. Построить новую версию: [math]\displaystyle{ back' \leftarrow back.\mathrm{push}(x) }[/math].
2. Вернуть [math]\displaystyle{ (front, back') }[/math].

Инвариант. Очередь версии равна [math]\displaystyle{ front \mathbin{+\!\!+} \mathrm{reverse}(back) }[/math]; добавление в конец не меняет голову.

Операция Push(Q, x)
Вход:  версия Q = (F, B); x — элемент
Выход: новая версия Q'
Инвариант: Q = F ++ reverse(B)
Сложность: O(1) времени, O(1) новых узлов

1  B' ← B.push(x)
2  return (F, B')

Крайние случаи. push в пустую очередь даёт [math]\displaystyle{ (∅, \{x\}) }[/math]: pop сразу потребует разворота.

Операция: Pop

Идея. Взять голову из [math]\displaystyle{ front }[/math]. Если [math]\displaystyle{ front }[/math] пуст, развернуть [math]\displaystyle{ back }[/math] в [math]\displaystyle{ front }[/math]; вернуть верхний элемент и новую версию с «отрезанной» головой.

Пошаговое описание:

1. Если очередь пуста — ошибка underflow.
2. Если [math]\displaystyle{ front = ∅ }[/math]: [math]\displaystyle{ F \leftarrow \mathrm{reverse}(back) }[/math], [math]\displaystyle{ B \leftarrow ∅ }[/math].
3. [math]\displaystyle{ x \leftarrow front.\mathrm{top}() }[/math].
4. Вернуть [math]\displaystyle{ (x, (front.\mathrm{pop}(), back)) }[/math].

Инвариант. Возвращаемый [math]\displaystyle{ x }[/math] — самый старый элемент; новая версия содержит очередь без него.

Операция Pop(Q)
Вход:  версия Q = (F, B), Q ≠ (∅, ∅)
Выход: (x, Q') — головной элемент и новая версия
Инвариант: x — минимальный по времени поступления
Сложность: O(1), если F ≠ ∅; иначе Θ(|B|) — разворот

1  if F = ∅ and B = ∅
2      error "pop из пустой очереди"
3  if F = ∅
4      F ← Reverse(B)                 # самая дорогая операция
5      B ← ∅
6  x ← F.top()
7  return (x, (F.pop(), B))

Функция Reverse(S)                    # разворот стека за O(|S|)
1  R ← ∅
2  while S ≠ ∅
3      R ← R.push(S.top())
4      S ← S.pop()
5  return R

Разбор. Для [math]\displaystyle{ Q = (∅, \{3,2,1\}) }[/math] (верх [math]\displaystyle{ back }[/math] — 3) pop разворачивает [math]\displaystyle{ back }[/math] в [math]\displaystyle{ front = \{1,2,3\} }[/math], возвращает 1 и даёт версию [math]\displaystyle{ (\{2,3\}, ∅) }[/math]. Следующие pop дешёвые, пока [math]\displaystyle{ front }[/math] не опустеет.

Сложность. [math]\displaystyle{ O(1) }[/math] при непустом [math]\displaystyle{ front }[/math]; [math]\displaystyle{ \Theta(|back|) }[/math] при развороте. Амортизированно по одной линии операций — [math]\displaystyle{ O(1) }[/math], но при ветвлении это не гарантия (см. рис. 3).

Крайние случаи. pop пустой очереди — ошибка. Ветвление после разворота повторяет разворот в каждой ветви.

Техники: банкирская, физическая, реального времени

Ленивый разворот. Вместо немедленного [math]\displaystyle{ \mathrm{reverse}(back) }[/math] строят поток reverse(back), хвост которого — thunk. Обращение к потоку форсирует его. Так как узлы разделяются, отложенная работа выполняется не более одного раза на версию.

Банкирская очередь. Каждому элементу при push выдаётся кредит; форсирование шага разворота списывает кредит. Инвариант «кредитов достаточно» гарантирует [math]\displaystyle{ O(1) }[/math] амортизированно, даже при передаче версий между вызовами [3][4].

Физическая очередь. Вместо явного кредита — потенциал [math]\displaystyle{ \Phi = |back| }[/math]; амортизированная стоимость операции [math]\displaystyle{ \hat{c} = c + \Delta\Phi }[/math] остаётся [math]\displaystyle{ O(1) }[/math] [3][5]. При [math]\displaystyle{ \Phi = |back| }[/math]: push даёт [math]\displaystyle{ \Delta\Phi = +1 }[/math] (запас), pop из непустого [math]\displaystyle{ front }[/math] — [math]\displaystyle{ \Delta\Phi = 0 }[/math], разворот — [math]\displaystyle{ \Delta\Phi = -|back| }[/math]; поэтому амортизированная стоимость разворота равна 0 и оплачена предыдущими push.

Очередь реального времени. Планировщик форсирует постоянное число шагов за операцию (в шестистековой версии — до трёх переносов), поэтому отдельный вызов всегда [math]\displaystyle{ O(1) }[/math]. Конкретная реализация — на шести (или пяти персистентных) стеках, разобрана в Очередь на шести стеках.

Сводная таблица сложности

Операция	Два стека (энергично)	Ленивая (банкирская/физическая)	Реального времени
push	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
pop	[math]\displaystyle{ O(1) }[/math] / [math]\displaystyle{ \Theta(n) }[/math] разворот	[math]\displaystyle{ O(1) }[/math] амортизированно	[math]\displaystyle{ O(1) }[/math] в худшем
empty	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Доступ к версии	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Новых ячеек на push	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Новых ячеек на разворот	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math] на разворот, [math]\displaystyle{ O(1) }[/math] аморт.	[math]\displaystyle{ O(1) }[/math] на операцию
Персистентность	полная	полная	полная

Оговорка: амортизированная граница [math]\displaystyle{ O(1) }[/math] для ленивых очередей действительна благодаря тому, что кредит/потенциал принадлежат структуре, а не последовательности вызовов. Наивная энергичная очередь на двух стеках такой гарантии не даёт при ветвлении версий.

Трассировка примера

Возьмём последовательность push(1), push(2), push(3), затем два pop, затем ветвление от третьей версии через push(9). Стеки записаны сверху вниз (верх … дно).

№	Операция	Версия [math]\displaystyle{ (F, B) }[/math]	Логическая очередь	Комментарий
v0	старт	[math]\displaystyle{ (∅, ∅) }[/math]	[]	пусто
v1	push(1)	[math]\displaystyle{ (∅, [1]) }[/math]	[1]	в [math]\displaystyle{ back }[/math]
v2	push(2)	[math]\displaystyle{ (∅, [2,1]) }[/math]	[1,2]	в [math]\displaystyle{ back }[/math]
v3	push(3)	[math]\displaystyle{ (∅, [3,2,1]) }[/math]	[1,2,3]	в [math]\displaystyle{ back }[/math]
v4	pop() → 1	[math]\displaystyle{ ([2,3], ∅) }[/math]	[2,3]	разворот [math]\displaystyle{ back }[/math] (Θ(n))
v5	pop() → 2	[math]\displaystyle{ ([3], ∅) }[/math]	[3]	дешёвый
b	v3.push(9)	[math]\displaystyle{ (∅, [9,3,2,1]) }[/math]	[1,2,3,9]	ветвь от v3
c	v3.pop() → 1	[math]\displaystyle{ ([2,3], ∅) }[/math]	[2,3]	своя версия разворота

Разберём ветвление. Версия v3 не изменилась, хотя от неё построены и [math]\displaystyle{ b }[/math], и [math]\displaystyle{ c }[/math]: узлы делятся, но разворот в [math]\displaystyle{ c }[/math] выполняется заново (в [math]\displaystyle{ b }[/math] он вообще не нужен). Это ровно тот случай, из-за которого энергичная реализация не имеет [math]\displaystyle{ O(1) }[/math] в худшем случае, — см. рис. 3. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность FIFO

Инвариант представления. Логическая очередь версии [math]\displaystyle{ (F, B) }[/math] равна [math]\displaystyle{ F \mathbin{+\!\!+} \mathrm{reverse}(B) }[/math].

База. Пустая очередь [math]\displaystyle{ (∅, ∅) }[/math] соответствует пустой последовательности.

Переход push. Новая версия [math]\displaystyle{ (F, B.\mathrm{push}(x)) }[/math]: логически [math]\displaystyle{ F \mathbin{+\!\!+} \mathrm{reverse}(B.\mathrm{push}(x)) = F \mathbin{+\!\!+} \mathrm{reverse}(B) \mathbin{+\!\!+} [x] }[/math], то есть [math]\displaystyle{ x }[/math] в конце. Инвариант сохранён.

Переход pop. Если [math]\displaystyle{ F \neq ∅ }[/math], верх [math]\displaystyle{ F }[/math] — самый старый элемент (инвариант), и новая версия [math]\displaystyle{ (F.\mathrm{pop}(), B) }[/math] убирает именно его. Если [math]\displaystyle{ F = ∅ }[/math], логическая очередь равна [math]\displaystyle{ \mathrm{reverse}(B) }[/math]; замена [math]\displaystyle{ F \leftarrow \mathrm{reverse}(B) }[/math], [math]\displaystyle{ B \leftarrow ∅ }[/math] сохраняет её, а верх нового [math]\displaystyle{ F }[/math] — самый старый элемент [math]\displaystyle{ B }[/math], то есть голова очереди. Значит, pop возвращает корректный элемент.

Отсюда: pop всегда возвращает минимальный по времени поступления элемент, то есть очередь работает по FIFO, и все версии корректны.

Персистентность

Утверждение. Операции не изменяют уже существующие узлы.

Доказательство. push создаёт новый узел со ссылкой на прежнюю вершину, pop возвращает существующий узел, а [math]\displaystyle{ \mathrm{reverse} }[/math] создаёт новые узлы, читая старые. Ни одно поле ранее созданного узла не присваивается. Значит, любая сохранённая ссылка на версию остаётся действительной — персистентность полная (можно продолжать любую версию).

Оценка памяти

[math]\displaystyle{ n }[/math] операций push создают ровно [math]\displaystyle{ n }[/math] узлов (по одному на push), которые делят версии (см. рис. 5). Развороты создают дополнительные узлы, но каждый — новый; при энергичном варианте один разворот даёт [math]\displaystyle{ \Theta(n) }[/math] узлов. Если требуется именно [math]\displaystyle{ O(1) }[/math] новых ячеек на операцию, разворот должен быть ленивым (амортизированно [math]\displaystyle{ O(1) }[/math]) или распределённым (худший случай [math]\displaystyle{ O(1) }[/math]).

Рис. 5. Версии делят общие узлы: [math]\displaystyle{ O(n) }[/math] против [math]\displaystyle{ \Theta(n^2) }[/math] при копировании.

Почему амортизация не переносится на персистентность

В мутирующей структуре каждая операция выполняется один раз, поэтому суммарная стоимость делится на число операций. В персистентной структуре одну операцию можно выполнить из разных версий — например, первый pop после длинной серии push запускает разворот, и если от той же версии ветвятся [math]\displaystyle{ k }[/math] раз, разворот повторится [math]\displaystyle{ k }[/math] раз. Классический метод потенциала, привязанный к последовательности вызовов, теряет силу.

Как это лечат. Окасаки показал, что амортизация сохраняется, если «долг» хранится в самой структуре: банкирская очередь несёт кредиты, физическая — потенциал [math]\displaystyle{ \Phi = |back| }[/math]. Тогда любые списания (debits) ограничены накопленным кредитом, и [math]\displaystyle{ O(1) }[/math] амортизированно держит даже при передаче версий [3][4]. Для [math]\displaystyle{ O(1) }[/math] в худшем случае применяют планировщик: одна операция — постоянное число шагов, что даёт очередь реального времени [1][3].

Сравнение с альтернативами

Реализация	Худший	Амортизир.	Новых ячеек	Замечание
Копия всей очереди	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	просто, но [math]\displaystyle{ \Theta(n^2) }[/math] на историю
Два стека (энергично)	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math] «в линии»	[math]\displaystyle{ O(1) }[/math] push, [math]\displaystyle{ \Theta(n) }[/math] разворот	амортизация не переносится
Банкирская (Okasaki)	до [math]\displaystyle{ O(n) }[/math] при форсировании	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] аморт.	кредиты в структуре
Физическая (Okasaki)	до [math]\displaystyle{ O(n) }[/math] при форсировании	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] аморт.	потенциал [math]\displaystyle{ \Phi }[/math]
Реального времени	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	планировщик / 6 стеков

Сводка по пяти реализациям — на рис. 6.

Рис. 6. От копирования ([math]\displaystyle{ \Theta(n) }[/math] на версию) до очереди реального времени ([math]\displaystyle{ O(1) }[/math]).

Вердикт. Нужны простые версии и допустимы амортизированные оценки — два стека или банкирская очередь. Нужна жёсткая гарантия времени отклика — очередь реального времени (Очередь на шести стеках). Копирование версий оправдано лишь на крошечных размерах.

Где применяется

1. Функциональные языки. В Haskell стандартные последовательности и библиотечные очереди персистентны; в OCaml и Standard ML есть как функциональные, так и мутабельные реализации. Банкирская и физическая очереди Окасаки — учебный канон и основа библиотечных реализаций. Почему: в чистом функциональном коде мутация запрещена, а старые версии нужно сохранять [3][4].

1. Версионирование и системы контроля версий. История изменений — это дерево версий структуры; персистентная структура хранит её без копирования данных. Почему: ветвление версий и откаты выполняются за [math]\displaystyle{ O(1) }[/math] по указателям [4][6].

1. Undo/redo и редакторы. Стек или очередь действий с историей строится из персистентных структур: каждое действие — новая версия, откат — переход по ссылке. Почему: [math]\displaystyle{ O(1) }[/math] новая память на действие и отсутствие блокировок.

1. Инкрементальные вычисления и кэширование. Персистентные структуры позволяют сравнивать версии и переиспользовать общие части (например, при мемоизации путей). Почему: sharing экономит память и время [4].

1. Параллельные вычисления. Неизменяемые версии безопасно разделяются потоками без синхронизации. Почему: нельзя испортить состояние, разделяемое несколькими потребителями [4].

Историческая справка

Очереди в реальном времени впервые описали Худ и Мелвилл (R. Hood, R. Melville) в работе Real Time Queue Operations in Pure LISP (Cornell University, 1980), где данные неизменяемы, а перенос работы распределён по операциям [2]. Идею ленивых очередей развил Ф. У. Бартон (F. W. Burton) в статье An Efficient Functional Implementation of FIFO Queues (Information Processing Letters, 1982) [8]. Наиболее известные конструкции — банкирская и физическая очереди (с ленивыми потоками и кредитом/потенциалом) и очередь реального времени — принадлежат Крису Окасаки (статья Simple and Efficient Purely Functional Queues and Deques, Journal of Functional Programming, 1995; книга Purely Functional Data Structures, Cambridge University Press, 1998) [3].

Общую теорию персистентности (методы path copying, fat nodes, node copying) заложили Дрисколл, Сарнак, Слитор и Тарьян (Making Data Structures Persistent, STOC 1986; JCSS 1989) [6]. Формальный амортизированный анализ, включая вошедший в обиход метод потенциала, развил Роберт Тарьян («Amortized Computational Complexity», 1985) [5]. Функциональные структуры-предшественники — списки LISP (Джон Маккарти, 1960).

Типичные ошибки и подводные камни

• Переносить амортизацию на персистентную структуру. Оценка [math]\displaystyle{ O(1) }[/math] «в линии» не означает [math]\displaystyle{ O(1) }[/math] при ветвлении: одну дорогую операцию можно повторить из разных версий.
• Считать персистентную очередь «просто очередью на двух стеках». Без лени/планировщика худший случай остаётся [math]\displaystyle{ \Theta(n) }[/math].
• Форсировать весь ленивый поток в одной операции. Это возвращает [math]\displaystyle{ \Theta(n) }[/math] в отдельный вызов; нужно форсировать маленькими порциями.
• Забыть про инвариант кредита/потенциала. Без него ленивая очередь теряет амортизированную оценку (кредиты могут «закончиться»).
• Мутировать разделяемые узлы. Любая запись в общий узел испортит все версии, которые на него ссылаются.
• Освобождать узлы «оптимизацией». Узел можно удалять, только когда на него не ссылается ни одна живая версия (нужна сборка мусора).
• Путать дебет и кредит. В банкирской очереди pop может ничего не форсировать, но при определённых условиях обязан заплатить лишний кредит; пропуск этого нарушает инвариант.
• Ожидать [math]\displaystyle{ O(1) }[/math] от разворота eager-варианта. Создание [math]\displaystyle{ \Theta(n) }[/math] узлов на разворот — самая дорогая операция; она и есть источник проблем.
• Хранить версии без нужды. Если ветвление не требуется, персистентность — лишние накладные расходы; иногда достаточно мутирующей очереди.

Задачи для практики

1. Две версии. Реализуйте персистентную очередь на двух неизменяемых стеках с push и pop. Ограничение: узлы неизменяемы. Подсказка: pop при пустом [math]\displaystyle{ front }[/math] разворачивает [math]\displaystyle{ back }[/math].

1. Ветвление. Постройте очередь [1,2,3], сделайте ветвь push(4) и ветвь pop. Сколько версий получилось и каковы их содержимые? Подсказка: обе ветви происходят от одной версии.

1. Амортизация. Докажите, что в одной линии операций энергичный вариант амортизированно [math]\displaystyle{ O(1) }[/math], и приведите пример ветвления, где отдельный pop стоит [math]\displaystyle{ \Theta(n) }[/math]. Подсказка: [math]\displaystyle{ n }[/math] дешёвых pop оплачивают один разворот; при ветвлении разворот повторяется.

1. Память. Покажите, что [math]\displaystyle{ n }[/math] операций push без разворотов дают ровно [math]\displaystyle{ n }[/math] узлов. Оцените дополнительные узлы при одном развороте. Подсказка: разворот создаёт [math]\displaystyle{ \Theta(n) }[/math] узлов.

1. Ленивый разворот. Опишите, как хранить reverse(back) в виде thunk и когда его форсировать. Подсказка: форсируйте по требованию головы.

1. Кредит. Для банкирской очереди придумайте правило выдачи кредитов при push и списания при форсировании так, чтобы инвариант «кредитов хватает» сохранялся. Подсказка: один кредит на элемент оплачивает один шаг разворота.

1. Потенциал. Для физической очереди вычислите [math]\displaystyle{ \Delta\Phi }[/math] при push и pop и покажите [math]\displaystyle{ \hat{c} = O(1) }[/math]. Подсказка: [math]\displaystyle{ \Phi = |back| }[/math].

1. Реальное время. Объясните, почему очереди с [math]\displaystyle{ O(1) }[/math] в худшем случае строят на нескольких стеках, а не на ленивых потоках напрямую. Подсказка: форсирование должно быть по шагу на операцию (см. Очередь на шести стеках).

Связанные темы

• Очередь — обычная FIFO-очередь; кольцевой буфер.
• Персистентный стек — базовый неизменяемый стек.
• Очередь на шести стеках — очередь реального времени и персистентный вариант на пяти стеках.
• Асимптотическая сложность — амортизация, метод потенциала, худший случай.
• Персистентные структуры данных — общая теория персистентности.
• Декартово дерево — персистентный treap.

Источники

1. Викиконспекты ИТМО: Персистентная очередь. URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентная_очередь.
2. Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980. URL: http://hdl.handle.net/1813/6273.
3. Okasaki C. Simple and Efficient Purely Functional Queues and Deques // Journal of Functional Programming. — 1995. — Vol. 5, № 4.
4. Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998 (банкирская и физическая очереди, амортизация в функциональных структурах).
5. Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
6. Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; JCSS. — 1989. — Vol. 38.
7. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (очередь, стек), гл. 17 (амортизированный анализ).
8. Burton F. W. An Efficient Functional Implementation of FIFO Queues // Information Processing Letters. — 1982. — Vol. 14, № 5. — P. 205–206.