persistent-data-structures 0.3.0

No project description provided

Persistent-Data-Structures

Курсовой проект по дисциплине "Современные методы программирования" - "Persistent data structures"

Разработчики:

• Карицкая Полина, 24225.1
• Пучков Дмитрий, 24225.1

---

Оглавление

• Persistent-Data-Structures
  • Разработчики:
  • Оглавление
  • Описание задания
  • Базовые требования
  • Дополнительные требования
  • Календарный план
  • Ожидаемое решение
  • Теоретическая часть
    • Персистентные структуры данных
    • Fat node
    • Path copying
    • Более эффективное по скорости доступа представление структур данных
  • API
  • Примеры использования
    • Массив (Persistent Array)
    • Список (Persistent Linked List)
    • Aссоциативный массив (Persistent Map)
  • Используемые источники

---

Описание задания

Реализовать библиотеку в Python со структурами данных в persistent-вариантах.

---

Базовые требования

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

---

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

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

---

Календарный план

Сроки	Этап работы	Разделение ответственностей
до 23.11.2024	- Создание каркаса проекта - Создание репозитория на GitHub	- Ответственный за настройку проекта и репозитория: Полина - Ответственный за организацию структуры файлов и начальную настройку CI/CD: Дмитрий
до 07.12.2024	Реализация базовой функциональности: - Массив (Persistent Array) - Двусвязный список (Persistent Linked List) - Ассоциативный массив (Persistent Map) - Создание единого API	- Ответственный за реализацию Persistent Array: совместно - Ответственный за реализацию Persistent Linked List: Полина - Ответственный за реализацию Persistent Map: Дмитрий - Ответственный за создание API: совместно
до 21.12.2024	Реализация дополнительной функциональности: - Реализовать более эффективное по скорости доступа представление структур данных, чем fat-node - Обеспечить произвольную вложенность данных (по аналогии с динамическими языками) - Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности	- Ответственный за улучшение представления структур данных: совместно - Ответственный за реализацию вложенности данных: совместно - Ответственный за разработку механизма undo-redo: совместно

---

Ожидаемое решение

Ожидаемое решение состоит в разработке библиотеки, которая будет поддерживать следующие структуры данных:

1. Persistent Array - массив с возможностью добавления элементов без изменения предыдущих состояний. Операции должны поддерживать константное время доступа.

2. Persistent Linked List - двусвязный список с поддержкой добавления и удаления элементов, при этом сохраняется возможность обратиться к предыдущим состояниям списка.

3. Persistent Map - ассоциативный массив, реализованный на основе хеш-таблицы или бинарного дерева поиска. Это будет позволять эффективно работать с данными, при этом поддерживать возможность обращения к предыдущим версиям данных.

4. Оптимизация доступа к данным - предложим более эффективное представление данных для ускорения операций доступа по сравнению с fat-node.

5. Типизация данных - обеспечим произвольную вложенность данных, при этом не отказываясь от строгой типизации через generic или template.

6. Undo/Redo Механизм - реализуем механизм для всех структур данных, который позволит отменять и повторять изменения, причем для вложенных структур будет поддерживаться каскадность.

Каждая из структур данных будет поддерживать все основные операции: вставку, удаление, обновление, а также предоставлять возможность работы с предыдущими версиями данных через персистентность данных. Вся библиотека будет иметь единый API для работы с данными и их модификацией. Также будет обеспечена возможность взаимодействия с данными в виде вложенных структур.

---

Теоретическая часть

Персистентные структуры данных

Персистентные структуры данных сохраняют предыдущие версии при изменении. Структура называется fully persistent, если все её версии доступны для изменений. В partially persistent структурах можно изменять только последнюю версию, но доступ к предыдущим возможен. Эти структуры часто реализуются с использованием алгоритмов, таких как path copying, node copying и fat node, а также с применением бинарных деревьев поиска и красно-черных деревьев.

Персистентные структуры используются в вычислительной геометрии, объектно-ориентированном программировании, текстовых редакторах, симуляциях и системах контроля версий, таких как Git.

Fat node

Fat node используется для создания персистентных структур данных, где изменения сохраняются только в измененных узлах дерева, а сами узлы могут расширяться, чтобы хранить все версии. Основной принцип заключается в том, чтобы хранить обновления и версии данных в списках, что позволяет эффективно отслеживать изменения в структуре.

Преимущества:

• Экономия памяти, так как изменяются только те части данных, которые действительно изменились;
• Быстрая работа с историей изменений.

Недостатки:

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

Можно посмотреть визуализацию метода fat node.

Path copying

Метод path copying используется для создания персистентных структур данных, где при изменении узла создается его копия, и нужно пройти по всем узлам от измененного до корня, чтобы обновить ссылки на новый узел. Этот метод упрощает доступ к данным, так как для поиска нужной версии достаточно пройти путь от корня.

Преимущества:

• Быстрый доступ к данным;
• Простота в реализации.

Недостатки:

• Большие затраты на память, поскольку изменения могут потребовать копирования всей структуры;
• Могут возникать дополнительные накладные расходы при частых модификациях.

Метод path copying также используется для создания полностью персистентных структур данных.

На иллюстрации продеминстрирован пример использования path copying на бинарном дереве поиска. При внесении изменения создается новый корень, при этом старый корень сохраняется для дальнейшего использования (он показан темно-серым цветом). Заметим также, что старое и новое деревья частично делят общую структуру.

Более эффективное по скорости доступа представление структур данных

Поскольку одно из требований — использование более эффективного подхода по сравнению с методом fat-node, в проекте будет применяться подход ...

---

API

Для работы с персистентными структурами данных используйте следующий API:

Создание объекта:

obj = [PersistentDataStructure]([args])

Обращение к элементу текщей версии:

obj[index]

Обращение по индексу к элементу произвольной версии для массива и списка:

obj.get(version, index)

Обращение по ключу к элементу произвольной версии для мапы:

obj.get(version, key)

Добавление элемента в конец в новую версию для массива и списка:

obj.add(element)

Добавление элемента в начало в новую версию списка:

obj.add_first(element)

Удаление элемента по индексу для массива и списка в новой версии и возвращение элемента:

obj.pop(index)

Удаление элемента по ключу для мапы в новой версии и возвращение элемента:

obj.pop(key)

Обновление элемента по индексу в новой версии массива или списка:

obj[index] = element

Обновление элемента по ключу в новой версии мапы:

obj['key'] = element

Вставка элемента в новую версию по указанному индексу для массива или списка:

obj.insert(index, element)

Удаление элемента в новой версии массива или списка по индексу:

obj.remove(index)

Удаление элемента в новой версии мапы по ключу:

obj.remove(key)

Получение размера массива или списка для текущей версии:

obj.get_size()

Проверка на пустоту для массива или списка:

obj.check_is_empty()

Возвращение состояние объекта для указанной версии:

obj.get_version(version)

Обновление текущей версии объекта до указанной:

obj.update_version(version)

Получение элемента текущей версии массива или списка по указанному индексу.

obj.__getitem__(index)

Получение элемента текущей версии мапы по указанному ключу.

obj.__getitem__(key)

Обновление или создание элемента по указанному индексу в новой версии для массива или списка.

obj.__setitem__(index)

Обновление или создание элемента по указанному ключу в новой версии для мапы.

obj.__setitem__(key)

Очистка объекта, при этом создается новая версия.

obj.clear()

---

Примеры использования

Массив (Persistent Array)

Примеры использования:

    >>> array = PersistentArray(size=5, default_value=0)  # Создаем массив из 5 элементов, заполненных нулями
    >>> array[0]  # Получаем значение первого элемента
    0
    >>> array[0] = 10  # Обновляем значение первого элемента в новой версии
    >>> array[0]  # Проверяем значение первого элемента в текущей версии
    10
    >>> array.add(20)  # Добавляем новый элемент в конец массива в новую версию
    >>> array[5]  # Проверяем значение нового элемента
    20
    >>> array.pop(1)  # Удаляем элемент с индексом 1 в новой версии
    0
    >>> array.insert(2, 15)  # Вставляем значение 15 на индекс 2 в новой версии
    >>> array[2]  # Проверяем вставленное значение
    15
    >>> array.remove(3)  # Удаляем элемент с индексом 3
    >>> array.get(1, 0)  # Получаем значение элемента с индексом 0 из версии 1
    0
    >>> array.clear()  # Очищаем массив, создавая новую версию
    >>> array.get_size()  # Проверяем размер массива в текущей версии
    0
    >>> array.check_is_empty()  # Проверяем, пуст ли массив
    True
    >>> array.get(0, 2)  # Пытаемся получить элемент из очищенного массива в версии 0
    Traceback (most recent call last):
        ...
    ValueError: Invalid index

Список (Persistent Linked List)

Примеры использования:

    >>> linked_list = PersistentLinkedList([1, 2, 3])  # Создаем список с начальными элементами
    >>> linked_list.add(4)  # Добавляем элемент в конец списка
    >>> linked_list[3]  # Получаем элемент по индексу в текущей версии
    4
    >>> linked_list.add_first(0)  # Добавляем элемент в начало списка
    >>> linked_list[0]  # Получаем элемент в текущей версии по индексу
    0
    >>> linked_list.insert(2, 1.5)  # Вставляем элемент на индекс 2
    >>> linked_list[2]  # Проверяем значение вставленного элемента
    1.5
    >>> linked_list.get(1, 2)  # Получаем элемент из версии 1 по индексу 2
    3
    >>> linked_list.pop(1)  # Удаляем элемент по индексу 1 в новой версии
    2
    >>> linked_list.remove(3)  # Удаляем элемент
    >>> linked_list.clear()  # Очищаем список, создавая новую версию
    >>> linked_list.get(0, 2)  # Пытаемся получить элемент из очищенной версии
    Traceback (most recent call last):
        ...
    IndexError: Index out of range
    >>> linked_list.update_version(2)  # Возвращаемся к версии 2
    >>> linked_list[0]  # Получаем элемент по индексу в версии 2
    1
    >>> linked_list.get_size()  # Получаем размер списка в текущей версии
    4
    >>> linked_list.check_is_empty()  # Проверяем, пуст ли список в текущей версии
    False

Aссоциативный массив (Persistent Map)

Примеры использования:

    >>> map = PersistentMap({'foo': 'bar'}) # Создаем пустой ассоциативный массив
    >>> map['key'] = 'value' # Добавляем элемент
    >>> map['key'] = 'value2' # Изменяем элемент в следующей версии
    >>> map['key'] # Получаем элемент последней версии
    'value2'
    >>> map.get(1, 'key')
    {'key': 'value'}
    >>> map.remove('key') # Удаляем элемент в новой версии
    >>> map.clear() # Очищаем ассоциативный массив в новой версии
    >>> map.get(0, 'key') # Пытаемся получить элемент отсутствующий в переданной версии
    Traceback (most recent call last):
        ...
    KeyError: Key "key" does not exist

---

Используемые источники

1. Milan Straka, "Functional Data Structures and Algorithms", Computer Science Institute of Charles University, Prague 2013

2. Крис Окасаки, "Чисто функциональные структуры данных", 2018

3. Статья на Geeks for geeks "Persistent data structures"

4. Несколько статей по персистентным векторам:

   • Understanding Clojure's Persistent Vectors, pt. 1
   • Understanding Clojure's Persistent Vectors, pt. 2
   • Understanding Clojure's Persistent Vectors, pt. 3

5. Driscoll J. R. et al. Making data structures persistent //Proceedings of the eighteenth annual ACM symposium on Theory of computing. – 1986. – С. 109-121.

6. Серия видео-лекций по персистентным структурам данных:

   • "Visualizing Persistent Data Structures" by Dann Toliver
   • Persistent Data Structures, MIT