Персистентные структуры данных

Эта статья находится в разработке!

Определение:

Персистенные структуры данных – это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояния.

Уровни персистентности

Есть несколько уровней персистентности

• частичная (англ. partial)
• полная (англ. full)
• конфлюэнтная (англ. confluent)
• фунциональная (англ. functional)

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

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

Конфлюэнтные структуры данных позволяют объединять две структуры данных в одну (деревья поиска, которые можно сливать).

Функциональные структур данных полностью персистентны по определению, так как в них запрещаются уничтожающие присваивания, т.е. любой переменной значение может быть присвоено только один раз и изменять значения переменных нельзя. Если структура данных функциональна, то она и конфлюэнтна, если конфлюэнтна, то и полностью персистентна, если полностью персистентна, то и частично персистентна. Однако бывают структуры данных не функциональные, но конфлюэнтные.

Способы преобразования структур данных в персистентные

Есть несколько способов сделать любую структуру персистентной:

• полное копирование (англ. full copy) когда при любой операции изменения полностью копируется структура данных и в получившуюся новую копию вносятся изменения;
• копирование пути (англ. path copiyng);

• метод «толстых» узлов (англ. fat node).

Рассмотрим для начала частичную персистентность. Для наглядности занумеруем разные версии структур данных. История изменений структуры данных линейна, мы в любой момент времени можем обратиться к любой версии структуры данных, но поменять можем только последнюю версию.

Сформулируем, что такое структура данных. Это набор узлов, в которых хранятся какие-то данные и эти узлы связаны ссылками. Классический пример структуры данных - дерево. Рассмотрим, как методом копирования пути превратить дерево в персистентное.

Метод копирование пути

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

Метод «толстых» узлов

Пусть в структуре данных есть узел, в котором нужно сделать изменения (например, на нашем рисунке в первой версии структуры данных есть поле [math]a=3[/math], а во второй версии это поле должно быть равно [math]4[/math]), но при этом нужно сохранить доступ и к старой версии узла. В таком случае можно хранить их оба в большом комбинированном узле.

‎

В нашем примере в этом «толстом» узле будет храниться первая версия [math]V_1[/math], у которой [math]a=3[/math] и вторая версия [math]V_2[/math], у которой [math]a=4[/math]. Если далее последуют еще какие-то изменения (например, поле [math]b[/math] нашего узла станет равно [math]5[/math]) сделаем еще одну версию структуры данных – [math]V_3[/math]. Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.

Преобразование списка в персистентный за O(1)

Если скомбинировать методы path copiyng и fat node, то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного [math]log[/math] памяти. Пусть мы имеем двусвязный список и хотим внести в него какое-то изменение, например, добавить узел [math]Z[/math] между узлами [math]X[/math] и [math]Y[/math], то есть при переходе из версии [math]1[/math] в версию [math]2[/math] добавим в наш двусвязный список узел [math]Z[/math]. Применим метод «толстых» узлов. Для этого в узлы [math]X[/math] и [math]Y[/math] добавим вторую версию и изменим ссылку, следующую из [math]X[/math], и предыдущую перед [math]Y[/math], как показано на рисунке. Эта структура работает так. Например, мы знаем, что текущая первая версия и идем по нашему списку слева направо от первого узла к узлу [math]X[/math], а затем хотим перейти к следующему узлу. В «толстом» узле [math]X[/math] мы выбираем нужную нам версию и далее следуем по ссылкам.

Пусть мы хотим добавить еще один элемент между узлами [math]X[/math] и [math]Y[/math], но проблема в том, что у [math]X[/math] и [math]Y[/math] уже есть вторая версия, добавлять третью невыгодно. Поэтому более двух версий добавлять не будем. Используем метод копирования пути. Скопируем узлы [math]X[/math] и [math]Y[/math], начиная с их третьей версии, и свяжем новые узлы с исходным списком. Для этого добавим вторые версии предыдущему перед [math]X[/math] и последующему после [math]Y[/math] узлам и свяжем эти узлы соответствующими ссылками. Так все версии остаются доступными.

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

Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, мы изменяем только ее последнюю версию. Примем функцию потенциала равной числу полных узлов последней версии. Если мы склонировали [math]k[/math] узлов, то количество полных узлов в последней версии уменьшится на [math]k[/math], и еще два узла мы добавим (по одному слева и справа). Таким образом, амортизационное время работы по добавлению элемента будет [math]O(1)[/math].

Общий метод построения частично персистентных структур данных

Применим методы, описанные выше, в общем случае для абстрактной структуры данных. Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы [math]P[/math]. Если мы будем клонировать узел, нам важно будет знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому будем в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый нами узел. Все узлы будем хранить в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (change log) длиной не больше [math]2P[/math]. Пусть мы хотим внести изменение в нашу структуру данных в узел [math]X[/math]. Если у нас есть место в change logе, мы просто вносим наше изменение туда. Если change log заполнен, то мы клонируем узел [math]X[/math]: берем стартовую версию узла, производим в ней все изменения, записанные в change log, добавляем последнее изменение и делаем версию со свободным change logом. Затем пройдем по обратным ссылкам от [math]X[/math] и в change log каждого узла, ссылающегося на [math]X[/math], добавим изменение указателя начиная с этой версии структуры данных с [math]X[/math] на [math]X'[/math].

Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех change logов в последней версии. Посмотрим, как меняется суммарный размер change logов, когда мы совершаем одно изменение. Если change log был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу. Если change log был полный, то потенциал уменьшается на размер change logа, так как мы склонировали узел с пустым change logом. После этого мы пошли по обратным ссылкам (их было [math]P[/math] штук) и добавили в [math]P[/math] узлов по одному значению. Таким образом амортизированное время работы будет [math]O(1)[/math].

Получение полностью персистентных структур данных

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

Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции «insert after» и «order». Обе операции нужно делать за [math]O(1[/math]). Это список с поддержкой запроса о порядке [[ http://www.cs.au.dk/~gerth/aa11/slides/order.pdf%7C List Order Maintenance]]. Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает. В change log «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью List Order Maintenance. В какой-то момент change log «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в change log склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.

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

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

См. также

• Персистентный стек
• Персистентная очередь
• Персистентный дек

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

• Дополнительные главы алгоритмов. Лекции А. Станкевича
• Персистентные структуры данных. Лекции Павла Маврина