120
правок
Изменения
Нет описания правки
== Эффективная реализация ==
По сравнению с реализацией на шести стеках, теперь у нас все стеки персистентные, а значит у нас нет необходимости хранить отдельно копию стека <tex>R</tex>, так как все его версии теперь доступны по его персистентности. Это позволяет нам заменить два стека <tex>Rc_1, Rc_2</tex> на один стек <tex>R_2</tex>, в который мы и будем записывать перекопированный кусок.
Персистентная очередь будет состоять из пяти персистентных стеков: <tex>L_1, L_2, R_1, R_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стеки <tex>R_1, R_2</tex> используются для операций <tex>pop</tex>, а стек <tex>T</tex> используется для временного хранения содержимого стека <tex>R</tex>.
В каждый момент времени определено, какой стек <tex>L</tex> из стеков <tex>L_1, L_2</tex> сейчас используется для операций <tex>push</tex>, какой стек <tex>R</tex> из стеков <tex>R_1, R_2</tex> сейчас используется для операций <tex>pop</tex>, а также находится ли очередь в режиме перекопирования (''recopy mode'').
В режиме перекопирования операции <tex>push</tex> перенаправляются в парный стек <tex>L'</tex>; операции <tex>pop</tex> выполняются над последней персистентной версией <tex>R</tex>, тогда операция <tex>empty</tex> всегда возвращает <tex>false</tex>, так как стек <tex>L</tex> содержит <tex>n+1>0</tex> элементов, а в режиме перекопирования мы не можем извлечь их операцией <tex>pop</tex>.
Для хранения последней персистентной версии <tex>R</tex> мы используем второй имеющийся стек <tex>R'</tex>, а также переменную <tex>toCopy</tex> {{---}} количество элементов, оставшихся в <tex>R'</tex>, оно уменьшается на <tex>1</tex> с каждой следующей операцией <tex>pop</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>L</tex> в <tex>R</tex>, <tex>n + 1</tex> операция.
# Переместить первые <tex>toCopy</tex> элементов стека <tex>T</tex> в <tex>R</tex>, а оставшиеся элементы выкинуть, <tex>n</tex> операций.
# Обменять местами стеки <tex>L</tex> и <tex>L'</tex>, <tex>2</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> памяти на персистентность на операцию.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
