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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Тикет 1-1-3)
(Эффективная реализация: тикет 1-1)
Строка 16: Строка 16:
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.
 
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.
   mas.push_back(value = x, prev = i)
+
   arr.push (x, i)
 
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
 
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
 
результирующий стек будет иметь номер <tex> n + 1 </tex>.
 
результирующий стек будет иметь номер <tex> n + 1 </tex>.
   mas.push_back( copy_of(mas[i.prev]) )
+
   a = arr[прошлый элемент для i-ого];
 +
  arr.push(a);
  
 
== Пример ==
 
== Пример ==

Версия 14:33, 9 мая 2015

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


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


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

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

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

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

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

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

 a = arr[прошлый элемент для i-ого];
 arr.push(a);

Пример

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


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


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


  • Выполним [math]pop(3)[/math]. он возвращает 5 и копирует 2-ую вершину.
Стек4.png
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]
Стек.png
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] памяти.


См. также

Ссылки