Персистентность
Мотивация
Мы хотим откатываться в прошлые состояния.
Виды персистентности
-
Частичная - можем изменять только последнюю версию, но читать любое прошлое состояние. Это компромисс между гибкостью и простотой реализации. Примеры: хранение истории изменений в текстовом редакторе, "undo/redo".
-
Полная - можем изменять любое прошлое состояние, при этом изменения создают новую версию, не влияя на исходное состояние. Это наиболее гибкий подход, позволяющий исследовать различные ветви развития данных.
-
Конфлюентная - полная персистентность с возможностью объединять различные версии, порождая новые. Этот вид персистентности является наиболее сложным в реализации, но открывает интересные возможности для анализа и синтеза исторических данных. Похоже на ветки в системах контроля версий (Git).
Учимся в персистентность
Персистентный стек
Пусть у нас стек — это односвязный список. В персистентной версии, каждый push создаёт новую ноду односвязного списка, разделяя часть структуры с предыдущими версиями. Таким образом, у нас есть один большой-стек дерево, и масив "указателей" на вершины каждой из версий
Реализация операции push:
Операция push(value, stack) создает новый элемент (ноду) списка, в котором:
- value - значение, которое кладется на стек.
- next - указатель на предыдущую версию стека stack.
Положим в индекс текущей версии указатель на данную вершину. Таким образом, push не изменяет предыдущую версию и никак не трогает другие версии. Важно отметить, что push выполняется за O(1), так как создается только один новый элемент.
Реализация операции pop:
Операция pop(stack) возвращает новую версию стека, полученную путем удаления первого элемента из списка stack. Предыдущая версия stack остается неизменной. pop также выполняется за O(1), так как просто возвращает указатель на следующий элемент в списке и ставит указатель в массиве версий на эту вершину
Персистентная очередь
2 персистентных стека. Версия нашей очереди характеризуется версиями 2-ух стеков. Но проблема, когда перекладываем: делая push и pop к одной версии мы каждый раз будем тратить O(n) времени на перекладку. То есть мы проигрываем в асимптотике. (частичная персистентность бы тут прокатила)
Амортизированные оценки ломаются.
Персистентный массив
Fat nodes
Каждый узел (node) структуры данных содержит историю изменений своих полей. Поиск нужной версии поля осуществляется по временной метке. Этот подход может потребовать значительного объема памяти для хранения истории.
В данном случае получилось, что мы реализовали частичную персистентность
Сдлеаем полностью персистентный массив, для этого научимс делать персистентное ДО
Персистентное ДО
Умеем минимум на отрзке и изменять значение в точке.
Применим технику Path Coping.
Общая идея Path Copying:
Основная идея заключается в том, что при изменении значения в ДО мы не изменяем существующие узлы напрямую. Вместо этого мы создаем новые узлы вдоль пути от корня к изменяемому листу, копируя данные из старых узлов. Все узлы, не лежащие на этом пути, остаются неизменными, что позволяет нам сохранять предыдущие версии дерева.
Update имеет сложность O(log n), где n - размер массива, так как он проходит только по одному пути в дереве. build имеет сложность O(n).
Память: В худшем случае, при каждом обновлении создается O(log n) новых узлов. Поэтому требуется O(m log n + n) памяти для хранения m версий дерева.
Массовые операции пишутся тоже также.
Теперь понятно, как делать перс массив.
Персистентный Декартач.
Делаем его так же, конкретнее читайте здесь.
Откаты
Хотим делать операцию: забудь про последние k операций, вернись в реальность.
Обычно просто храним стек с изменениями и всё