Персистентная очередь — различия между версиями
Genyaz (обсуждение | вклад) (→checkRecopy) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 24 промежуточные версии 6 участников) | |||
Строка 1: | Строка 1: | ||
− | + | '''Персистентная очередь''' (англ. ''persistent queue'') {{---}} это [[Очередь|очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится. | |
− | == | + | == Основная идея == |
− | + | Для создания персистентной очереди очень удобно пользоваться ее реализацией на [[Стек|стеках]], поскольку стеки легко сделать [[Персистентный стек|персистентными]], причем в этом случае мы добьемся функциональной персистентности. [[Очередь#Реализация на двух стеках|Реализация на двух стеках]] не подходит для этого, так как в худшем случае требует <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>S</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>S</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>S</tex>, и уменьшается при каждом извлечении из <tex>S</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>Q</tex> будет состоять из | + | Посмотрим на дополнительные действия, которые нам предстоят: |
+ | # Переместить содержимое <tex>R</tex> в <tex>S</tex>, <tex>n</tex> действий. | ||
+ | # Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий. | ||
+ | # Переместить первые <tex>\mathtt{toCopy}</tex> элементов из <tex>S</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',S</tex>, а также двух внутренних переменных <tex>\mathtt{recopy}, \mathtt{toCopy}</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>\mathtt{copied}</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>S</tex>. | ||
Инвариант очереди (обычный режим): | Инвариант очереди (обычный режим): | ||
Строка 35: | Строка 41: | ||
# <tex>L.size \leqslant R.size</tex> | # <tex>L.size \leqslant R.size</tex> | ||
# <tex>R.size = 0 \equiv Q.size = 0</tex> | # <tex>R.size = 0 \equiv Q.size = 0</tex> | ||
− | # <tex>L'.size = 0, | + | # <tex>Rc</tex> {{---}} копия <tex>R</tex> |
+ | # <tex>Rc'.size < R.size - L.size</tex> | ||
+ | # <tex>L'.size = 0, S.size = 0</tex> | ||
+ | |||
+ | Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',S,Rc'</tex>, которые нам понадобятся. | ||
Инвариант очереди (режим перекопирования): | Инвариант очереди (режим перекопирования): | ||
− | # Если <tex>L.size = 0</tex>, то первые <tex>toCopy</tex> элементов <tex> | + | # <tex>Rc.size = \mathtt{toCopy}</tex> |
+ | # Если <tex>L.size = 0</tex>, то: | ||
+ | ## При <tex>\mathtt{toCopy} > 0</tex> первые <tex>\mathtt{toCopy}</tex> элементов <tex>S</tex> {{---}} корректны, то есть действительно содержатся в очереди. | ||
+ | ## При <tex>\mathtt{toCopy} \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке. | ||
Очередь будет работать в двух режимах: | Очередь будет работать в двух режимах: | ||
− | # Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex>, операция <tex>empty = (R.size = 0)</tex>. | + | # Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</tex>. |
− | # Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>R | + | # Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>\mathtt{empty} = \mathtt{false}</tex>, совершаем дополнительные действия. |
− | Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, | + | Также после операции в обычном режиме следует проверка на активацию перекопирования (<tex>\mathtt{recopy} = (L.size > R.size)</tex>), если это так, <tex>\mathtt{toCopy} = R.size, \mathtt{recopy} = true, \mathtt{copied} = false</tex>, совершается первый набор дополнительных действий. |
− | После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=( | + | После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>\mathtt{recopy} = (S.size == 0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>. |
− | В качестве версии очереди мы будем использовать запись <tex>Q= | + | Следующий псевдокод выполняет требуемые операции: |
− | Пусть персистентный стек возвращает вместе с обычным результатом стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex> | + | === empty === |
+ | <code> | ||
+ | '''boolean''' empty(): | ||
+ | '''return''' !recopy '''and''' R.size == 0 | ||
+ | </code> | ||
+ | === push === | ||
+ | <code> | ||
+ | '''function''' push(x : '''T'''): | ||
+ | '''if''' !recopy | ||
+ | L.push(x) | ||
+ | '''if''' Rc'.size > 0 | ||
+ | Rc'.pop() | ||
+ | checkRecopy() | ||
+ | '''else''' | ||
+ | L'.push(x) | ||
+ | checkNormal() | ||
+ | </code> | ||
+ | === pop === | ||
+ | <code> | ||
+ | '''T''' pop(): | ||
+ | '''if''' !recopy | ||
+ | '''T''' tmp = R.pop() | ||
+ | Rc.pop() | ||
+ | '''if''' Rc'.size > 0 | ||
+ | Rc'.pop() | ||
+ | checkRecopy() | ||
+ | '''return''' tmp | ||
+ | '''else''' | ||
+ | '''T''' tmp = Rc.pop() | ||
+ | '''if''' toCopy > 0 | ||
+ | toCopy = toCopy - 1 | ||
+ | '''else''' | ||
+ | R.pop() | ||
+ | Rc'.pop() | ||
+ | checkNormal() | ||
+ | '''return''' tmp | ||
+ | </code> | ||
+ | |||
+ | === checkRecopy === | ||
+ | <code> | ||
+ | '''function''' checkRecopy(): | ||
+ | recopy = L.size > R.size | ||
+ | '''if''' recopy | ||
+ | toCopy = R.size | ||
+ | copied = false | ||
+ | checkNormal() | ||
+ | </code> | ||
+ | |||
+ | === checkNormal === | ||
+ | <code> | ||
+ | '''function''' checkNormal(): | ||
+ | additionalOperations() | ||
+ | <span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span> | ||
+ | recopy = S.size <tex> \neq </tex> 0 | ||
+ | </code> | ||
+ | |||
+ | === additionalOperations === | ||
+ | <code> | ||
+ | '''function''' additionalOperations(): | ||
+ | <span style="color:#008000">// Нам достаточно 3 операций на вызов</span> | ||
+ | '''int''' toDo = 3 | ||
+ | <span style="color:#008000">// Пытаемся перекопировать R в S</span> | ||
+ | '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0 | ||
+ | S.push(R.pop()) | ||
+ | toDo = toDo - 1 | ||
+ | <span style="color:#008000">// Пытаемся перекопировать L в R и Rc'</span> | ||
+ | '''while''' toDo > 0 '''and''' L.size > 0 | ||
+ | copied = true | ||
+ | '''T''' x = L.pop() | ||
+ | R.push(x) | ||
+ | Rc'.push(x) | ||
+ | toDo = toDo - 1 | ||
+ | <span style="color:#008000">// Пытаемся перекопировать S в R и Rc' с учетом toCopy</span> | ||
+ | '''while''' toDo > 0 '''and''' S.size > 0 | ||
+ | '''T''' x = S.pop() | ||
+ | '''if''' toCopy > 0 | ||
+ | R.push(x) | ||
+ | Rc'.push(x) | ||
+ | toCopy = toCopy - 1 | ||
+ | toDo = toDo - 1 | ||
+ | <span style="color:#008000">// Если все скопировано, то меняем роли L, L' и Rc, Rc'</span> | ||
+ | '''if''' S.size == 0 | ||
+ | swap(L, L') | ||
+ | swap(Rc, Rc') | ||
+ | </code> | ||
+ | |||
+ | == Персистентная очередь на пяти стеках == | ||
+ | |||
+ | После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <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= \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle</tex>, содержащую пять версий персистентных стеков и три переменных. | ||
+ | |||
+ | Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex>\langle Sn, x\rangle</tex>, а операция <tex>S.push(x)</tex> возвращает <tex>Sn</tex>. | ||
+ | |||
+ | Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть <tex>Q.pop</tex> возвращает <tex>\langle Qn, x\rangle</tex>, а <tex>Q.push(x)</tex> возвращает <tex>Qn</tex>. | ||
Следующий псевдокод выполняет требуемые операции: | Следующий псевдокод выполняет требуемые операции: | ||
=== empty === | === empty === | ||
<code> | <code> | ||
− | empty() | + | '''boolean''' empty(): |
'''return''' !recopy '''and''' R.size == 0 | '''return''' !recopy '''and''' R.size == 0 | ||
</code> | </code> | ||
=== push === | === push === | ||
<code> | <code> | ||
− | push(x) | + | '''function''' push(x : '''T'''): |
− | '''if''' !recopy | + | '''if''' !recopy |
− | Ln = L.push(x) | + | '''stack<T>''' Ln = L.push(x) |
− | Q' = <Ln, L', R, R', | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <Ln, L', R, R', S, recopy, toCopy, copied> |
'''return''' Q'.checkRecopy() | '''return''' Q'.checkRecopy() | ||
− | '''else''' | + | '''else''' |
− | Ln' = L'.push(x) | + | '''stack<T>''' Ln' = L'.push(x) |
− | Q' = <L, Ln', R, R', | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, Ln', R, R', S, recopy, toCopy, copied> |
'''return''' Q'.checkNormal() | '''return''' Q'.checkNormal() | ||
</code> | </code> | ||
=== pop === | === pop === | ||
<code> | <code> | ||
− | pop() | + | <'''stack<T>''', '''T'''> pop(): |
− | '''if''' !recopy | + | '''if''' !recopy |
<Rn, x> = R.pop() | <Rn, x> = R.pop() | ||
− | Q' = <L, L', Rn, R', | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', Rn, R', S, recopy, toCopy, copied> |
'''return''' <Q'.checkRecopy(), x> | '''return''' <Q'.checkRecopy(), x> | ||
− | '''else''' | + | '''else''' |
<Rn', x> = R'.pop() | <Rn', x> = R'.pop() | ||
− | Q' = <L, L', | + | '''int''' curCopy = toCopy |
+ | Rn = R | ||
+ | '''if''' toCopy > 0 | ||
+ | curCopy = curCopy - 1 | ||
+ | '''else''' | ||
+ | <Rn, x> = Rn.pop() | ||
+ | Q' = <L, L', Rn, Rn', S, recopy, curCopy, copied> | ||
'''return''' <Q'.checkNormal(), x> | '''return''' <Q'.checkNormal(), x> | ||
</code> | </code> | ||
=== checkRecopy === | === checkRecopy === | ||
<code> | <code> | ||
− | checkRecopy() | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkRecopy(): |
− | '''if''' L.size > R.size | + | '''if''' L.size > R.size |
− | Q' = <L, L', R, R', | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', R, R', S, true, R.size, false> |
'''return''' Q'.checkNormal() | '''return''' Q'.checkNormal() | ||
− | '''else''' | + | '''else''' |
− | '''return''' <L, L', R, R', | + | '''return''' <L, L', R, R', S, false, toCopy, copied> |
</code> | </code> | ||
=== checkNormal === | === checkNormal === | ||
<code> | <code> | ||
− | checkNormal() | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkNormal(): |
Q' = Q.additionalOperations() | Q' = Q.additionalOperations() | ||
− | // Если мы не все перекопировали, то у нас не пуст стек | + | <span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span> |
− | return <Q'.L, Q'.L', Q'.R, Q'.R', Q'. | + | return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.S, Q'.S.size <tex> \ne </tex> 0, Q'.toCopy, Q'.copied> |
</code> | </code> | ||
=== additionalOperations === | === additionalOperations === | ||
<code> | <code> | ||
− | additionalOperations() | + | <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> additionalOperations(): |
− | // Нам достаточно 3 операций на вызов | + | <span style="color:#008000">// Нам достаточно 3 операций на вызов</span> |
− | toDo = 3 | + | '''int''' toDo = 3 |
− | // Пытаемся перекопировать R в | + | <span style="color:#008000">// Пытаемся перекопировать R в S</span> |
− | Rn = R | + | '''stack<T>''' Rn = R |
− | + | '''stack<T>''' Sn = S | |
− | '''while''' toDo > 0 '''and''' Rn.size > 0 | + | '''boolean''' curCopied = copied |
+ | '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0 | ||
<Rn, x> = Rn.pop() | <Rn, x> = Rn.pop() | ||
− | + | Sn = Sn.push(x) | |
toDo = toDo - 1 | toDo = toDo - 1 | ||
Ln = L | Ln = L | ||
− | // Пытаемся перекопировать L в R | + | <span style="color:#008000">// Пытаемся перекопировать L в R</span> |
− | '''while''' toDo > 0 '''and''' Ln.size > 0 | + | '''while''' toDo > 0 '''and''' Ln.size > 0 |
+ | curCopied = true | ||
<Ln, x> = Ln.pop() | <Ln, x> = Ln.pop() | ||
Rn = Rn.push(x) | Rn = Rn.push(x) | ||
toDo = toDo - 1 | toDo = toDo - 1 | ||
curCopy = toCopy | curCopy = toCopy | ||
− | // Пытаемся перекопировать | + | <span style="color:#008000">// Пытаемся перекопировать S в R с учетом toCopy</span> |
− | '''while''' toDo > 0 '''and''' | + | '''while''' toDo > 0 '''and''' Sn.size > 0 |
− | < | + | <Sn, x> = Sn.pop() |
− | '''if''' curCopy > 0 | + | '''if''' curCopy > 0 |
Rn = Rn.push(x) | Rn = Rn.push(x) | ||
curCopy = curCopy - 1 | curCopy = curCopy - 1 | ||
toDo = toDo - 1 | toDo = toDo - 1 | ||
− | Ln' = L' | + | '''stack<T>''' Ln' = L' |
− | // Если все скопировано, то меняем роли L1, L2 | + | <span style="color:#008000">// Если все скопировано, то меняем роли L1, L2</span> |
− | '''if''' | + | '''if''' S.size == 0 |
swap(Ln, Ln') | swap(Ln, Ln') | ||
− | '''return''' <Ln, Ln', Rn, R', | + | '''return''' <Ln, Ln', Rn, R', Sn, recopy, curCopy, curCopied> |
</code> | </code> | ||
+ | == Пример == | ||
+ | |||
+ | Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения. | ||
+ | |||
+ | [[Файл:PersistentQueue_state0.png|300px|nothumb|left|]] | ||
+ | |||
+ | <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>S</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>S</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>S</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>S</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>S</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] | ||
+ | * [http://habrahabr.ru/post/241231 Хабрахабр {{---}} Персистентная очередь] | ||
+ | * [http://codeforces.com/blog/entry/15685 Codeforces {{---}} Персистентная очередь и её друзья] | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Амортизационный анализ]] | [[Категория: Амортизационный анализ]] | ||
+ | [[Категория: Структуры данных]] |
Текущая версия на 19:15, 4 сентября 2022
Персистентная очередь (англ. persistent queue) — это очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.
Содержание
Основная идея
Для создания персистентной очереди очень удобно пользоваться ее реализацией на стеках, поскольку стеки легко сделать персистентными, причем в этом случае мы добьемся функциональной персистентности. Реализация на двух стеках не подходит для этого, так как в худшем случае требует времени, а значит и памяти на операцию в случае персистентности. Покажем сначала, как создать очередь в реальном времени с времени на операцию, а затем превратим ее в персистентную.
Реализация очереди на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим
времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с истинного времени на операцию.Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек
для операций и стек для операций . К моменту опустошения стека нам нужно успеть получить стек , содержащий текущие элементы стека в правильном для извлечения порядке. Перекопирование (recopy mode) начнется, когда появится опасность того, что мы не сможем за оставшиеся операций со стеком перекопировать стек в новый стек . Очевидно, это ситуация , пусть такое состояние отражает специальная переменная логического типа .Понятно, что во время перекопирования могут поступить операции
, а стек в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек , в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями и , на первый взгляд, все станет хорошо.Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек
может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции — ), когда при следующем перекопировании у нас не будет свободного стека для копирования туда элементов . Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека во вспомогательный стек , затем копировать элементы из стека в , а затем обратно копировать элементы из стека в . Легко показать, что приведенный алгоритм как раз получает на выходе в все элементы стеков в правильном порядке.Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека
, появляются следующие проблемы:- Что вернуть при операции ? Для этого заведем себе стек — копию стека , из которого мы и будем извлекать требуемые элементы.
- Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия для копирования всех элементов, которые мы копируем в , а по окончании перекопирования поменяем ролями стеки , как мы делали со стеками .
- Как учесть, что во время перекопирования часть элементов была извлечена из ? Для этого заведем специальную переменную , которая показывает, сколько корректных элементов находится в стеке , и уменьшается при каждом извлечении из или операции . К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если . Если во время операции у нас , это означает, что теперь в стеке находится весь правый кусок очереди, так что нам придется извлечь элемент из него.
Теперь может возникнуть проблема с непустым
после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.Пусть на начало перекопирования в стеке
содержится элементов, тогда в стеке находится элементов. Мы корректно можем обработать любое количество операций , а также операций . Заметим, что операция во время перекопирования всегда возвращает , так как мы не можем извлекать элементы из стека , который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать операцию.Посмотрим на дополнительные действия, которые нам предстоят:
- Переместить содержимое в , действий.
- Переместить содержимое в стеки , действий.
- Переместить первые элементов из в , остальные выкинуть, действий.
- Поменять ролями стеки , , действия.
Таким образом, получили
дополнительных действия за операций, или дополнительных действий на операцию в режиме перекопирования, что и требовалось.Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция
не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за следующих за активацией меняющих операций ( ) поступило операций , операций . Очевидно, что после перекопирования в новых стеках окажется: элементов в , элементов в , то есть до следующего перекопирования еще операции. С другой стороны, стек содержал всего элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.Итак, очередь
будет состоять из шести стеков , а также двух внутренних переменных , которые нужны для корректности перекопирования + дополнительная переменная , показывающая, перемещали ли мы элементы из стека в стек , чтобы не начать перемещать эти элементы в стек .Инвариант очереди (обычный режим):
- Стек содержит левую половину очереди, порядок при извлечении обратный.
- Стек содержит правую половину очереди, порядок при извлечении прямой.
- — копия
Тогда к следующему перекопированию (
) мы гарантированно будем иметь пустые стеки , которые нам понадобятся.Инвариант очереди (режим перекопирования):
- Если
- При первые элементов — корректны, то есть действительно содержатся в очереди.
- При стек содержит весь правый кусок очереди в правильном порядке.
, то:
Очередь будет работать в двух режимах:
- Обычный режим, кладем в , извлекаем из и из для поддержания порядка, операция .
- Режим перекопирования, кладем в , извлекаем из , возможно из , , совершаем дополнительные действия.
Также после операции в обычном режиме следует проверка на активацию перекопирования (
), если это так, , совершается первый набор дополнительных действий.После операции в режиме перекопирования следует проверка на завершение перекопирования (
), а при завершении меняются ролями стеки , .Следующий псевдокод выполняет требуемые операции:
empty
boolean empty(): return !recopy and R.size == 0
push
function push(x : T): if !recopy L.push(x) if Rc'.size > 0 Rc'.pop() checkRecopy() else L'.push(x) checkNormal()
pop
T pop(): if !recopy T tmp = R.pop() Rc.pop() if Rc'.size > 0 Rc'.pop() checkRecopy() return tmp else T tmp = Rc.pop() if toCopy > 0 toCopy = toCopy - 1 else R.pop() Rc'.pop() checkNormal() return tmp
checkRecopy
function checkRecopy(): recopy = L.size > R.size if recopy toCopy = R.size copied = false checkNormal()
checkNormal
function checkNormal(): additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек S recopy = S.size 0
additionalOperations
function additionalOperations(): // Нам достаточно 3 операций на вызов int toDo = 3 // Пытаемся перекопировать R в S while not copied and toDo > 0 and R.size > 0 S.push(R.pop()) toDo = toDo - 1 // Пытаемся перекопировать L в R и Rc' while toDo > 0 and L.size > 0 copied = true T x = L.pop() R.push(x) Rc'.push(x) toDo = toDo - 1 // Пытаемся перекопировать S в R и Rc' с учетом toCopy while toDo > 0 and S.size > 0 T x = S.pop() if toCopy > 0 R.push(x) Rc'.push(x) toCopy = toCopy - 1 toDo = toDo - 1 // Если все скопировано, то меняем роли L, L' и Rc, Rc' if S.size == 0 swap(L, L') swap(Rc, Rc')
Персистентная очередь на пяти стеках
После того, как мы получили очередь в реальном времени с обычными стеками, ее можно легко превратить в персистентную, сделав все стеки персистентными, но на самом деле персистентность позволяет не создавать явной копии стека , так что достаточно всего пяти стеков.
Вместо стеков
персистентная очередь хранит один стек , в который при активации перекопирования записывается последняя версия стека , в дальнейшем все операции обращаются именно к ней. Все замечания о остаются в силе.Также нам нет необходимости опустошать стек
к моменту перекопирования, так как скопировать туда новую версию мы можем за , а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.В качестве версии очереди мы будем использовать запись
, содержащую пять версий персистентных стеков и три переменных.Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция
возвращает , а операция возвращает .Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть
возвращает , а возвращает .Следующий псевдокод выполняет требуемые операции:
empty
boolean empty(): return !recopy and R.size == 0
push
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', S, 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', S, recopy, toCopy, copied> return Q'.checkNormal()
pop
<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', S, recopy, toCopy, copied> return <Q'.checkRecopy(), x> else <Rn', x> = R'.pop() int curCopy = toCopy Rn = R if toCopy > 0 curCopy = curCopy - 1 else <Rn, x> = Rn.pop() Q' = <L, L', Rn, Rn', S, recopy, curCopy, copied> return <Q'.checkNormal(), x>
checkRecopy
<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', S, true, R.size, false> return Q'.checkNormal() else return <L, L', R, R', S, false, toCopy, copied>
checkNormal
<stack<T>, stack<T>, stack<T>, stack<T>, stack<T>, boolean, int, boolean> checkNormal(): Q' = Q.additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек S return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.S, Q'.S.size 0, Q'.toCopy, Q'.copied>
additionalOperations
<stack<T>, stack<T>, stack<T>, stack<T>, stack<T>, boolean, int, boolean> additionalOperations(): // Нам достаточно 3 операций на вызов int toDo = 3 // Пытаемся перекопировать R в S stack<T> Rn = R stack<T> Sn = S boolean curCopied = copied while not curCopied and toDo > 0 and Rn.size > 0 <Rn, x> = Rn.pop() Sn = Sn.push(x) toDo = toDo - 1 Ln = L // Пытаемся перекопировать L в R while toDo > 0 and Ln.size > 0 curCopied = true <Ln, x> = Ln.pop() Rn = Rn.push(x) toDo = toDo - 1 curCopy = toCopy // Пытаемся перекопировать S в R с учетом toCopy while toDo > 0 and Sn.size > 0 <Sn, x> = Sn.pop() if curCopy > 0 Rn = Rn.push(x) curCopy = curCopy - 1 toDo = toDo - 1 stack<T> Ln' = L' // Если все скопировано, то меняем роли L1, L2 if S.size == 0 swap(Ln, Ln') return <Ln, Ln', Rn, R', Sn, recopy, curCopy, curCopied>
Пример
Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины — текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека
указывает на ту версию стека , которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.
Сделаем операцию
, изначально режим обычный, так что элемент пойдет в стек . Эта операция активирует режим перекопирования, в результате которого содержимое перекопируется в стек , после чего перекопирование завершится, стеки поменяются местами.
Сделаем операцию
, у нас обычный режим, поэтому элемент пойдет в стек , перекопирование не активируется.
Сделаем операцию
, у нас обычный режим, поэтому элемент пойдет в стек , активируется перекопирование, , за три операции мы успеваем перекопировать элемент стека в стек , а также перекопировать два элемента стека в стек .
Сделаем операцию
, мы в режиме перекопирования, поэтому элемент пойдет в стек , далее мы успеваем перекопировать обратно элемент из стека в стек , перекопирование завершается, стеки меняются местами.
Сделаем операцию
, у нас обычный режим, поэтому элемент пойдет в стек , перекопирование не активируется.
Сделаем операцию
, у нас обычный режим, поэтому элемент пойдет в стек , перекопирование не активируется.
Сделаем операцию
, у нас обычный режим, поэтому элемент пойдет в стек , перекопирование активируется, , , за три операции мы успеваем перекопировать содержимое стека в стек .
Сделаем операцию
, мы находимся в режиме перекопирования, так что элемент извлекается из , . За три операции мы успеваем перекопировать три элемента стека в стек .
Сделаем операцию
, мы находимся в режиме перекопирования, так что элемент извлекается из , . За три операции мы успеваем перекопировать один элемент стека в стек , а также извлечь два элемента стека , с учетом только один элемент попадет в стек , .
Сделаем операцию
, мы находимся в режиме перекопирования, так что элемент извлекается из , но , так что нам приходится извлечь еше один элемент из стека . Мы извлекаем один элемент из стека , перекопирование заканчивается, стеки меняются местами.