nsu-sdt-pds

Курсач по СМП на тему "Persistent data structure"

• Алгоритмы
• Умные расчеты

Пресистентность в Кожуре

• #01
• #02
• #03
• #04
• #05

Задание

Требования: реализуйте библиотеку со следующими структурами данных в persistent-вариантах:

• Массив (константное время доступа, переменная длинна)
• Двусвязный список
• Ассоциативный массив (на основе Hash-таблицы, либо бинарного дерева)
• Должен быть единый API для всех структур, желательно использовать естественный API для выбранной платформы

Дополнительные требования

• Обеспечить произвольную вложенность данных (по аналогии с динамическими языками), не отказываясь при этом полностью от типизации посредствомgeneric/template.
• Реализовать универсальныйundo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур)
• Реализовать более эффективное по скорости доступа представление структур данных, чем fat-node
• Расширить экономичное использование памяти на операцию преобразования одной структуры к другой (например, списка в массив)
• Реализовать поддержку транзакционной памяти STM (?atom VS ref. agent мб очередь операций с пуллом потоков VS actor)

Ссылки

• Задание (pdf)
• Задание (новое)
• Задание (старое)
• Persistent data structure в кожуре (java)
• Functional Data Structures in Scala (видосик 50 мин.)
• MIT youtube
• Habr 01 simple
• Сторонняя реализация java абстракций
• Вики

Инфа

Классы в java

Виды пресистентности

Как че вообще

Можно представить дерево в виде списка, и делать вставку за O(1). Обход дерева указан на рисунке ниже (красным)