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

Персистентная очередь (англ. 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], которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.

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

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

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

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

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

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

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

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

Сделаем операцию [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].

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

См. также

• Персистентный стек
• Персистентный дек
• Персистентная приоритетная очередь

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

• Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980
• Хабрахабр — Персистентная очередь
• Codeforces — Персистентная очередь и её друзья