Введение 3
Постановка задачи 5
1. Теоретическое обоснование темы 6
1.1. Проблема 6
1.2. Структура данных Декартово дерево 8
1.3. Операции с Декартовым деревом 11
1.4. Структура данных Декартово дерево по неявному ключу 14
1.5. Операции с Декартовым деревом по неявному ключу 16
2. Комплексный анализ алгоритмов 18
2.1. Асимптотический анализ 18
2.2. Асимптотический анализ времени работы алгоритмов 19
2.3. Асимптотический анализ расхода памяти алгоритмов 25
3. Разработка реализующей программы 27
3.1. Выбор языка программирования и среды разработки 27
3.2. Реализация структуры данных 29
3.3. Реализация основных операций со структурой 32
3.4. Реализация алгоритмов решения поставленных задач 35
4. Численный эксперимент 38
4.1. Входные и выходные данные эксперимента 38
4.2. Сравнительный анализ времени работы алгоритмов 39
4.3. Сравнительный анализ расхода памяти алгоритмов 42
Заключение 49
Список использованной литературы 51
Приложение
В течение долгого времени реляционные базы данных (БД) доминировали в индустрии программного обеспечения, предоставляя механизмы для хранения данных, работы с многопоточностью и транзакциями и в основном стандартные интерфейсы для интеграции с приложениями и генерации отчетности. Однако в последнее время возрасла популярность нового типа баз данных, известного как NoSQL, который стал альтернативой реляционным базам данных. Под NoSQL («не SQL» или «не только SQL») понимают ряд подходов, направленных на реализацию хранилищ баз данных, которые существенно отличаются от реляционных и имеют возможность линейно масштабироваться. В отличие от реляционной модели, данные в таких БД не структурированы (структура данных не регламентирована) и агрегированы (одна сущность не разбивается на несколько таблиц и максимально оптимизирована под нужды приложения).
Появление NoSQL баз данных связано с появлением больших объемов данных, для работы с которыми возникла необходимость в распределенных БД, работающих на кластерах. Для создания таких баз пришлось ввести новый набор свойств BASE: базовая доступность, гибкое состояние, согласованность в конечном счете.
Помимо различия в моделях данных, NoSQL СУБД сильно отличаются друг от друга и внутренним устройством. Для реализации хранилищ используются различные структуры данных: хеш-таблицы, деревья и др., которые делятся на ассоциативные («ключ-значение») и последовательные. Последовательные контейнеры хранят данные в памяти линейно, сохраняя относительные позиции элементов. Ассоциативные контейнеры не сохраняют порядок, в котором вставляются элементы, а вместо этого используют ключи, хранящиеся в элементе, или сам элемент в качестве ключа для достижения максимальной скорости вставки, выборки и удаления. Ассоциативные контейнеры являются наиболее популярными и используемыми в NoSQL базах данных.
Методы построения контейнеров данных «ключ-значение» можно разделить на две категории. Одна из групп методов подразумевает использование некоторого глобального упорядочения (числового или лексикографического). Ключи хранятся в отсортированном состоянии, а для поиска используется бинарный алгоритм. Контейнеры, полученные данным методом, называются отсортированными ассоциативными контейнерами. Примерами таких контейнеров являются различные деревья.
Одной из форм реализации дерева является Декартово дерево, - структура данных, аналогичная дереву, но с условием: значение в любом узле больше, чем значения его потомков. Эта структура имеет и другие названия, например, дерамида (в английской литературе treap), так как является объединением двоичного дерева и пирамиды. Ее модификация, декартово дерево по неявному ключу позволяет реализовать большое количество операций с массивом и подмассивами за логарифмическое время.
Постановка задачи
Поставленная задача состоит в разработке алгоритмов работы со структурой данных декартово дерево по неявному ключу, в реализации составленных алгоритмов, их тестировании, а также в реализации и тестировании алгоритмов, основанных на работе с другой структурой данных, в представлении результатов работы алгоритмов с последующим сравнительным анализом.
В целях рассмотрения заявленной темы на практике был составлен список задач. На примере их решения с использованием различных структур данных в дальнейшем будет проведен сравнительный анализ:
• поиск элемента на заданной позиции;
• перестановка элементов множества на заданном отрезке в обратном порядке;
• перемещение заданного отрезка в наборе данных после указанной позиции.
С использованием инструментов среды разработки Visunl Studio, а также синтаксиса языка C++ были реализованы основные операции, выполняемые над структурой данных декартово дерево по неявному ключу, а также алгоритмы решения поставленных задач.
В течение работы было реализовано поддержание в декартовом дереве информации числового типа разного объема, выполнение нескольких видов основных запросов на обработку, будь то в единственной вершине либо на отрезке, за логарифмическое время. Вкупе с элементарными свойствами декартового дерева и преимуществами его применения, рассмотренными при сравнительном теоретическом анализе и подтвержденными в ходе численного эксперимента, это предоставляет простор для использования его на практике в любой системе, где требуется хранить значительные объемы данных, и периодически запрашивать у этих данных какие-нибудь статистики.
В ходе анализа применения для работы с данными рассматриваемой структуры сравнительно с использованием более примитивной структурой было сделано заключение: проблема большого перерасхода ресурсов памяти (от 2 до 4 байт на узел для того, чтобы хранить высоту) вполне компенсируется высокой производительностью простого кода и эффективностью использования временного ресурса в контексте хранения, обработки больших объемов данных и сбору статистики по большому числу параметров. Так как эти деревья позволяют считать сумму/разницу, минимум/максимум, а также другие операции за время O(log n).
В процессе рассуждений о выгодах и убытках реализации методов можно отметить, что небольшой недостаток декартового дерева также заключается в том, что приоритеты Y практически не используются, кроме как при балансировки дерева. Такая трата памяти впустую может быть исправлена.
Можно выдвинуть гипотезу о том, чтобы вместо генерации значений равномерно распределенной случайной величины брать в качестве значений приоритетов реальную информацию. Тогда, умножив все Y на некоторое простое число Р и взяв по модулю 2Л64, можно доказать, что Y будут распределены случайным образом. Для того, что бы при необходимости узнать Y, нужно будет умножить на обратный элемент к Р по модулю 2Л64.
Однако такой метод чреват последствиями с точки зрения безопасности: если кто-то сможет найти и применить метод вычисления числа Р, то, генерируя новые вершины для формирования в зловредном порядке, он сможет нарушить сбалансированность дерева с серьезными последствиями для работы программы.
Существуют и другие подходы к оптимизации использования памяти, однако их рассмотрение требует отдельной научно-исследовательской работы.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
