Pull to refresh

Персистентные структуры, часть 1: персистентный стек

Reading time 3 min
Views 37K
Я заметил, что на хабре было достаточно много постов о таких классических структурах данных, как стек, очередь, хип; рассматривались так же дерево отрезков и множество различных деревьев поиска, но очень мало внимания уделялось персистентным структурам данных. В этом цикле статей я хотел бы поговорить как раз о них. Так уж сложилось, что я достаточно давно занимаюсь олимпиадным программированием, так что рассматривать я их буду с точки зрения моего опыта применения персистентных структур в этой области.

Персистентными структурами данных мы будем называть такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры. Очевидно, что как один из вариантов (не самый лучший, конечно) можно рассматривать полное копирование всей структуры при каждом изменении. Это чрезвычайно неэффективно как по памяти, так и по времени работы, но этот способ можно применять например на стадии тестирования более сложной организации структуры. Но тем не менее толку от такой реализации мало, поэтому далее мы, кроме всего прочего, займемся поиском более оптимальных реализаций для различных структур.

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

Персистентный стек


Постановка задачи. Изначально существует один пустой стек с номером 0, n (количество стеков) изначально равно одному. От вас требуется реализовать следующие операции:
  • push(i, x) — Добавить элемент x в стек номер i. Результирующий стек будет иметь номер n + 1.
  • pop(i) — Вернуть последний элемент стека номер i и «выкинуть его из стека». Результирующий стек будет иметь номер n + 1.

Проще говоря, после каждой операции необходимо создать «новый» стек, не портя старый.

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

Для того, чтобы приблизиться к идее оптимального решения, можно попробовать представить стек в виде графа, где вершина — это его элемент, тогда от каждой вершины (кроме хвоста) пустим ребро в предыдущий элемент стека. Пример для стека, в который последовательно добавили '1', '2', '3', '4', '5':



Понятно, что для того, чтобы восстановить весь стек нам достаточно знать «голову» стека. Давайте попробуем вместо n копий стека хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:
  • push(x, i) — создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
  • pop(i) — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.


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


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


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


Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции pop(2) и pop(3):
pop(2) возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.


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


Очевидно, что один запрос работает за O(1) и суммарно требуется O(n) памяти, что не может не радовать.

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

N детей по очереди лепят снеговиков. Первый ребенок слепил снеговик из одного шара радиусом R1. Каждый следующий ребенок слепил такого же снеговика, как и предыдущий, но подумав немного либо добавил шар радиусом Ri, либо разрушил верхний, уже имеющийся шар. Гарантируется, что все снеговики имеют строго положительное число шаров. Входные данные — N, информация о каждом из детей о том, разрушил ли он последний шар, либо добавил свой (тогда дается и его радиус). Далее дается набор из K чисел в пределах от 1-го до N, для каждого требуется вывести последовательность шаров в снеговике с таким номером. Ограничение на N и K — миллион.

После прочтения раздела с реализацией персистентного стека решение этой задачи становится очевидным.

Заключение. Сегодня мы рассмотрели такую структуру данных, как персистентный стек и её эффективную реализацию. Это было полезно с точки зрения понимания в дальнейшем других персистентных структур и принципов их реализаций. Как уже было отмечено, в следующий статьях я планирую рассмотреть более сложные структуры, такие как персистентные очередь, декартово дерево и дерево отрезков. Сложнее структуры — сложнее и интереснее их реализации и решения с помощью них задач. Спасибо за внимание.
Tags:
Hubs:
+43
Comments 42
Comments Comments 42

Articles