Курсовой проект по дисциплине "Современные методы программирования" - "Persistent data structures"
- Карицкая Полина, 24225.1
- Пучков Дмитрий, 24225.1
- Persistent-Data-Structures
Реализовать библиотеку в Python со структурами данных в persistent-вариантах.
- Массив (константное время доступа, переменная длина)
- Двусвязный список
- Ассоциативный массив (на основе Hash-таблицы, либо бинарного дерева)
- Реализовать более эффективное по памяти представление структур данных;
- Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур);
- Реализовать поддержку транзакционной памяти (STM).
| Сроки | Этап работы | Разделение ответственностей |
|---|---|---|
| до 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 | Реализация дополнительной функциональности: - Реализовать более эффективное по памяти представление структур данных - Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур) - Реализовать поддержку транзакционной памяти (STM) |
- Ответственный за улучшение эффективности по памяти: Полина - Ответственный за реализацию undo-redo механизма: Дмитрий - Ответственный за поддержку транзакционной памяти (STM): совместно |
Ожидаемое решение состоит в разработке библиотеки, которая будет поддерживать следующие структуры данных:
-
Persistent Array - массив с возможностью добавления элементов без изменения предыдущих состояний. Операции должны поддерживать константное время доступа.
-
Persistent Linked List - двусвязный список с поддержкой добавления и удаления элементов, при этом сохраняется возможность обратиться к предыдущим состояниям списка.
-
Persistent Map - ассоциативный массив, реализованный на основе хеш-таблицы или бинарного дерева поиска. Это будет позволять эффективно работать с данными, при этом поддерживать возможность обращения к предыдущим версиям данных.
-
Оптимизация по памяти - предложим более эффективное по памяти представление данных операций доступа по сравнению с fat-node.
-
Undo/Redo Механизм - реализуем механизм для всех структур данных, который позволит отменять и повторять изменения, причем для вложенных структур будет поддерживаться каскадность.
-
Транзакционная память (STM) - реализуем механизм транзакционной памяти для обеспечения атомарности операций с данными.
Каждая из структур данных будет поддерживать все основные операции: вставку, удаление, обновление, а также предоставлять возможность работы с предыдущими версиями данных через персистентность данных. Вся библиотека будет иметь единый API для работы с данными и их модификацией. Также будет обеспечена возможность взаимодействия с данными в виде вложенных структур.
Персистентные структуры данных сохраняют предыдущие версии при изменении. Структура называется fully persistent, если все её версии доступны для изменений. В partially persistent структурах можно изменять только последнюю версию, но доступ к предыдущим возможен. Эти структуры часто реализуются с использованием алгоритмов, таких как path copying, node copying и fat node, а также с применением бинарных деревьев поиска и красно-черных деревьев.
Персистентные структуры используются в вычислительной геометрии, объектно-ориентированном программировании, текстовых редакторах, симуляциях и системах контроля версий, таких как Git.
Fat node используется для создания персистентных структур данных, где изменения сохраняются только в измененных узлах дерева, а сами узлы могут расширяться, чтобы хранить все версии. Основной принцип заключается в том, чтобы хранить обновления и версии данных в списках, что позволяет эффективно отслеживать изменения в структуре.
Преимущества:
- Экономия памяти, так как изменяются только те части данных, которые действительно изменились;
- Быстрая работа с историей изменений.
Недостатки:
- Может быть менее эффективен для структур с частыми изменениями, так как увеличение размера узлов приводит к дополнительным затратам на память.
Можно посмотреть визуализацию метода fat node.
Метод path copying используется для создания персистентных структур данных, где при изменении узла создается его копия, и нужно пройти по всем узлам от измененного до корня, чтобы обновить ссылки на новый узел. Этот метод упрощает доступ к данным, так как для поиска нужной версии достаточно пройти путь от корня.
Преимущества:
- Быстрый доступ к данным;
- Простота в реализации.
Недостатки:
- Большие затраты на память, поскольку изменения могут потребовать копирования всей структуры;
- Могут возникать дополнительные накладные расходы при частых модификациях.
Метод path copying также используется для создания полностью персистентных структур данных.
На иллюстрации продеминстрирован пример использования path copying на бинарном дереве поиска. При внесении изменения создается новый корень, при этом старый корень сохраняется для дальнейшего использования (он показан темно-серым цветом). Заметим также, что старое и новое деревья частично делят общую структуру.
Поскольку одно из требований — использование более эффективного подхода по сравнению с методом fat-node, в проекте будет применяться подход с использованием B-деревьев.
Для работы с персистентными структурами данных используйте следующий API:
Создание объекта:
from persistent_data_structure import PersistentLinkedList, PersistentArray, PersistentMap
lst = PersistentLinkedList()
arr = PersistentLinkedList()
dct = PersistentMap()Обращение к элементу текщей версии:
lst[index]
arr[index]
dct[key]Обращение по индексу к элементу произвольной версии для массива и списка:
arr.get(version, index)
lst.get(version, index)Обращение по ключу к элементу произвольной версии для мапы:
dct.get(version, key)Добавление элемента в конец в новую версию для массива и списка:
arr.add(element)
lst.add(element)Добавление элемента в начало в новую версию списка:
lst.add_first(element)Удаление элемента по индексу для массива и списка в новой версии и возвращение элемента:
arr.pop(index)
lst.pop(index)Удаление элемента по ключу для мапы в новой версии и возвращение элемента:
dct.pop(key)Обновление элемента по индексу в новой версии массива или списка:
arr[index] = element
lst[index] = elementОбновление элемента по ключу в новой версии мапы:
dct['key'] = elementВставка элемента в новую версию по указанному индексу для массива или списка:
arr.insert(index, element)
lst.insert(index, element)Удаление элемента в новой версии массива или списка по индексу:
arr.remove(index)
lst.remove(index)Удаление элемента в новой версии мапы по ключу:
dct.remove(key)Получение размера массива или списка для текущей версии:
arr.get_size()
lst.get_size()Проверка на пустоту для массива или списка:
arr.check_is_empty()
lst.check_is_empty()Возвращение состояние объекта для указанной версии:
arr.get_version(version)
lst.get_version(version)
dct.get_version(version)Обновление текущей версии объекта до указанной:
arr.update_version(version)
lst.update_version(version)
dct.update_version(version)Получение элемента текущей версии массива или списка по указанному индексу.
arr.__getitem__(index)
lst.__getitem__(index)Получение элемента текущей версии мапы по указанному ключу.
dct.__getitem__(key)Обновление или создание элемента по указанному индексу в новой версии для массива или списка.
arr.__setitem__(index)
lst.__setitem__(index)Обновление или создание элемента по указанному ключу в новой версии для мапы.
dct.__setitem__(key)Очистка объекта, при этом создается новая версия.
arr.clear()
lst.clear()
dct.clear()Примеры использования:
>>> 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
Примеры использования:
>>> 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
Примеры использования:
>>> 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
-
Milan Straka, "Functional Data Structures and Algorithms", Computer Science Institute of Charles University, Prague 2013
-
Крис Окасаки, "Чисто функциональные структуры данных", 2018
-
Статья на Geeks for geeks "Persistent data structures"
-
Несколько статей по персистентным векторам:
-
Driscoll J. R. et al. Making data structures persistent //Proceedings of the eighteenth annual ACM symposium on Theory of computing. – 1986. – С. 109-121.
-
Серия видео-лекций по персистентным структурам данных: