Изменения

Перейти к: навигация, поиск

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

11 байт добавлено, 22:26, 30 марта 2015
Получение полностью персистентных структур данных
[[Файл:Полная персистентность.png‎]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции ''«insert after»'' и ''«order»''. Обе операции нужно делать за <tex>O(1</tex>). Это список с поддержкой запроса о порядке [''List Order Maintenance'' <ref>[ http://www.cs.au.dk/~gerth/aa11/slides/order.pdf| List Order Maintenance]]</ref>.
Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью ''List Order Maintenance''.
142
правки

Навигация