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

Задача, в целом, фундаментальная, но вопрос мой вопрос произрастает из истоков олимпиадного программирования, где скорость - ключевой ресурс. Чтобы не было проблем в четкости формулировки, прикреплю ссылку. Вот [1] (http://acm.timus.ru/problem.aspx?space=1&num=1992)!
Но если коротко, то есть объект, в который можно добавлять что-то и это же самое убирать (откатываться до прежней версии, более старого содержимого), а потом, аналогично, восстанавливать откаты. Но самое важное - можно делать клонирование объекта со всей его историей откатов и текущим состоянием. Именно тут и всплывает вопрос: как реализовать клонирование наиболее оптимальным способом?
Конечно, самым простым решением является просто полное клонирование (.clone(), в java) с реализацией интерфейса Cloneable или схожего. После этого у нас будут две независимые сущности, с которыми можно работать; критический недостаток - количество потребляемой памяти и время, конечно же. Есть идеи как улучшить и оптимизировать обычную идею двух стеков; или же что альтернативное? Спасибо!

Ответ

Ещё одно популярное решение — иммутабельные структуры данных. При этом вам не нужно никогда глубокое копирование, вы можете повторно использовать общие части, т. к. они не изменяются.
При создании нового состояния вы копируете ссылки на все неизменившиеся части старого в объект, представляющий собой новое состояние (это быстро и не требует много памяти). Изменившиеся части создаёте заново (или если у вас есть эта информация, используете её, раз она иммутабельна). Новое состояние храните в списке «версий» состояния.
Дополнительное чтение по теме: Immutability in C# Part Two: A Simple Immutable Stack (да, это на C#, но принципы те же).