Персистентная очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 6 участников)
Строка 1: Строка 1:
'''Персистентная очередь''' {{---}} это [[Очередь|очередь]], реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменяться.
+
'''Персистентная очередь''' (англ. ''persistent queue'') {{---}} это [[Очередь|очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.
  
= Основная идея =
+
== Основная идея ==
  
Для создания персистентной очереди очень удобно пользоваться ее реализацией на стеках, поскольку стеки легко сделать персистентными. Реализация на двух стеках не подходит для этого, так как в худшем сучае требует <tex>O(n)</tex> времени, а значит и <tex>O(n)</tex> памяти в случае персистентности на операцию. Покажем сначала как создать очередь в реальном времени с <tex>O(1)</tex> времени на операцию, а затем превратим ее в персистентную.
+
Для создания персистентной очереди очень удобно пользоваться ее реализацией на [[Стек|стеках]], поскольку стеки легко сделать [[Персистентный стек|персистентными]], причем в этом случае мы добьемся функциональной персистентности. [[Очередь#Реализация на двух стеках|Реализация на двух стеках]] не подходит для этого, так как в худшем случае требует <tex>O(n)</tex> времени, а значит и <tex>O(n)</tex> памяти на операцию в случае персистентности. Покажем сначала, как создать очередь в реальном времени с <tex>O(1)</tex> времени на операцию, а затем превратим ее в персистентную.
  
 
== Реализация очереди на шести стеках ==
 
== Реализация очереди на шести стеках ==
Строка 9: Строка 9:
 
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
 
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
  
Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> в правильном для извлечения порядке. Перекопирование (''recopy mode'') начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>pop</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>recopy</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>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо.
+
Понятно, что во время перекопирования могут поступить операции <tex>\mathtt{push}</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, на первый взгляд, все станет хорошо.
  
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>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{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>R</tex>, появляются следующие проблемы:
# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</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>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex>, и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>. Если во время операции <tex>pop</tex> у нас <tex>toCopy = 0</tex>, это означает, что теперь в стеке <tex>R</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>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
  
Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>. Заметим, что операция <tex>empty</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</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>R</tex> в <tex>S</tex>, <tex>n</tex> действий.
 
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
 
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
# Переместить первые <tex>toCopy</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</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>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>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3 = O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось.
  
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>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>\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>recopy, toCopy</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>copied</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>T</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>.  
  
 
Инвариант очереди (обычный режим):
 
Инвариант очереди (обычный режим):
Строка 43: Строка 43:
 
# <tex>Rc</tex> {{---}} копия <tex>R</tex>
 
# <tex>Rc</tex> {{---}} копия <tex>R</tex>
 
# <tex>Rc'.size < R.size - L.size</tex>
 
# <tex>Rc'.size < R.size - L.size</tex>
# <tex>L'.size = 0, T.size = 0</tex>
+
# <tex>L'.size = 0, S.size = 0</tex>
  
Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',T,Rc'</tex>, которые нам понадобятся.
+
Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',S,Rc'</tex>, которые нам понадобятся.
  
 
Инвариант очереди (режим перекопирования):
 
Инвариант очереди (режим перекопирования):
# <tex>Rc.size = toCopy</tex>
+
# <tex>Rc.size = \mathtt{toCopy}</tex>
 
# Если <tex>L.size = 0</tex>, то:
 
# Если <tex>L.size = 0</tex>, то:
## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.
+
## При <tex>\mathtt{toCopy} > 0</tex> первые <tex>\mathtt{toCopy}</tex> элементов <tex>S</tex> {{---}} корректны, то есть действительно содержатся в очереди.
## При <tex>toCopy \leqslant 0</tex> стек <tex>R</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>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</tex>.
# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>empty=false</tex>, совершаем дополнительные действия.
+
# Режим перекопирования, кладем в <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, copied = false</tex>, совершается первый набор дополнительных действий.
+
Также после операции в обычном режиме следует проверка на активацию перекопирования (<tex>\mathtt{recopy} = (L.size > R.size)</tex>), если это так, <tex>\mathtt{toCopy} = R.size, \mathtt{recopy} = true, \mathtt{copied} = false</tex>, совершается первый набор дополнительных действий.
  
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
+
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>\mathtt{recopy} = (S.size == 0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</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
 
       L.push(x)
 
       L.push(x)
       '''if''' Rc'.size > 0:
+
       '''if''' Rc'.size > 0
 
           Rc'.pop()
 
           Rc'.pop()
 
       checkRecopy()
 
       checkRecopy()
     '''else''':
+
     '''else'''
 
       L'.push(x)
 
       L'.push(x)
 
       checkNormal()
 
       checkNormal()
Строка 81: Строка 81:
 
=== pop ===
 
=== pop ===
 
<code>
 
<code>
  pop()
+
  '''T''' pop():
     '''if''' !recopy:
+
     '''if''' !recopy
       tmp = R.pop()
+
       '''T''' tmp = R.pop()
 
       Rc.pop()
 
       Rc.pop()
       '''if''' Rc'.size > 0:
+
       '''if''' Rc'.size > 0
 
           Rc'.pop()
 
           Rc'.pop()
 
       checkRecopy()
 
       checkRecopy()
 
       '''return''' tmp
 
       '''return''' tmp
     '''else''':
+
     '''else'''
       tmp = Rc.pop()
+
       '''T''' tmp = Rc.pop()
       '''if''' toCopy > 0:
+
       '''if''' toCopy > 0
 
           toCopy = toCopy - 1
 
           toCopy = toCopy - 1
       '''else''':
+
       '''else'''
 
           R.pop()
 
           R.pop()
 
           Rc'.pop()
 
           Rc'.pop()
Строка 102: Строка 102:
 
=== checkRecopy ===
 
=== checkRecopy ===
 
<code>
 
<code>
  checkRecopy()     
+
  '''function''' checkRecopy():    
 
     recopy = L.size > R.size
 
     recopy = L.size > R.size
     '''if''' recopy:
+
     '''if''' recopy
 
       toCopy = R.size
 
       toCopy = R.size
 
       copied = false
 
       copied = false
Строка 112: Строка 112:
 
=== checkNormal ===
 
=== checkNormal ===
 
<code>
 
<code>
  checkNormal()
+
  '''function''' checkNormal():
 
     additionalOperations()
 
     additionalOperations()
    // Если мы не все перекопировали, то у нас не пуст стек T
+
    <span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span>
     recopy = T.size <tex> \ne </tex> 0
+
     recopy = S.size <tex> \neq </tex> 0
 
</code>
 
</code>
 +
 
=== additionalOperations ===
 
=== additionalOperations ===
 
<code>
 
<code>
  additionalOperations()
+
  '''function''' additionalOperations():
     // Нам достаточно 3 операций на вызов
+
     <span style="color:#008000">// Нам достаточно 3 операций на вызов</span>
     toDo = 3
+
     '''int''' toDo = 3
     // Пытаемся перекопировать R в T
+
     <span style="color:#008000">// Пытаемся перекопировать R в S</span>
     '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0:
+
     '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0
       T.push(R.pop())
+
       S.push(R.pop())
 
       toDo = toDo - 1
 
       toDo = toDo - 1
     // Пытаемся перекопировать L в R и Rc'
+
     <span style="color:#008000">// Пытаемся перекопировать L в R и Rc'</span>
     '''while''' toDo > 0 '''and''' L.size > 0:
+
     '''while''' toDo > 0 '''and''' L.size > 0
 
       copied = true
 
       copied = true
       x = L.pop()
+
       '''T''' x = L.pop()
 
       R.push(x)
 
       R.push(x)
 
       Rc'.push(x)
 
       Rc'.push(x)
 
       toDo = toDo - 1
 
       toDo = toDo - 1
     // Пытаемся перекопировать T в R и Rc' с учетом toCopy
+
     <span style="color:#008000">// Пытаемся перекопировать S в R и Rc' с учетом toCopy</span>
     '''while''' toDo > 0 '''and''' T.size > 0:
+
     '''while''' toDo > 0 '''and''' S.size > 0
       x = T.pop()
+
       '''T''' x = S.pop()
       '''if''' toCopy > 0:
+
       '''if''' toCopy > 0
 
           R.push(x)
 
           R.push(x)
 
           Rc'.push(x)
 
           Rc'.push(x)
 
           toCopy = toCopy - 1
 
           toCopy = toCopy - 1
 
       toDo = toDo - 1
 
       toDo = toDo - 1
     // Если все скопировано, то меняем роли L, L' и Rc, Rc'
+
     <span style="color:#008000">// Если все скопировано, то меняем роли L, L' и Rc, Rc'</span>
     '''if''' T.size == 0:
+
     '''if''' S.size == 0
 
       swap(L, L')
 
       swap(L, L')
 
       swap(Rc, Rc')
 
       swap(Rc, Rc')
Строка 149: Строка 150:
 
== Персистентная очередь на пяти стеках ==
 
== Персистентная очередь на пяти стеках ==
  
После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными [[Стек|стеками]], ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека, так что достаточно всего пяти стеков.
+
После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <tex>O(1) = 6</tex> обычными стеками, ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека <tex>R</tex>, так что достаточно всего пяти стеков.
 
 
Будем отталкиваться от реализации на [[Очередь#Реализация на двух стеках|двух стеках]]. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex>, стек <tex>R</tex> для операций <tex>pop</tex>.
 
К моменту опустошения стека <tex>R</tex> нам нужно получить стек <tex>R'</tex>, содержащий все элементы стека <tex>L</tex> в правильном для извлечения порядке. Этого можно добиться, если переместить все элементы стека <tex>L</tex>, в стек <tex>R'</tex>, назовем такой процесс перекопированием, а очередь будет в это время находится в режиме перекопирования (''recopy mode''). Режим перекопирования активируется, когда во время очередной операции мы уже можем не успеть переместить нужные элементы, а именно <tex>L.size>R.size</tex>. Состояние очереди будет фиксировать логическая переменная <tex>recopy</tex>.
 
 
 
Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция <tex>empty=false</tex>, так как мы не можем извлекать элементы, находившиеся в не пустом стеке <tex>L</tex>, значит очередь всегда не пуста. Договоримся также, что операция <tex>empty</tex> не меняет внутреннюю структуру очереди и не создает новой версии очереди.
 
 
 
Поскольку стек <tex>L</tex> во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементы, пришедшие с <tex>push</tex>. Для таких элементов заведем специальный стек <tex>L'</tex> в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с <tex>L</tex>.
 
 
 
Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек <tex>R</tex> опустошится за время перекопирования, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были <tex>push</tex>). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем переместим все элементы стека <tex>L</tex> в стек <tex>R</tex>, затем обратно переместим все элементы <tex>T</tex> в стек <tex>R</tex>. Легко показать, что такая последовательность действий приведет к правильному для извлечения порядку элементов в <tex>R</tex>.
 
 
 
Теперь разберемся с операциями <tex>pop</tex>. Теперь у нас теряет свою структуру стек <tex>R</tex>, значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком <tex>R</tex>, но теперь мы можем просто записать в <tex>R'</tex> последнюю версию стека <tex>R</tex> и дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, будем использовать переменную <tex>toCopy=R'.size</tex>, будем уменьшать ее на <tex>1</tex> при каждом извлечении из <tex>T</tex> и операциях <tex>pop</tex>. Так как извлеченные элементы будут нарастать со дна стека <tex>T</tex>, мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>, а при <tex>toCopy \leqslant 0</tex> в стеке <tex>R</tex> будет содержаться весь правый кусок очереди в правильном порядке, так что придется извлечь элемент и из него тоже.
 
 
 
Теперь проанализируем наш алгоритм. Пусть в стеке <tex>R</tex> на начало перекопирования содержатся <tex>n</tex> элементов, тогда в стеке <tex>R</tex> находится <tex>n+1</tex> элемент. Мы можем корректно обработать все операции <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>, операции <tex>empty</tex> мы не учитываем. Тогда мы должны завершить перекопирование не больше, чем за <tex>n+1</tex> операцию.
 
 
Всего в режиме перекопирования нужно:
 
# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex> времени, <tex>n</tex> памяти.
 
# Переместить содержимое <tex>L</tex> в <tex>R</tex>, <tex>n+1</tex> времени, <tex>n+1</tex> памяти.
 
# Переместить первые <tex>toCopy</tex> элементов из стека <tex>T</tex> в стек <tex>R</tex>, остальные выкинуть, <tex>n</tex> времени, <tex>n</tex> памяти.
 
# Поменять ролями стеки <tex>L, L'</tex>, <tex>1</tex> времени.
 
 
 
Таким образом, мы получили <tex>3 \cdot n + 2</tex> времени и <tex>3 \cdot n + 1</tex> памяти на <tex>n + 1</tex> операцию, то есть <tex>3=O(1)</tex> времени и памяти на операцию. Совершая три дополнительных действия вместе с каждой операцией <tex>push, pop</tex> в режиме перекопирования мы гарантируем, что перекопирование завершится до опустошения стека <tex>R'</tex>.
 
 
 
Теперь проверим корректность условия активации. Пусть среди <tex>n</tex> следующих за активацией операций <tex>push, pop</tex> присуствует <tex>x</tex> операций <tex>pop</tex> и <tex>n - x</tex> операций <tex>push</tex>. Тогда, очевидно, в стеке <tex>R</tex> окажется <tex>2 \cdot n + 1 - x</tex> элементов, а в стеке <tex>L</tex> станет <tex>n - x</tex> элементов, то есть на <tex>n + 1</tex> элемент меньше, чем в стеке <tex>R</tex>, а значит до следующего перекопирования <tex>n+2</tex> операции.
 
 
 
Заметим, что теперь если очередь находится в обычном режиме, <tex>L.size \leqslant R.size</tex>, значит <tex>empty=(R.size==0)</tex>.
 
 
 
Итак, очередь <tex>Q</tex> будет состоять из пяти стеков <tex>L,L',R,R',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования, + дополнительной переменной <tex>copied</tex>, начинали ли мы уже перемещать элементы из стека <tex>L</tex> в <tex>R</tex>, чтобы не начать их перекладывать в <tex>T</tex>.
 
 
 
Инвариант очереди (обычный режим):
 
# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.
 
# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.
 
# <tex>L.size \leqslant R.size</tex>
 
# <tex>R.size = 0 \equiv Q.size = 0</tex>
 
# <tex>L'.size = 0, T.size = 0</tex>
 
  
Инвариант очереди (режим перекопирования):
+
Вместо стеков <tex>Rc, Rc'</tex> персистентная очередь хранит один стек <tex>R'</tex>, в который при активации перекопирования записывается последняя версия стека <tex>R</tex>, в дальнейшем все операции <tex>\mathtt{pop}</tex> обращаются именно к ней. Все замечания о <tex>\mathtt{toCopy}</tex> остаются в силе.
# Если <tex>L.size = 0</tex>, то:
 
## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.
 
## При <tex>toCopy \leqslant </tex> стек <tex>R</tex> корректный, то есть содержит все элементы правого куска очереди в правильном порядке.
 
  
Очередь будет работать в двух режимах:
+
Также нам нет необходимости опустошать стек <tex>R'</tex> к моменту перекопирования, так как скопировать туда новую версию <tex>R</tex> мы можем за <tex>O(1)</tex>, а  освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.  
# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex>, операция <tex>empty = (R.size = 0)</tex>.
 
# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>R'</tex>, <tex>empty=false</tex>, совершаем дополнительные действия.
 
  
Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, copied = false, R'=R</tex>, совершается первый набор дополнительных действий.
+
В качестве версии очереди мы будем использовать запись <tex>Q= \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle</tex>, содержащую пять версий персистентных стеков и три переменных.
  
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>L, L'</tex>.
+
Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex>\langle Sn, x\rangle</tex>, а операция <tex>S.push(x)</tex> возвращает <tex>Sn</tex>.
  
В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy, copied></tex>, содержащую пять версий стеков и три переменных.
+
Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть <tex>Q.pop</tex> возвращает <tex>\langle Qn, x\rangle</tex>, а <tex>Q.push(x)</tex> возвращает <tex>Qn</tex>.
Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><Sn, x></tex>, а операция <tex>S.push</tex> возвращает <tex><Sn></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', T, recopy, toCopy, copied>
+
       <'''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', T, recopy, toCopy, copied>  
+
       <'''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', T, recopy, toCopy, copied>
+
       <'''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()
       curCopy = toCopy
+
       '''int''' curCopy = toCopy
 
       Rn = R
 
       Rn = R
       '''if''' toCopy > 0:
+
       '''if''' toCopy > 0
 
           curCopy = curCopy - 1
 
           curCopy = curCopy - 1
       '''else''':
+
       '''else'''
 
           <Rn, x> = Rn.pop()  
 
           <Rn, x> = Rn.pop()  
       Q' = <L, L', Rn, Rn', T, recopy, curCopy, copied>
+
       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', T, true, R.size, false>
+
       <'''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', T, false, toCopy, copied>
+
       '''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()
     // Если мы не все перекопировали, то у нас не пуст стек T
+
     <span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span>
     return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.T, Q'.T.size <tex> \ne </tex> 0, Q'.toCopy, Q'.copied>
+
     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 в T
+
     <span style="color:#008000">// Пытаемся перекопировать R в S</span>
     Rn = R
+
     '''stack<T>''' Rn = R
     Tn = T
+
     '''stack<T>''' Sn = S
     curCopied = copied
+
     '''boolean''' curCopied = copied
     '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0:
+
     '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0
 
       <Rn, x> = Rn.pop()
 
       <Rn, x> = Rn.pop()
       Tn = Tn.push(x)
+
       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
 
       curCopied = true
 
       <Ln, x> = Ln.pop()
 
       <Ln, x> = Ln.pop()
Строка 275: Строка 236:
 
       toDo = toDo - 1
 
       toDo = toDo - 1
 
     curCopy = toCopy
 
     curCopy = toCopy
     // Пытаемся перекопировать T в R с учетом toCopy
+
     <span style="color:#008000">// Пытаемся перекопировать S в R с учетом toCopy</span>
     '''while''' toDo > 0 '''and''' Tn.size > 0:
+
     '''while''' toDo > 0 '''and''' Sn.size > 0
       <Tn, x> = Tn.pop()
+
       <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''' T.size == 0:
+
     '''if''' S.size == 0
 
       swap(Ln, Ln')
 
       swap(Ln, Ln')
     '''return''' <Ln, Ln', Rn, R', Tn, recopy, curCopy, curCopied>       
+
     '''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) — это очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.

Основная идея

Для создания персистентной очереди очень удобно пользоваться ее реализацией на стеках, поскольку стеки легко сделать персистентными, причем в этом случае мы добьемся функциональной персистентности. Реализация на двух стеках не подходит для этого, так как в худшем случае требует [math]O(n)[/math] времени, а значит и [math]O(n)[/math] памяти на операцию в случае персистентности. Покажем сначала, как создать очередь в реальном времени с [math]O(1)[/math] времени на операцию, а затем превратим ее в персистентную.

Реализация очереди на шести стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек [math]L[/math] для операций [math]\mathtt{push}[/math] и стек [math]R[/math] для операций [math]\mathtt{pop}[/math]. К моменту опустошения стека [math]R[/math] нам нужно успеть получить стек [math]R'[/math], содержащий текущие элементы стека [math]L[/math] в правильном для извлечения порядке. Перекопирование (recopy mode) начнется, когда появится опасность того, что мы не сможем за оставшиеся [math]R.size[/math] операций [math]\mathtt{pop}[/math] со стеком [math]R[/math] перекопировать стек [math]L[/math] в новый стек [math]R'[/math]. Очевидно, это ситуация [math]L.size\gt R.size[/math], пусть такое состояние отражает специальная переменная логического типа [math]\mathtt{recopy}[/math].

Понятно, что во время перекопирования могут поступить операции [math]\mathtt{push}[/math], а стек [math]L[/math] в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек [math]L'[/math], в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями [math]L,L'[/math] и [math]R,R'[/math], на первый взгляд, все станет хорошо.

Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек [math]R[/math] может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции — [math]\mathtt{push}[/math]), когда при следующем перекопировании у нас не будет свободного стека для копирования туда элементов [math]L[/math]. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека [math]R[/math] во вспомогательный стек [math]S[/math], затем копировать элементы из стека [math]L[/math] в [math]R[/math], а затем обратно копировать элементы из стека [math]S[/math] в [math]R[/math]. Легко показать, что приведенный алгоритм как раз получает на выходе в [math]R[/math] все элементы стеков [math]L,R[/math] в правильном порядке.

Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека [math]R[/math], появляются следующие проблемы:

  1. Что вернуть при операции [math]\mathtt{pop}[/math]? Для этого заведем себе стек [math]Rc[/math] — копию стека [math]R[/math], из которого мы и будем извлекать требуемые элементы.
  2. Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия [math]Rc'[/math] для копирования всех элементов, которые мы копируем в [math]R[/math], а по окончании перекопирования поменяем ролями стеки [math]Rc, Rc'[/math], как мы делали со стеками [math]L, L'[/math].
  3. Как учесть, что во время перекопирования часть элементов была извлечена из [math]Rc[/math]? Для этого заведем специальную переменную [math]\mathtt{toCopy}[/math], которая показывает, сколько корректных элементов находится в стеке [math]S[/math], и уменьшается при каждом извлечении из [math]S[/math] или операции [math]\mathtt{pop}[/math]. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если [math]\mathtt{toCopy}\gt 0[/math]. Если во время операции [math]\mathtt{pop}[/math] у нас [math]\mathtt{toCopy} = 0[/math], это означает, что теперь в стеке [math]R[/math] находится весь правый кусок очереди, так что нам придется извлечь элемент из него.

Теперь может возникнуть проблема с непустым [math]Rc[/math] после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.

Пусть на начало перекопирования в стеке [math]R[/math] содержится [math]n[/math] элементов, тогда в стеке [math]L[/math] находится [math]n + 1[/math] элементов. Мы корректно можем обработать любое количество операций [math]\mathtt{push}[/math], а также [math]n[/math] операций [math]\mathtt{pop}[/math]. Заметим, что операция [math]\mathtt{empty}[/math] во время перекопирования всегда возвращает [math]false[/math], так как мы не можем извлекать элементы из стека [math]L[/math], который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать [math]n + 1[/math] операцию.

Посмотрим на дополнительные действия, которые нам предстоят:

  1. Переместить содержимое [math]R[/math] в [math]S[/math], [math]n[/math] действий.
  2. Переместить содержимое [math]L[/math] в стеки [math]R, Rc'[/math], [math]n + 1[/math] действий.
  3. Переместить первые [math]\mathtt{toCopy}[/math] элементов из [math]S[/math] в [math]R, Rc'[/math], остальные выкинуть, [math]n[/math] действий.
  4. Поменять ролями стеки [math]Rc, Rc'[/math], [math]L, L'[/math], [math]2[/math] действия.

Таким образом, получили [math]3 \cdot n + 3[/math] дополнительных действия за [math]n + 1[/math] операций, или [math]3 = O(1)[/math] дополнительных действий на операцию в режиме перекопирования, что и требовалось.

Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция [math]\mathtt{empty}[/math] не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за [math]n[/math] следующих за активацией меняющих операций ([math]\mathtt{push}, \mathtt{pop}[/math]) поступило [math]x[/math] операций [math]\mathtt{pop}[/math], [math]n - x[/math] операций [math]\mathtt{push}[/math]. Очевидно, что после перекопирования в новых стеках окажется: [math]n-x[/math] элементов в [math]L[/math], [math]2 \cdot n + 1 - x = (n - x) + (n + 1)[/math] элементов в [math]R[/math], то есть до следующего перекопирования еще [math]n + 2[/math] операции. С другой стороны, стек [math]Rc[/math] содержал всего [math]n[/math] элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.

Итак, очередь [math]Q[/math] будет состоять из шести стеков [math]L,L',R,Rc,Rc',S[/math], а также двух внутренних переменных [math]\mathtt{recopy}, \mathtt{toCopy}[/math], которые нужны для корректности перекопирования + дополнительная переменная [math]\mathtt{copied}[/math], показывающая, перемещали ли мы элементы из стека [math]L[/math] в стек [math]R[/math], чтобы не начать перемещать эти элементы в стек [math]S[/math].

Инвариант очереди (обычный режим):

  1. Стек [math]L[/math] содержит левую половину очереди, порядок при извлечении обратный.
  2. Стек [math]R[/math] содержит правую половину очереди, порядок при извлечении прямой.
  3. [math]L.size \leqslant R.size[/math]
  4. [math]R.size = 0 \equiv Q.size = 0[/math]
  5. [math]Rc[/math] — копия [math]R[/math]
  6. [math]Rc'.size \lt R.size - L.size[/math]
  7. [math]L'.size = 0, S.size = 0[/math]

Тогда к следующему перекопированию ([math]L.size=R.size+1[/math]) мы гарантированно будем иметь пустые стеки [math]L',S,Rc'[/math], которые нам понадобятся.

Инвариант очереди (режим перекопирования):

  1. [math]Rc.size = \mathtt{toCopy}[/math]
  2. Если [math]L.size = 0[/math], то:
    1. При [math]\mathtt{toCopy} \gt 0[/math] первые [math]\mathtt{toCopy}[/math] элементов [math]S[/math] — корректны, то есть действительно содержатся в очереди.
    2. При [math]\mathtt{toCopy} \leqslant 0[/math] стек [math]R[/math] содержит весь правый кусок очереди в правильном порядке.

Очередь будет работать в двух режимах:

  1. Обычный режим, кладем в [math]L[/math], извлекаем из [math]R[/math] и из [math]Rc, Rc'[/math] для поддержания порядка, операция [math]empty = (R.size = 0)[/math].
  2. Режим перекопирования, кладем в [math]L'[/math], извлекаем из [math]Rc[/math], возможно из [math]R[/math], [math]\mathtt{empty} = \mathtt{false}[/math], совершаем дополнительные действия.

Также после операции в обычном режиме следует проверка на активацию перекопирования ([math]\mathtt{recopy} = (L.size \gt R.size)[/math]), если это так, [math]\mathtt{toCopy} = R.size, \mathtt{recopy} = true, \mathtt{copied} = false[/math], совершается первый набор дополнительных действий.

После операции в режиме перекопирования следует проверка на завершение перекопирования ([math]\mathtt{recopy} = (S.size == 0)[/math]), а при завершении меняются ролями стеки [math]Rc, Rc'[/math], [math]L, L'[/math].

Следующий псевдокод выполняет требуемые операции:

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 [math] \neq [/math] 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')

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

После того, как мы получили очередь в реальном времени с [math]O(1) = 6[/math] обычными стеками, ее можно легко превратить в персистентную, сделав все стеки персистентными, но на самом деле персистентность позволяет не создавать явной копии стека [math]R[/math], так что достаточно всего пяти стеков.

Вместо стеков [math]Rc, Rc'[/math] персистентная очередь хранит один стек [math]R'[/math], в который при активации перекопирования записывается последняя версия стека [math]R[/math], в дальнейшем все операции [math]\mathtt{pop}[/math] обращаются именно к ней. Все замечания о [math]\mathtt{toCopy}[/math] остаются в силе.

Также нам нет необходимости опустошать стек [math]R'[/math] к моменту перекопирования, так как скопировать туда новую версию [math]R[/math] мы можем за [math]O(1)[/math], а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.

В качестве версии очереди мы будем использовать запись [math]Q= \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle[/math], содержащую пять версий персистентных стеков и три переменных.

Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция [math]S.pop[/math] возвращает [math]\langle Sn, x\rangle[/math], а операция [math]S.push(x)[/math] возвращает [math]Sn[/math].

Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть [math]Q.pop[/math] возвращает [math]\langle Qn, x\rangle[/math], а [math]Q.push(x)[/math] возвращает [math]Qn[/math].

Следующий псевдокод выполняет требуемые операции:

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 [math] \ne [/math] 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>      

Пример

Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины — текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека [math]R'[/math] указывает на ту версию стека [math]R[/math], которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.

PersistentQueue state0.png


Сделаем операцию [math] \mathtt{push(1)} [/math], изначально режим обычный, так что элемент пойдет в стек [math]L[/math]. Эта операция активирует режим перекопирования, в результате которого содержимое [math]L[/math] перекопируется в стек [math]R[/math], после чего перекопирование завершится, стеки [math]L, L'[/math] поменяются местами.

PersistentQueue state1.png


Сделаем операцию [math] \mathtt{push(2)} [/math], у нас обычный режим, поэтому элемент пойдет в стек [math]L[/math], перекопирование не активируется.

PersistentQueue state2.png


Сделаем операцию [math] \mathtt{push(3)} [/math], у нас обычный режим, поэтому элемент пойдет в стек [math]L[/math], активируется перекопирование, [math]R' = R[/math], за три операции мы успеваем перекопировать элемент стека [math]R[/math] в стек [math]S[/math], а также перекопировать два элемента стека [math]L[/math] в стек [math]R[/math].

PersistentQueue state3.png


Сделаем операцию [math] \mathtt{push(4)} [/math], мы в режиме перекопирования, поэтому элемент пойдет в стек [math]L'[/math], далее мы успеваем перекопировать обратно элемент из стека [math]S[/math] в стек [math]R[/math], перекопирование завершается, стеки [math]L, L'[/math] меняются местами.

PersistentQueue state4.png


Сделаем операцию [math] \mathtt{push(5)} [/math], у нас обычный режим, поэтому элемент пойдет в стек [math]L[/math], перекопирование не активируется.

PersistentQueue state5.png


Сделаем операцию [math] \mathtt{push(6)} [/math], у нас обычный режим, поэтому элемент пойдет в стек [math]L[/math], перекопирование не активируется.

PersistentQueue state6.png


Сделаем операцию [math] \mathtt{push(7)} [/math], у нас обычный режим, поэтому элемент пойдет в стек [math]L[/math], перекопирование активируется, [math]R' = R[/math], [math]\mathtt{toCopy} = 3[/math], за три операции мы успеваем перекопировать содержимое стека [math]R[/math] в стек [math]S[/math].

PersistentQueue state7.png


Сделаем операцию [math]\mathtt{pop}[/math], мы находимся в режиме перекопирования, так что элемент извлекается из [math]R'[/math], [math]\mathtt{toCopy} = 2[/math]. За три операции мы успеваем перекопировать три элемента стека [math]L[/math] в стек [math]R[/math].

PersistentQueue state8.png


Сделаем операцию [math]\mathtt{pop}[/math], мы находимся в режиме перекопирования, так что элемент извлекается из [math]R'[/math], [math]\mathtt{toCopy} = 1[/math]. За три операции мы успеваем перекопировать один элемент стека [math]L[/math] в стек [math]R[/math], а также извлечь два элемента стека [math]S[/math], с учетом [math]\mathtt{toCopy}[/math] только один элемент попадет в стек [math]R[/math], [math]\mathtt{toCopy} = 0[/math].

PersistentQueue State9.png


Сделаем операцию [math]\mathtt{pop}[/math], мы находимся в режиме перекопирования, так что элемент извлекается из [math]R'[/math], но [math]\mathtt{toCopy} = 0[/math], так что нам приходится извлечь еше один элемент из стека [math]R[/math]. Мы извлекаем один элемент из стека [math]S[/math], перекопирование заканчивается, стеки [math]L, L'[/math] меняются местами.

PersistentQueue state10.png


См. также

Источники информации