251
правка
Изменения
почти все фиксы
'''Персистентная очередь''' {{---}} это [[Очередь|очередь]], реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.
== Основная идея ==
Для создания персистентной очереди очень удобно пользоваться ее реализацией на [[Стек|стеках]], поскольку стеки легко сделать [[Персистентный стек|персистентными]], причем в этом случае мы добьемся функциональной персистентности. [[Очередь#Реализация на двух стеках|Реализация на двух стеках]] не подходит для этого, так как в худшем случае требует <tex>O(n)</tex> времени, а значит и <tex>O(n)</tex> памяти на операцию в случае персистентности. Покажем сначала, как создать очередь в реальном времени с <tex>O(1)</tex> времени на операцию, а затем превратим ее в персистентную.
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>\mathtt{push}</tex> и стек <tex>R</tex> для операций <tex>\mathtt{pop}</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> в правильном для извлечения порядке. Перекопирование (''recopy mode'') начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>\mathtt{pop}</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>\mathtt{recopy}</tex>.
Понятно, что во время перекопирования могут поступить операции <tex>\mathtt{push}</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, на первый взгляд, все станет хорошо.
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>\mathtt{push}</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
# Что вернуть при операции <tex>\mathtt{pop}</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>\mathtt{toCopy}</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex>, и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>\mathtt{pop}</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>\mathtt{toCopy}>0</tex>. Если во время операции <tex>\mathtt{pop}</tex> у нас <tex>\mathtt{toCopy } = 0</tex>, это означает, что теперь в стеке <tex>R</tex> находится весь правый кусок очереди, так что нам придется извлечь элемент из него.
Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>\mathtt{push}</tex>, а также <tex>n</tex> операций <tex>\mathtt{pop}</tex>. Заметим, что операция <tex>\mathtt{empty}</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</tex> операцию.
Посмотрим на дополнительные действия, которые нам предстоят:
# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex> действий.
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
# Переместить первые <tex>\mathtt{toCopy}</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</tex> действий.
# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</tex> действия.
Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось.
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>\mathtt{empty}</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>\mathtt{push}, \mathtt{pop}</tex>) поступило <tex>x</tex> операций <tex>\mathtt{pop}</tex>, <tex>n - x</tex> операций <tex>\mathtt{push}</tex>. Очевидно, что после перекопирования в новых стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.
Итак, очередь <tex>Q</tex> будет состоять из шести стеков <tex>L,L',R,Rc,Rc',T</tex>, а также двух внутренних переменных <tex>\mathtt{recopy}, \mathtt{toCopy}</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>\mathtt{copied}</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>T</tex>.
Инвариант очереди (обычный режим):
Инвариант очереди (режим перекопирования):
# <tex>Rc.size = \mathtt{toCopy}</tex>
# Если <tex>L.size = 0</tex>, то:
## При <tex>\mathtt{toCopy } > 0</tex> первые <tex>\mathtt{toCopy}</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>\mathtt{toCopy } \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке.
Очередь будет работать в двух режимах:
# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</tex>.
# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>\mathtt{empty} =\mathtt{false}</tex>, совершаем дополнительные действия.
Также после операции в обычном режиме следует проверка на активацию перекопирования (<tex>\mathtt{recopy } = (L.size > R.size)</tex>), если это так, <tex>\mathtt{toCopy} =R.size, \mathtt{recopy} =true, \mathtt{copied } = false</tex>, совершается первый набор дополнительных действий.
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>\mathtt{recopy} =(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
Следующий псевдокод выполняет требуемые операции:
=== empty ===
<code>
'''boolean''' empty():
'''return''' !recopy '''and''' R.size == 0
</code>
=== push ===
<code>
'''function''' push(x: '''T'''):
'''if''' !recopy
L.push(x)
=== pop ===
<code>
'''T''' pop():
'''if''' !recopy
'''T''' tmp = R.pop()
Rc.pop()
'''if''' Rc'.size > 0
'''return''' tmp
'''else'''
'''T''' tmp = Rc.pop()
'''if''' toCopy > 0
toCopy = toCopy - 1
=== checkRecopy ===
<code>
'''function''' checkRecopy() :
recopy = L.size > R.size
'''if''' recopy
=== checkNormal ===
<code>
'''function''' checkNormal():
additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
=== additionalOperations ===
<code>
'''function''' additionalOperations():
// Нам достаточно 3 операций на вызов
'''int''' toDo = 3
// Пытаемся перекопировать R в T
'''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0
'''while''' toDo > 0 '''and''' L.size > 0
copied = true
'''T''' x = L.pop()
R.push(x)
Rc'.push(x)
// Пытаемся перекопировать T в R и Rc' с учетом toCopy
'''while''' toDo > 0 '''and''' T.size > 0
'''T''' x = T.pop()
'''if''' toCopy > 0
R.push(x)
== Персистентная очередь на пяти стеках ==
После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными стеками, ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека <tex>R</tex>, так что достаточно всего пяти стеков.
Вместо стеков <tex>Rc, Rc'</tex> персистентная очередь хранит один стек <tex>R'</tex>, в который при активации перекопирования записывается последняя версия стека <tex>R</tex>, в дальнейшем все операции <tex>\mathtt{pop}</tex> обращаются именно к ней. Все замечания о <tex>\mathtt{toCopy}</tex> остаются в силе.
Также нам нет необходимости опустошать стек <tex>R'</tex> к моменту перекопирования, так как скопировать туда новую версию <tex>R</tex> мы можем за <tex>O(1)</tex>, а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.
В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}></tex>, содержащую пять версий персистентных стеков и три переменных.
Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><Sn, x></tex>, а операция <tex>S.push(x)</tex> возвращает <tex>Sn</tex>.
=== empty ===
<code>
'''boolean''' empty():
'''return''' !recopy '''and''' R.size == 0
</code>
=== push ===
<code>
'''function''' push(x: '''T'''):
'''if''' !recopy
'''stack<T>''' Ln = L.push(x) <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <Ln, L', R, R', T, recopy, toCopy, copied>
'''return''' Q'.checkRecopy()
'''else'''
'''stack<T>''' Ln' = L'.push(x) <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, Ln', R, R', T, recopy, toCopy, copied>
'''return''' Q'.checkNormal()
</code>
=== pop ===
<code>
<'''stack<T>''', '''T'''> pop():
'''if''' !recopy
<Rn, x> = R.pop()
<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', Rn, R', T, recopy, toCopy, copied>
'''return''' <Q'.checkRecopy(), x>
'''else'''
<Rn', x> = R'.pop()
'''int''' curCopy = toCopy
Rn = R
'''if''' toCopy > 0
=== checkRecopy ===
<code>
<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkRecopy() :
'''if''' L.size > R.size
<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', R, R', T, true, R.size, false>
'''return''' Q'.checkNormal()
'''else'''
=== checkNormal ===
<code>
<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkNormal():
Q' = Q.additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
=== additionalOperations ===
<code>
<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> additionalOperations():
// Нам достаточно 3 операций на вызов
'''int''' toDo = 3
// Пытаемся перекопировать R в T
'''stack<T>''' Rn = R '''stack<T>''' Tn = T '''boolean''' curCopied = copied
'''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0
<Rn, x> = Rn.pop()
curCopy = curCopy - 1
toDo = toDo - 1
'''stack<T>''' Ln' = L'
// Если все скопировано, то меняем роли L1, L2
'''if''' T.size == 0
</code>
== Пример ==
Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(1) } </tex>, изначально режим обычный, так что элемент пойдет в стек <tex>L</tex>. Эта операция активирует режим перекопирования, в результате которого содержимое <tex>L</tex> перекопируется в стек <tex>R</tex>, после чего перекопирование завершится, стеки <tex>L, L'</tex> поменяются местами.
[[Файл:PersistentQueue_state1.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(2) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state2.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(3) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, активируется перекопирование, <tex>R' = R</tex>, за три операции мы успеваем перекопировать элемент стека <tex>R</tex> в стек <tex>T</tex>, а также перекопировать два элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state3.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(4) } </tex>, мы в режиме перекопирования, поэтому элемент пойдет в стек <tex>L'</tex>, далее мы успеваем перекопировать обратно элемент из стека <tex>T</tex> в стек <tex>R</tex>, перекопирование завершается, стеки <tex>L, L'</tex> меняются местами.
[[Файл:PersistentQueue_state4.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(5) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state5.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(6) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state6.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> \mathtt{push(7) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование активируется, <tex>R' = R</tex>, <tex>\mathtt{toCopy} =3</tex>, за три операции мы успеваем перекопировать содержимое стека <tex>R</tex> в стек <tex>T</tex>.
[[Файл:PersistentQueue_state7.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy } = 2</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state8.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy } = 1</tex>. За три операции мы успеваем перекопировать один элемент стека <tex>L</tex> в стек <tex>R</tex>, а также извлечь два элемента стека <tex>T</tex>, с учетом <tex>\mathtt{toCopy}</tex> только один элемент попадет в стек <tex>R</tex>, <tex>\mathtt{toCopy } = 0</tex>.
[[Файл:PersistentQueue_State9.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, но <tex>\mathtt{toCopy } = 0</tex>, так что нам приходится извлечь еше один элемент из стека <tex>R</tex>. Мы извлекаем один элемент из стека <tex>T</tex>, перекопирование заканчивается, стеки <tex>L, L'</tex> меняются местами.
[[Файл:PersistentQueue_state10.png|300px|nothumb|left|]]
<br clear = "all"/>
== См. также ==
*[[Персистентный стек]]
*[[Персистентный дек]]
*[[Персистентная приоритетная очередь]]
= Ссылки = Источники информации ==
* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
