142
правки
Изменения
Нет описания правки
Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех ''change log''ов в последней версии. Посмотрим, как меняется суммарный размер ''change log''ов, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.
Если ''change log'' был полный, то потенциал уменьшается на размер ''change log''а, так как мы склонировали узел с пустым ''change log''ом. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.
==Получение полностью персистентных структур данных==
Для полностью персистентных структур данных применить описанный выше метод преобразования не получится, так как история создания версий не линейна и нельзя отсортировать изменения по версиям, как в частично персистентных структурах данных.
Пусть мы храним историю изменения версий в виде дерева. Сделаем обход этого дерева в глубину. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда добавляется новая версия нашей структуры данных, мы вставляем два элемента в середину списка.
[[Файл:Полная персистентность.png]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции ''«insert after»'' и ''«order»''. Обе операции нужно делать за <tex>O(1</tex>). Это список с поддержкой запроса о порядке (''List Order Maintenance'').
Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью ''List Order Maintenance''.
В какой-то момент <math>change log</math> «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный числу полных узлов. Когда мы раздваиваем узел, мы уменьшаем число полных узлов на единицу.
