142
правки
Изменения
Нет описания правки
==Преобразование списка в персистентный за O(1)==
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного <tex>log </tex> памяти.
Пусть мы имеем двусвязный список и хотим внести в него какое-то изменение, например, добавить узел <tex>Z</tex> между узлами <tex>X</tex> и <tex>Y</tex>, то есть при переходе из версии <tex>1</tex> в версию <tex>2</tex> добавим в наш двусвязный список узел <tex>Z</tex>.
Применим метод «толстых» узлов. Для этого в узлы <tex>X</tex> и <tex>Y</tex> добавим вторую версию и изменим ссылку, следующую из <tex>X</tex>, и предыдущую перед <tex>Y</tex>, как показано на рисунке.
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, мы изменяем только ее последнюю версию. Примем функцию потенциала равной числу полных узлов последней версии. Если мы склонировали <tex>k</tex> узлов, то количество полных узлов в последней версии уменьшится на <tex>k</tex>, и еще два узла мы добавим (по одному слева и справа). Таким образом, амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
==Общий метод построения частично персистентных структур данных==
Применим методы, описанные выше, в общем случае для абстрактной структуры данных. Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы <tex>P</tex>. Если мы будем клонировать узел, нам важно будет знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому будем в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый нами узел.
Все узлы будем хранить в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (''change log'') длиной не больше <tex>2P</tex>.
Пусть мы хотим внести изменение в нашу структуру данных в узел <tex>X</tex>. Если у нас есть место в ''change log''е, мы просто вносим наше изменение туда. Если ''change log'' заполнен, то мы клонируем узел <tex>X</tex>: берем стартовую версию узла, производим в ней все изменения, записанные в ''change log'', добавляем последнее изменение и делаем версию со свободным ''change log''ом. Затем пройдем по обратным ссылкам от <tex>X</tex> и в ''change log'' каждого узла, ссылающегося на <tex>X</tex>, добавим изменение указателя начиная с этой версии структуры данных с <tex>X</tex> на <tex>X'</tex>.
[[Файл:Частичная персистентность.png]]
Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех ''change log''ов в последней версии. Посмотрим, как меняется суммарный размер ''change log''ов, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.
Если ''change log'' был полный, то потенциал уменьшается на размер ''change log''а, так как мы склонировали узел с пустым ''change log''ом. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.
