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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 22715 участника Yurik (обсуждение))
м (rollbackEdits.php mass rollback)
 
(не показано 55 промежуточных версий 8 участников)
Строка 1: Строка 1:
{{Определение
+
== Алгоритм ==
|definition=Персистентными структурами данных называются такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.
 
}}
 
  
Рассмотрим такую структуру на примере стека.
+
=== Реализация на массиве ===
 +
Заведем массив запросов, модифицирующих стек.<br>
 +
  '''struct''' '''Query''':
 +
    '''T''' value
 +
    '''uint''' prev
 +
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 +
Тогда операции push и pop будут иметь следующий вид:<br>
 +
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек с номером <tex>i</tex>, результирующий стек будет иметь номер <tex> n + 1 </tex>,
 +
  '''function''' push(i : '''uint''', x : '''T'''):
 +
    s.top = s.top + 1
 +
    s[s.top].value = x
 +
    s[s.top].prev = i
 +
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i</tex> и копирует элемент, предыдущий для него, результирующий стек будет иметь номер <tex> n + 1 </tex>.
 +
  '''T''' pop(i : '''uint'''):
 +
    '''Query''' k = s[i]
 +
    k = s[k.prev]
 +
    push(k.prev, k.value)
 +
    '''return''' s[i].value
  
 +
=== Реализация на списке ===
 +
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.
 +
  '''struct''' '''Node''':
 +
    '''T''' value
 +
    '''Node''' prev
 +
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
 +
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
 +
Сам персистентный стек будет обозначаться <tex>s</tex>.<br>
  
== Наивная реализация ==
+
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
 +
  '''Stack''' push(i : '''Node''', x : '''T'''):
 +
    k.value = x
 +
    k.prev = i
 +
    s.top = k
 +
    '''return''' s
  
Самое простое и очевидное решение этой задачи —  честное копирование стека при каждой операции.  <br>
+
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него.
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n * n)</tex>.
+
  '''pair<T, Stack>''' pop(i : '''Node'''):
 +
    '''T''' val = i.value
 +
    i = i.prev
 +
    '''return''' pair(val, s)
  
== Эффективная реализация ==
+
== Пример ==
  
 +
Пусть изначально у нас есть один пустой стек. Запишем его в массив.
 +
[[Файл:стек1.png|500px|nothumb|right|]]
 +
{| border = 1; cellspacing = 0; class="wikitable"
 +
|- align = "center"
 +
!index
 +
!1
 +
|-align = "center"
 +
!value
 +
|<tex>\mathtt{null}</tex>
 +
|-align = "center"
 +
!prev
 +
|<tex>\mathtt{null}</tex>
 +
|}
  
Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека.
 
  
Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>
+
Далее выполним <tex>\mathrm{push}(1, 3)</tex>. Создается новая вершина со значением <tex>3</tex>, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:
* <tex>push(x, i)</tex> - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
+
[[Файл:стек2.png|500px|nothumb|right|]]
* <tex>pop(i)</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
+
{| border = 1; cellspacing = 0; class="wikitable"
Результирующие стеки будут иметь номер n + 1.
+
|- align = "center"
 +
!index
 +
!1
 +
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
 +
|-align = "center"
 +
!value
 +
|<tex>\mathtt{null}</tex>
 +
|3
 +
|-align = "center"
 +
!prev
 +
|<tex>\mathtt{null}</tex>
 +
|1
 +
|}
  
  
 +
Аналогично выполним <tex>\mathrm{push}(2, 5)</tex>:
 +
[[Файл:стек3.png|500px|nothumb|right|]]
 +
{| border = 1; cellspacing = 0; class="wikitable"
 +
|- align = "center"
 +
!index
 +
!1
 +
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
 +
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
 +
|-align = "center"
 +
!value
 +
|<tex>\mathtt{null}</tex>
 +
|3
 +
|5
 +
|-align = "center"
 +
!prev
 +
|<tex>\mathtt{null}</tex>
 +
|1
 +
|2
 +
|}
  
== Пример ==
 
  
Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:
+
Выполним <tex>\mathrm{pop}(3)</tex>. Он возвращает <tex>5</tex> и копирует 2-ую вершину.
<br>
+
[[Файл:стек4.png|500px|nothumb|right|]]
[[Файл:B5bb212f3702e565498c4412e13242a7.jpg|Картинка]]<br>
+
{| border = 1; cellspacing = 0; class="wikitable"
<br>
+
|- align = "center"
<br>
+
!index
Далее выполним <tex>push(1, 5)</tex>. Создается новая вершина со значением 5, ссылающаяся на 1-ую:
+
!1
<br>
+
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;
[[Файл:612b6fe1562242b3a455b2abb698dfc9.jpg|nothumb]]<br>
+
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;
<br>
+
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;
Аналогично выполним <tex>push(2, 10)</tex> и <tex>push(1, 6)</tex>:
+
|-align = "center"
<br><br>
+
!value
[[Файл:2beb71892fd79b675e095d5432827d03.jpg|nothumb]]
+
|<tex>\mathtt{null}</tex>
<br>
+
|3
 +
|5
 +
|3
 +
|-align = "center"
 +
!prev
 +
|<tex>\mathtt{null}</tex>
 +
|1
 +
|2
 +
|1
 +
|}
  
Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции <tex>pop(2)</tex> и <tex>pop(3)</tex>:
 
  
<br>
+
Так будет выглядеть массив после последовательности операций <tex>\mathrm{push}(3, 6),  \mathrm{push}(5, 1),  \mathrm{pop}(4),  \mathrm{pop}(5),  \mathrm{push}(7, 9):</tex>
* <tex>pop(2)</tex> возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.
+
[[Файл:стек.png|500px|nothumb|right|]]
<br>
+
{| border = 1; cellspacing = 0; class="wikitable"
[[Файл:3ab7456751529d76c5f1392d5d3b5fcb.jpg|nothumb]]
+
|- align = "center"
 +
!index
 +
!1
 +
!&nbsp;&nbsp;&nbsp;&nbsp;2&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;5&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;8&nbsp;&nbsp;&nbsp;&nbsp;
 +
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;
 +
|-align = "center"
 +
!value
 +
|<tex>\mathtt{null}</tex>
 +
|3
 +
|5
 +
|3
 +
|6
 +
|1
 +
|<tex>\mathtt{null}</tex>
 +
|5
 +
|9
 +
|-align = "center"
 +
!prev
 +
|<tex>\mathtt{null}</tex>
 +
|1
 +
|2
 +
|1
 +
|3
 +
|5
 +
|<tex>\mathtt{null}</tex>
 +
|2
 +
|7
 +
|}
  
<br><br>
 
  
* <tex>pop(3)</tex> возвращает 10 и копирует 2-ую вершину: получаем шестой стек.
+
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.
<br><br>
 
[[Файл:Eced2ebbcee643d6c87576b0d3460785.jpg|nothumb]]<br>
 
<br>
 
  
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти (массив длины n и n самих "стеков").
+
== Применение ==
 +
Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках). <br>
 +
См. [[Персистентная очередь]]
  
 
== См. также==
 
== См. также==
Строка 60: Строка 172:
 
* [[Персистентный дек]]
 
* [[Персистентный дек]]
  
== Ссылки ==
+
== Источники информации ==
  
* [http://habrahabr.ru/blogs/algorithm/113585/ Персистентный стек - статья на хабре]
+
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr {{---}} Персистентный стек]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
[[Категория: Структуры данных ]]
+
[[Категория: Амортизационный анализ]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:33, 4 сентября 2022

Алгоритм

Реализация на массиве

Заведем массив запросов, модифицирующих стек.

 struct Query:
   T value
   uint prev

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

  • [math] \mathrm{push}(i, x)[/math] — добавляет элемент [math]x[/math] в стек с номером [math]i[/math], результирующий стек будет иметь номер [math] n + 1 [/math],
 function push(i : uint, x : T):
   s.top = s.top + 1
   s[s.top].value = x
   s[s.top].prev = i 
  • [math]\mathrm{pop}(i)[/math] — возвращает значение, хранящееся в элементе с номером [math]i[/math] и копирует элемент, предыдущий для него, результирующий стек будет иметь номер [math] n + 1 [/math].
 T pop(i : uint):
   Query k = s[i]
   k = s[k.prev]
   push(k.prev, k.value)
   return s[i].value

Реализация на списке

Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.

 struct Node:
   T value
   Node prev

Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.
У каждого узла будет [math]2[/math] поля: значение в вершине стека и ссылка на предыдущую версию стека.
Сам персистентный стек будет обозначаться [math]s[/math].

  • [math] \mathrm{push}(i, x)[/math] — добавляет элемент [math]x[/math] в стек узла [math]i[/math],
 Stack push(i : Node, x : T):
   k.value = x
   k.prev = i
   s.top = k
   return s
  • [math]\mathrm{pop}(i)[/math] — возвращает значение, хранящееся в узле [math]i[/math] и копирует элемент, предыдущий для него.
 pair<T, Stack> pop(i : Node):
   T val = i.value 
   i = i.prev
   return pair(val, s)

Пример

Пусть изначально у нас есть один пустой стек. Запишем его в массив.

Стек1.png
index 1
value [math]\mathtt{null}[/math]
prev [math]\mathtt{null}[/math]


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

Стек2.png
index 1     2    
value [math]\mathtt{null}[/math] 3
prev [math]\mathtt{null}[/math] 1


Аналогично выполним [math]\mathrm{push}(2, 5)[/math]:

Стек3.png
index 1     2         3    
value [math]\mathtt{null}[/math] 3 5
prev [math]\mathtt{null}[/math] 1 2


Выполним [math]\mathrm{pop}(3)[/math]. Он возвращает [math]5[/math] и копирует 2-ую вершину.

Стек4.png
index 1     2         3         4    
value [math]\mathtt{null}[/math] 3 5 3
prev [math]\mathtt{null}[/math] 1 2 1


Так будет выглядеть массив после последовательности операций [math]\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(4), \mathrm{pop}(5), \mathrm{push}(7, 9):[/math]

Стек.png
index 1     2         3         4         5         6         7         8         9    
value [math]\mathtt{null}[/math] 3 5 3 6 1 [math]\mathtt{null}[/math] 5 9
prev [math]\mathtt{null}[/math] 1 2 1 3 5 [math]\mathtt{null}[/math] 2 7


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

Применение

Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках).
См. Персистентная очередь

См. также

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