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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
  
 
Самое простое и очевидное решение этой задачи —  честное копирование стека при каждой операции.  <br>
 
Самое простое и очевидное решение этой задачи —  честное копирование стека при каждой операции.  <br>
−
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n^2)</tex>.
+
Очевидно, это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n^2)</tex>.
  
 
== Эффективная реализация ==
 
== Эффективная реализация ==
  
−
 
+
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br>
−
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.  
+
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br>
−
 
 
−
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.
 
−
 
 
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
−
* <tex>push(i, x)</tex> — добавляет элемент х к стеку с номером i, результирующий стек будет иметь номер n + 1.
+
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.
 
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
 
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
−
результирующий стек будет иметь номер n + 1.
+
результирующий стек будет иметь номер <tex> n + 1 </tex>.
  
  
 
== Пример ==
 
== Пример ==
  
−
Пусть изначально у нас есть один пустой стек. Запишем его в массив.
+
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.
−
<br>
 
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
 
|- align = "center"
 
|- align = "center"
 
!index
 
!index
−
|1
+
!1
 
|-align = "center"
 
|-align = "center"
 
!value
 
!value
Строка 40: Строка 36:
 
|}
 
|}
  
−
<br>
+
 
−
<br>
+
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:
−
Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2ю ячейку массива:
 
−
<br>
 
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
 
|- align = "center"
 
|- align = "center"
 
!index
 
!index
−
|1
+
!1
−
|&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
 
|-align = "center"
 
|-align = "center"
 
!value
 
!value
Строка 59: Строка 53:
 
|}
 
|}
  
−
<br>
+
 
−
Аналогично выполним <tex>push(2, 5)</tex>:
+
* Аналогично выполним <tex>push(2, 5)</tex>:
−
<br>
 
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
 
|- align = "center"
 
|- align = "center"
 
!index
 
!index
−
|1
+
!1
−
|&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
 
|-align = "center"
 
|-align = "center"
 
!value
 
!value
Строка 80: Строка 73:
 
|}
 
|}
  
−
<br>
 
−
<br>
 
  
−
<br>
+
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.
−
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2ю вершину.
 
−
<br>
 
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
 
|- align = "center"
 
|- align = "center"
 
!index
 
!index
−
|1
+
!1
−
|&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;
 
|-align = "center"
 
|-align = "center"
 
!value
 
!value
Строка 107: Строка 96:
 
|}
 
|}
  
−
<br><br>
 
  
−
Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex>
+
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex>
  
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
 
|- align = "center"
 
|- align = "center"
 
!index
 
!index
−
|1
+
!1
−
|&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;
−
|&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;
+
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;
 
|-align = "center"
 
|-align = "center"
 
!value
 
!value
Строка 148: Строка 136:
 
<br>
 
<br>
  
−
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти (массив длины n и n самих "стеков").
+
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.
  
 
== См. также==
 
== См. также==

Версия 16:34, 7 июня 2012

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


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


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

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

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

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

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

результирующий стек будет иметь номер [math] n + 1 [/math].


Пример

  • Пусть изначально у нас есть один пустой стек. Запишем его в массив.
index 1
value [math]null[/math]
prev [math]null[/math]


  • Далее выполним [math]push(1, 3)[/math]. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:
index 1     2    
value [math]null[/math] 3
prev [math]null[/math] 1


  • Аналогично выполним [math]push(2, 5)[/math]:
index 1     2         3    
value [math]null[/math] 3 5
prev [math]null[/math] 1 2


  • Выполним [math]pop(3)[/math]. он возвращает 5 и копирует 2-ую вершину.
index 1     2         3         4    
value [math]null[/math] 3 5 3
prev [math]null[/math] 1 2 1


  • Так будет выглядеть массив после последовательности операций [math]push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):[/math]
index 1     2         3         4         5         6         7         8         9    
value [math]null[/math] 3 5 3 6 1 [math]null[/math] 5 9
prev [math]null[/math] 1 2 1 3 5 [math]null[/math] 2 7


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

См. также

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Персистентный_стек&oldid=24336»