Курсовой проект по дисциплине "Современные методы программирования" - "Persistent data structures"
Реализовать библиотеку со следующими структурами данных в persistent-вариантах (с единым API для всех структур)
- Массив (константное время доступа, переменная длина)
- Двусвязный список
- Ассоциативный массив (на основе Hash-таблицы, либо бинарного дерева)
- Должен быть единый API для всех структур, желательно использовать естественный API для выбранной платформы
- Обеспечить произвольную вложенность данных (по аналогии с динамическими языками), не отказываясь при этом полностью от типизации посредством generic/template;
- Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур);
- Реализовать более эффективное по скорости доступа представление структур данных, чем fat-node.
- Расширить экономичное использование памяти на операцию преобразования одной структуры к другой (например, списка в массив)
- Реализовать поддержку транзакционной памяти (STM)
- Кондакова Дарья Алексеевна, гр. 22225
- Хорошавин Алексей Константинович, гр. 22222
- Найти соответствующие алгоритмы;
- Подобрать и изучить публикации по теме Persistent Data Structures;
- Изучив теорию по персистентным структурам данных, реализовать их в проекте с использованием выбранного стека технологий.
| Сроки | Этап работы |
|---|---|
| до 24.11.2022 |
|
| до 08.12.2022 | Реализация базовой функциональности:
|
| до 24.12.2022 (что успеем) | Реализация дополнительной функциональности:
|
Неизменяемые структуры данных сохраняют свои предыдущие версии при изменении и, следовательно, являются фактически неизменными.
Полностью постоянные структуры данных допускают как обновления, так и запросы к любой версии. Многие операции вносят лишь небольшие изменения. Поэтому просто копирование предыдущей версии было бы неэффективным.
Чтобы сэкономить время и память, важно определить сходство между двумя версиями и переиспользовать как можно больший объем данных. Чаще всего в литературе о реализации неизменяемых структур данных встречаются два алгоритма Fat node и Path copying, а также их комбинации и улучшения.
Суть алгоритма состоит в том, чтобы записывать все изменения, внесенные в поля узлов в самих узлах, без удаления старых значений полей.
Главными проблемами данного алгоритма являются большой объем занимаемой памяти и амортизация времени для сохранения модификации из-за увеличения размеров узлов.
При использовании данного алгоритма создаются копии каждого узла встреченного на пути к измененному узлу. Поэтому для каждого изменения будет создан новый корень, по сути являющийся "новой версией" структуры данных.
В данной статье также описывается комбинация рассмотренных алгоритмов с привязкой к частному случаю деревьев поиска: Making data structures persistent.
Так как одно из дополнительных требований - применить более эффективное представление по сравнению с fat-node, то будем использовать path coping с применением структуры B-деревьев.
Данная реализация описана в лекции: 1. Persistent Data Structures
Для API можно использовать естественный вариант для известных структур в Java, для этого можно обратиться к официальной документации:
За основу для массива и списка было принято решение взять Java List, для мапы - Java Abstract Map.
Для обеспечения единого API (например, методы undo/redo) было решено добавить асбтрактный класс AbstractPersistentCollection, имплементирующий интерфейс UndoRedoCollection.
Рассматриваемые структуры связаны между собой, реализовав массив можно использовать похожий механизм для списка, а для хеш таблицы мапы можно уже использовать двусвязный список. Поэтому большая часть времени уйдет на реализацию персистентного массива.
В ходе поиска информации в Интернете был найден набор статей, посвященных персистентному вектору. На примере данной структуры описаны базовые алгоритмы, которые позволят понять, как их применить для массива, а затем списка и мапы.
Серия статей:
- Understanding Clojure's Persistent Vectors, pt. 1
- Understanding Clojure's Persistent Vectors, pt. 2
- Understanding Clojure's Persistent Vectors, pt. 3
- Understanding Clojure's Transients
- Persistent Vector Performance Summarised
В ходе изучения материала статей, были использованы структуры для хранения версий той или иной коллекции. Описан механизм поиска элемента по индексам с использованием битовых масок и преобразований, что дает оптимизацию операций над коллекциями.