Персистентные структуры данных: Математика "путешествий во времени" в коде
В классическом императивном программировании изменение переменной или узла в дереве безвозвратно уничтожает старое значение. Если вам нужно отменить действие (Ctrl+Z), вам приходится заранее сохранять копию всей структуры, что катастрофически расходует оперативную память. В функциональном программировании и математической логике мутации запрещены. Для решения проблемы эффективного хранения истории изменений были придуманы персистентные структуры данных.
Персистентная структура данных (Persistent data structure) — это структура, которая при любом изменении сохраняет все свои предыдущие версии доступа (версионирование). Математическая задача состоит в том, чтобы новая версия переиспользовала максимум узлов из старой версии, чтобы время обновления и расход памяти оставались логарифмическими O(log N), а не линейными.
Для бинарных деревьев поиска эта задача решается методом копирования пути (Path Copying). Когда мы хотим вставить новый лист в иммутабельное дерево, мы не меняем существующие узлы. Мы создаем новый лист, затем создаем копию его родителя (который теперь ссылается на новый лист и на старого второго потомка), затем копию дедушки, и так вплоть до нового корня. В результате в памяти остаются два корня: старый корень ведет к старому состоянию дерева, а новый корень ведет к новому состоянию. При этом они совместно используют 99% неизмененных поддеревьев (Structural Sharing).
Существуют разные классы персистентности:
- Частично персистентные: можно читать любые прошлые версии, но изменять (создавать новые версии) можно только самую последнюю (как система контроля версий без ветвлений).
- Полностью персистентные: можно читать и изменять любую историческую версию, порождая параллельные ветки реальности (дерево версий).
- Сливаемые (Confluently persistent): ветки реальности можно математически сливать обратно в одну (операция Merge в Git).
Там, где метод копирования пути тратит слишком много памяти, применяется метод Толстых узлов (Fat Nodes). Каждый узел дерева превращается в мини-таблицу, хранящую историю изменений своих указателей с временными метками. Персистентные структуры — это не просто академическая абстракция, это математический фундамент работы языка Clojure, архитектуры Redux в веб-разработке и современных файловых систем (таких как ZFS и Btrfs), использующих механизм Copy-on-Write.
