Быстрое клонирование

#java #алгоритм #память #структуры_данных

Задача, в целом, фундаментальная, но вопрос мой вопрос произрастает из истоков олимпиадного
программирования, где скорость - ключевой ресурс.
Чтобы не было проблем в четкости формулировки, прикреплю ссылку. Вот [1] (http://acm.timus.ru/problem.aspx?space=1&num=1992)!


Но если коротко, то есть объект, в который можно добавлять что-то и это же самое
убирать (откатываться до прежней версии, более старого содержимого), а потом, аналогично,
восстанавливать откаты. Но самое важное - можно делать клонирование объекта со всей
его историей откатов и текущим состоянием. Именно тут и всплывает вопрос: как реализовать
клонирование наиболее оптимальным способом?


Конечно, самым простым решением является просто полное клонирование (.clone(), в
java) с реализацией интерфейса Cloneable или схожего. После этого у нас будут две независимые
сущности, с которыми можно работать; критический недостаток - количество потребляемой
памяти и время, конечно же. Есть идеи как улучшить и оптимизировать обычную идею двух
стеков; или же что альтернативное?

Спасибо!  
    

Ответы

Ответ 1

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

При создании нового состояния вы копируете ссылки на все неизменившиеся части старого
в объект, представляющий собой новое состояние (это быстро и не требует много памяти).
Изменившиеся части создаёте заново (или если у вас есть эта информация, используете
её, раз она иммутабельна). Новое состояние храните в списке «версий» состояния.

Дополнительное чтение по теме: Immutability in C# Part Two: A Simple Immutable Stack
(да, это на C#, но принципы те же).


Ответ 2

Обращаю внимание, что в запросах на вывод надо назвать только последнюю технологию.



Там нужен указатель на предка в дереве. Даже само дерево не нужно.

Каждый элемент имеет значение и ссылку на такой же. Массив клонов содержит такие
элементы. Массив деков содержит последовательность откатов для клона.

Вроде на этом всё. Любая операция выполняется за O(1).


Ответ 3

Вариант 1. (Copy-on-Write)

Создаём копию в виде ссылки. Когда изменится оригинал либо копия, выполняем глубокое
копирование. Если ничего не меняется, память почти не расходуется, максимум что нам
надо - несколько байт для счётчика.



Вариант 2

А вот теперь решение посложнее. История изменений объекта фактически есть набор состояний
объекта. Эти состояния можно упорядочить. Создаём массив, в который помещаем состояние
объекта после изменения. С каждым объектом будет связан вектор ссылок на состояния.
Вектор ссылок в общем случае требует меньше места, чем набор состояний. Вектор копируем
при копировании объекта.

Ещё можно гибридизировать оба подхода, копируя вектор ссылок только при изменении
объектов.