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

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

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

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

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


Постановка задачи. Изначально существует один пустой стек с номером 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 — миллион.

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

Заключение. Сегодня мы рассмотрели такую структуру данных, как персистентный стек и её эффективную реализацию. Это было полезно с точки зрения понимания в дальнейшем других персистентных структур и принципов их реализаций. Как уже было отмечено, в следующий статьях я планирую рассмотреть более сложные структуры, такие как персистентные очередь, декартово дерево и дерево отрезков. Сложнее структуры — сложнее и интереснее их реализации и решения с помощью них задач. Спасибо за внимание.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 42
    +9
    > Заключение. Сегодня мы рассмотрели

    Откуда это вот берётся? :) Уже в куче статей в последнее время видел. Вы ж не лабораторную сдаёте и не курсовой, дык зачем этот официоз? В конце-концов, резюме, конечно, нужно, но чаще всего оно в таком виде подаётся, что ощущаешь себя преподом, принимающим списанную лабу.
      +2
      Да, пожалуй вы правы. Видимо это от чрезмерного старания — как-никак первый раз пробую себя на хабре =)
        0
        Это полезная штука.

        Есть стандартная структура статей: вступление, основная часть и заключение.

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

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

        Кроме того, повторение--мать учения. Кажется, чтобы информация запомнилась, ее надо повторять через 20 минут, через пару чаов и через пару дней. Заключение как раз и соответствует первому повторению.
          +2
          А я и не говорил, что заключение не нужно. Нужно, конечно же. Но вот стиль подачи у многих очень попахивает университетской банальностью. «Мы рассмотрели бла-бла-бла, из чего сделали вывод бла-бла-бла».
          Мы ж на хабре, а не на сдаче курсовой, да? К чему все эти ненужности? Можно простым языком написать, а не используя этот банальный штамп, вбитый всем нам в голову в институтах.
        +1
        А в какой литературе с этими структурами данных можно познакомиться поподробнее?
          0
          Насколько я знаю, это направление возникло относительно недавно, и в больших книжках (да и в маленьких тоже) о нём не прочитать.

          P.S. о_О Ваш первый комментарий за последние почти 4 года.
            0
            Относительно недавно это стало модно на олимпиадах использовать, насколько я знаю.
              +1
              модно это стало в том числе в свете многопоточности
              +1
              Вот описание в точности такого же стека. Дата публикации: 15 December 1983.
              0
              Если не ошибаюсь, можно поискать что-нибудь Тарьяна
                +1
                да, да, тоже на него наткнулся www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
              • НЛО прилетело и опубликовало эту надпись здесь
                0
                Насколько я знаю, это направление возникло относительно недавно, и в больших книжках (да и в маленьких тоже) о нём не прочитать.

                P.S. о_О Ваш первый комментарий за последние почти 4 года.
                  +1
                  очень похоже все это на immutable stack из блога Эрика Липперта. Там только упор делается не на возможность получения любой версии, а на неизменяемость объекта. Впрочем, по-моему получилось тоже самое. кстати там целый цикл великолепный статей про неизменяемость (immutability)
                    +1
                    На ВКОШПе последнем была задачка, которая решалась в том числе персистентным деревом отрезков.
                      +1
                      Ну не обязательно деревом отрезков, когда я ее решал (к сожалению уже после олимпиады =)), я использовал декартово дерево по неявному ключу.

                      Вообще я как раз планировал разобрать ее, когда речь будет идти о декартовом дереве.
                      +1
                      > Очевидно, что один запрос работает за O(1)
                      Мне не очевидно :) Вы не заострили внимание, что это зависит от того, как мы ищем i-й элемент. На вскидку массив даст константный доступ, но или нужно зарезервировать достаточно места, либо его расширять динамически. Хотя в алгоритмах я не разбираюсь, и буду рад, если укажите, где я ошибся :)
                        +1
                        Да, пожалуй стоило упомянуть, что речь идет о структуре типа массив.

                        Насчет динамического расширенияВ данном случае можно зарезервировать изначально массив из 1-го элемента. Далее при каждом добавлении количество элементов растет, и когда оно становится равным зарезервированному количеству мы расширяем его в два раза. Каждое расширение работает за O от количества элементов на момент расширения.

                        Если мы добавили n элементов (округлим n вверх так, чтобы n = 2 ^ k), то суммируя количество операций расширения получим: 1 + 2 + 4 + 8 +… + 2 ^ k = 2 ^ (k + 1) = 2 * n, откуда получаем O(n). Таким образом количество операций, потраченных на расширение имеет тот же порядок, что и количество операций добавления, что не может не радовать.
                          0
                          Ах жаль, с тегом промазал =(
                            +1
                            Ну и стоит упомянуть, что vector в c++ делает именно это.
                              0
                              Стоит упомянуть, что он еще умеет освобождать память, о чем речь пока не идет.
                              0
                              Какое суммирование, вы о чем? Я нахожусь на n-ом шаге и до этого только добавлял, и мне нужно целиком скопировать весь массив. Это O(n)! В худшем случае, добавление займет O(n). Понятно, что в среднем, особенно если я буду часто удалять, это будет O(1), но это совсем не гарантировано.

                              Я правильно понял, что вы пытались усреднить?
                                0
                                Формально — да, но…

                                Пусть вас не пугает то, что нужно скопировать весь массив. Выше я написал, почему если просуммировать все операции после добавления n элементов мы получим O(n) операций (кстати с небольшой константой), т.е. O(1) на одно добавление.

                                Кстати удаление на эту оценку никак не влияет.
                                  0
                                  Как раз встал с кровати, осознав, что удаление не влияет, и уведомление пришло :)
                            0
                            А у понятия персистентная структура есть русское название?
                              0
                              Никогда не встречал, мне кажется что нет =)
                                0
                                «Неизменяемая» (хотя это скорее immutable), «сохраняемая», не? Хотя вообще отличеие persistent jn immutable лишь в хранении указателей на старые версии насколько я понимаю.
                                  +1
                                  Вообще, мне казалось, что персистентный означает сохраняемый между запусками программы. Так что для таких структур, ИМХО, immutable лучше подходит.
                                    0
                                    Прочитав статью автора мне показалось, что его персистентный стек не что иное как immutable стэк. Беглое гугление привело меня в википедию, где написано «Persistent data structures are effectively immutable». То есть всякая persistent data structure является immutable. Но там не говорится, являются ли эти классы эквивалентными, то есть immutable -> persistent. Беглое гугление на этот вопрос ответа уже не дало, придумать immutable, но не persistent структуру мне не удалось. Поэтому я бы не стал утверждать, что «immutable лучше подходит» без должного обоснования.
                                      0
                                      «Persistence in computer science refers to the characteristic of state that outlives the process that created it» — с вики
                                        +1
                                        у нас прямо конкурс цитат :) из статьи по моей ссылке: «A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word „persistent.“» То есть слово одно, а значений два (минимум).
                                          0
                                          Спасибо, почитаю повнимательнее :)
                              0
                              По прочтении статьи возникло стойкое желание прочитать кого-нибудь авторитетного по этим структурам данных. Гугл мямлит что-то о модуле для Перла. Не более.

                              На мой скорый взгляд, тут описано некий намек на реализацию дерева с числовым индексом в виде идентификатора узла.

                              Меня гложат большие сомнения по поводу адекватности производительности поиска по несбалансированному дереву по цифровому индексу (в статье — номер ревизии стека) для обращения к элементам дерева\стека.

                              Непонятен вопрос, как собрать все конечные состояния стека (а их может быть список)?

                              Как держать актуальный список головных ревизий? /Головная ревизия — последнее на текущий момент изменение всех веток развития стека/

                                0
                                Головная ревизия — <… бла-бла...>: перемудрил, простите. :)

                                Головная ревизия — набор всех изменений одной ветки развития стека.
                                  0
                                  Чего-то не проснусь никак… Зачеркните мой предыдущий пост. :)

                                  Головная ревизия — это последнее на текущий момент изменение в одной ветке развития.

                                  Разрисована оранжевым фоном.

                                  Состояние стека в одной из веток может быть получен, как я понимаю, проходом через все узлы соответствующей ветки (помечена красной окантовкой)

                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  Все это дело можно хранить на массиве (например vector в с++). Выше я писал почему это работает достаточно быстро. Никаких деревьев не нужно.
                                  0
                                  Классная задача и элегантный метод решения, супер. Интересно, каким способом можно реализовать персистентность произвольного графа.
                                    +1
                                    Я в подробностях рассмотрю для деревьев в одной из следующих статей
                                    +1
                                    Спасибо, полезная статья!
                                    Можно привести еще несколько задач на эту структуру данных? И, если возможно, с контестером — чтобы можно было проверить решение.
                                      +1
                                      Конкретно на стэк — не знаю. Это достаточно простая структура. Есть задача на персистентное дерево отрезков с ВКОШП-2010 (I, «Откаты»). Но она довольно сложная.
                                      Условия и тесты

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                    Самое читаемое