Персистентный стек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
== Эффективная реализация ==
 
== Эффективная реализация ==
  
Попробуем решить задачу эффективнее. Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>
+
 
 +
Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека.
 +
 
 +
Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>
 
* <tex>push(x, i)</tex> - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
 
* <tex>push(x, i)</tex> - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
 
* <tex>pop(i)</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
 
* <tex>pop(i)</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
 
Результирующие стеки будут иметь номер n + 1.
 
Результирующие стеки будут иметь номер n + 1.
 +
 +
  
 
== Пример ==
 
== Пример ==
Строка 48: Строка 53:
 
<br>
 
<br>
  
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.
+
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти (массив длины n и n самих "стеков").
  
 
== См. также==
 
== См. также==

Версия 22:29, 1 марта 2012

Определение:
Персистентными структурами данных называются такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.


Рассмотрим такую структуру на примере стека.


Наивная реализация

Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции.
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет [math]O(n)[/math] и количество требуемой памяти — [math]O(n * n)[/math].

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

Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека.

Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:

  • [math]push(x, i)[/math] - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
  • [math]pop(i)[/math] - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.

Результирующие стеки будут иметь номер n + 1.


Пример

Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:
nothumb


Далее выполним [math]push(1, 5)[/math]. Создается новая вершина со значением 5, ссылающаяся на 1-ую:
nothumb

Аналогично выполним [math]push(2, 10)[/math] и [math]push(1, 6)[/math]:

nothumb

Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции [math]pop(2)[/math] и [math]pop(3)[/math]:


  • [math]pop(2)[/math] возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.


nothumb



  • [math]pop(3)[/math] возвращает 10 и копирует 2-ую вершину: получаем шестой стек.



nothumb

В итоге мы имеем доступ ко всем версиям стека за [math]O(1)[/math] времени и [math]O(n)[/math] памяти (массив длины n и n самих "стеков").

См. также

Ссылки