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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
Режим перекопирования активируется, когда в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. Пусть в стеке <tex>R</tex> в этот момент находилось <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находилось <tex>n+1</tex> элементов. Заметим, что мы можем корректно обработать только <tex>n</tex> запросов <tex>pop</tex>, операции <tex>push</tex> и <tex>empty</tex> мы обрабатываем корректно всегда, следовательно мы должны закончить перекопирование за <tex>n+1</tex> операцию, включая активирующую.
 
Режим перекопирования активируется, когда в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. Пусть в стеке <tex>R</tex> в этот момент находилось <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находилось <tex>n+1</tex> элементов. Заметим, что мы можем корректно обработать только <tex>n</tex> запросов <tex>pop</tex>, операции <tex>push</tex> и <tex>empty</tex> мы обрабатываем корректно всегда, следовательно мы должны закончить перекопирование за <tex>n+1</tex> операцию, включая активирующую.
  
Для заверешения перекопирования нужно:
+
Для завершения перекопирования нужно:
 
# Переместить все содержимое стека <tex>R</tex> в <tex>T</tex>, <tex>n</tex> операций.
 
# Переместить все содержимое стека <tex>R</tex> в <tex>T</tex>, <tex>n</tex> операций.
 
# Переместить все содержимое стека <tex>L</tex> в <tex>R</tex>, <tex>n + 1</tex> операция.  
 
# Переместить все содержимое стека <tex>L</tex> в <tex>R</tex>, <tex>n + 1</tex> операция.  
Строка 22: Строка 22:
  
 
Итого, мы должны сделать <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, то есть выполняя <tex>O(1)=3</tex> дополнительных действия на операцию, мы сможем завершить перекопирование и вернуться в обычный режим до исчерпания стека <tex>R'</tex>, получив <tex>O(1)</tex> реального времени и <tex>O(1)</tex> памяти на персистентность на операцию.  
 
Итого, мы должны сделать <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, то есть выполняя <tex>O(1)=3</tex> дополнительных действия на операцию, мы сможем завершить перекопирование и вернуться в обычный режим до исчерпания стека <tex>R'</tex>, получив <tex>O(1)</tex> реального времени и <tex>O(1)</tex> памяти на персистентность на операцию.  
 +
 +
Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</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>R</tex> на <tex>n+1</tex> больше элементов, чем в стеке <tex>L</tex>, а это значит, что до следующего режима перекопирования <tex>n + 2</tex> операции, и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>Rc</tex>, если он не пустой.
 +
 +
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
 +
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]

Версия 11:17, 7 июня 2013

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

Эффективная реализация

По сравнению с реализацией на шести стеках, теперь у нас все стеки персистентные, а значит у нас нет необходимости хранить отдельно копию стека [math]R[/math], так как все его версии теперь доступны по его персистентности. Это позволяет нам заменить два стека [math]Rc_1, Rc_2[/math] на один стек [math]R_2[/math], в который мы и будем записывать перекопированный кусок.

Персистентная очередь будет состоять из пяти персистентных стеков: [math]L_1, L_2, R_1, R_2, T[/math], причем стеки [math]L_1, L_2[/math] используются для операций [math]push[/math], стеки [math]R_1, R_2[/math] используются для операций [math]pop[/math], а стек [math]T[/math] используется для временного хранения содержимого стека [math]R[/math].

В каждый момент времени определено, какой стек [math]L[/math] из стеков [math]L_1, L_2[/math] сейчас используется для операций [math]push[/math], какой стек [math]R[/math] из стеков [math]R_1, R_2[/math] сейчас используется для операций [math]pop[/math], а также находится ли очередь в режиме перекопирования (recopy mode).

В режиме перекопирования операции [math]push[/math] перенаправляются в парный стек [math]L'[/math]; операции [math]pop[/math] выполняются над последней персистентной версией [math]R[/math], тогда операция [math]empty[/math] всегда возвращает [math]false[/math], так как стек [math]L[/math] содержит [math]n+1\gt 0[/math] элементов, а в режиме перекопирования мы не можем извлечь их операцией [math]pop[/math].

Для хранения последней персистентной версии [math]R[/math] мы используем второй имеющийся стек [math]R'[/math], а также переменную [math]toCopy[/math] — количество элементов, оставшихся в [math]R'[/math], оно уменьшается на [math]1[/math] с каждой следующей операцией [math]pop[/math].

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

Для завершения перекопирования нужно:

  1. Переместить все содержимое стека [math]R[/math] в [math]T[/math], [math]n[/math] операций.
  2. Переместить все содержимое стека [math]L[/math] в [math]R[/math], [math]n + 1[/math] операция.
  3. Переместить первые [math]toCopy[/math] элементов стека [math]T[/math] в [math]R[/math], а оставшиеся элементы выкинуть, [math]n[/math] операций.
  4. Обменять местами стеки [math]L[/math] и [math]L'[/math], [math]2[/math] операции.

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

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

Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке [math]L[/math] находится не больше элементов, чем в [math]R[/math], так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека [math]R[/math].