В данной работе приводится сравнение указанных выше структур данных. Каждая из них имеет свои преимущества и недостатки, которые я покажу на практике, протестировав структуры.

• Sorted array
• Sorted list
• Sorted expanded list
• Тестирование
• Запуск программы
• Входные и выходные данные

Для каждой из структур данных реализованы:

1. Операция вставки - add
2. Операция удаления по значению - erase
3. Операция поиска по значению - search_index
4. Операция обращения по индексу - operator[]
5. Операция получения минимального и максимального элементов - min/max
6. Операция вывода на экран текущего состояния структуры - print

Примечание:
Обращение по индексу, как и получение крайних элементов дают константные данные, так как иначе происходит нарушение структуры данных. Для изменения структуры данных используются только операции add и erase.

Структура данных представляет собой непрерывную, динамически расширяющуюся область памяти, которая в любом состоянии структуры заполнена отсортированными данными. Пользователь должен сам задать функцию-компаратор для данных, если он не сделал этого, по умолчанию используется std::less.

void add(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Так как структура данных изначально отсортирована, то применяется алгоритм бинарного поиска для определения места вставки нового элемента. Бинарный поиск.
Если массив заполнен полностью, происходит расширение массива (коэффициент амортизации задается пользователем, если тот не указал - берется 1,5).
Нужная часть массива сдвигается вправо и на позицию вставляется исходный элемент.
Сложность в лучшем случае - О(1), в среднем - O(n), в худшем - O(n)

Доказательство сложности

В среднем, нужно бинарным поиском найти место вставки за O(log2(n)), затем вставить элемент, что вызовет сдвиг всех элементов после него, то есть O(n). Результирующая сложность - O(n)

bool erase(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Так как структура данных изначально отсортирована, то применяется алгоритм бинарного поиска для определения места нахождения элемента. Бинарный поиск. Если такого элемента нет в массиве - функция вернет false. Если он есть - производится сдвиг нужной части массива и вернется true.
Сложность в лучшем случае - О(1), в среднем - O(n), в худшем - O(n)

Доказательство сложности

В среднем, нужно бинарным поиском найти элемент за O(log2(n)), затем удалить элемент, что вызовет сдвиг всех элементов после него, то есть O(n). Результирующая сложность - O(n).

long int search_index(T _data) // сигнатура функции

Применяется алгоритм бинарного поиска, если элемент нашелся в массиве, возвращается его индекс, если такого элемента нет возвращается -1.
Сложность в лучшем случае - O(1), в среднем - О(log2(n)), в худшем - O(log2(n))

const T& operator[](size_t index) // сигнатура функции

Возвращает константную ссылку на элемент массива по индексу, если индекс слишком велик, бросает исключение std::invalid_argument("Too big to be true")
Сложность - O(1).

const T& get_min()

Возвращается первый элемент массива. Сложность - O(1).

const T& get_max()

Возвращается последний элемент массива. Сложность - O(1).

Функция вывода структуры данных. В нее передается по ссылке объект stringstream, куда и записывается вывод. Данные выводятся внутри [ ] и разделены запятой. Пример - [ 1, 2, 3, 4, 5]

Основными преимуществами отсортированного массива являются:

1. Быстрый поиск элемента в массиве
2. Чрезвычайно маленький объем дополнительной памяти
3. Быстрый доступ к элементу массива

Недостатки:

1. Необходимость иногда производить дорогостоящую операцию перевыделения памяти.
2. Возможность возникновения ситуации, когда выделился огромный объем неиспользуемой памяти.
3. Возможность ситуации, когда непрерывная область памяти становится слишком большой для хранения.

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

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

Структура данных представляет собой множество связанных между собой блоков, в каждом из которых хранится объект данных, указатель на следующий блок и указатель на предыдущий блок. Данные отсортированы в порядке следования блоков.
Пользователь должен сам задать функцию-компаратор для данных, если он не сделал этого, по умолчанию используется std::less.

void add(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Так как структура данных изначально отсортирована, вычисляется разность между начальным блоком и элементом и конечным блоком и элементом. Производится проход по списку в прямом или обратном направлении в зависимостри от разницы, в поисках места вставки элемента. Когда место найдено конструируем новый блок и переопределяем указатели. Сложность в лучшем случае - О(1), в среднем - O(n), в худшем - O(n)

В лучшем случае элемент вставится на первое место за константу.
В среднем случае нам нужно сначала обнаружить элемент, после которого вставляется новый, что происходит за O(n). Результирующая сложность - O(n). Аналогично для сложности в худшем случае.

bool erase(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Так как структура данных изначально отсортирована вычисляется разность между начальным блоком и элементом и конечным блоком и элементом. Производится проход по списку в прямом или обратном направлении в зависимостри от разницы, в поисках нужного блока. Когда место найдено удаляем блок и переопределяем указатели.
Сложность в лучшем случае - О(1), в среднем - O(k), в худшем - O(n)

Доказательство сложности

В лучшем случае удалим первый элемент. В среднем найдем элемент, который нужно удалить за O(n), затем удалим за константу. Результирующая - O(n).

const bool search(T _data) // сигнатура функции

Вычисляется разность между начальным блоком и элементом и конечным блоком и элементом. Производится проход по списку в прямом или обратном направлении в зависимостри от разницы. Если элемент найден - возвращается true, в ином случае - false
Сложность в лучшем случае - O(1), в среднем - О(k), в худшем - O(n)

const T& operator[](size_t index) // сигнатура функции

Производится проход в прямом или обратном направлении по аналогии с предыдущими функциями. Если индекс больше длины списка бросается исключение std::invalid_argument("Too big to be true")
Сложность - O(n).

const T& get_min()

Возвращается первый элемент списка. Сложность - O(1).

const T& get_max()

Возвращается последний элемент списка. Сложность - O(1).

Функция вывода структуры данных. В нее передается по ссылке объект stringstream, куда и записывается вывод. Данные выводятся по блокам и разделены ->. Пример - 1 -> 2 -> 3 -> 4 -> 5

Основными преимуществами отсортированного списка являются:

1. Кусочное хранение данных
2. Быстрая операция добавления и удаления

Недостатки:

1. Большой объем дополнительной памяти - O(n).
2. Долгий поиск элементов.

Структура данных может использоваться, например, для буферизации. Когда приходят блоки видео-файла их удобно хранить в данной структуре, так как память не переаллоцируется для очередного блока данных.

Структура данных представляет собой множество связанных между собой блоков, в каждом из которых хранится массив данных, указатель на следующий блок и указатель на предыдущий блок. Данные отсортированы в порядке следования блоков.
Пользователь должен сам задать функцию-компаратор для данных, если он не сделал этого, по умолчанию используется std::less.

void add(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Проходом по списку вычисляется массив, в который нужно произвести вставку. Если в массиве есть место для вставки, то производится вставка в массив по аналогии с обычным отсортированным массивом. Если же места нет, то элемент сравнивается с первым элементом массива. Если первый больше, то создается новый блок, который ставится перед найденным и куда помещается исходный элемент. Если меньше, то создается новый блок, который ставится после найденного и куда помещается последний элемент найденного массива. Далее происходит вставка в найденный массив. Сложность в лучшем случае - О(1), в среднем - O(n/k + k), в худшем - O(n/k + k), где k - мощность каждого массива

Доказательство сложности

В лучшем случае будет пустой массив, в который мы вставим элемент.
В среднем случае нам нужно сначала обнаружить массив, в который производится вставка. Это делается за O(n/k), т.к. таково количество подмассивов. Дальше ищется место вставки бинарным поиском - O(log2(k)), затем происходит вставка в массив за O(k). Результирующая сложность - O(n/k + k). Аналогично для сложности в худшем случае.

bool erase(T _data) // сигнатура функции

Функция принимает объект пользовательского типа данных. Находится массив, в котором может содержаться элемент. производится удаление из отсортированного массива. Если элемента там нет, возвращается false, в ином случае возвращается true. Если массив стал пустым, блок удаляется.
Сложность в лучшем случае - О(1), в среднем - O(n/k + k), в худшем - O(n/k + k)

Доказательство сложности

В лучшем случае будет пустой массив c одним элементом, из которого мы удалим элемент.
В среднем случае нам нужно сначала обнаружить массив, из которого производится удаление. Это делается за O(n/k), т.к. таково количество подмассивов. Дальше ищется элемент бинарным поиском - O(log2(k)), затем происходит удаление из массива за O(k). Результирующая сложность - O(n/k + k). Аналогично для сложности в худшем случае.

const bool search(T _data) // сигнатура функции

Находится массив, в котором может содержаться элемент. производится поиск в отсортированном массиве. Если элемент найден - возвращается true, в ином случае - false
Сложность в лучшем случае - O(1), в среднем - О(n/k + log2(k)), в худшем - O(n/k + log2(k)) ` Доказательство сложности

В лучшем случае будет первое взятое бинарным поиском число окажется искомым.
В среднем случае нам нужно сначала обнаружить массив, в которм ищем элемент. Это делается за O(n/k), т.к. таково количество подмассивов. Дальше ищется элемент бинарным поиском - O(log2(k)). Результирующая сложность - O(n/k + log2(k))

const T& operator[](size_t index) // сигнатура функции

Находится массив, содержащий этот индекс(индекс считается общим для всех массивов). Если индекс больше длины списка бросается исключение std::invalid_argument("Too big to be true")
Сложность - O(n/k)

const T& get_min()

Возвращается первый элемент первого массива в списке. Сложность - O(1).

const T& get_max()

Возвращается последний элемент последнего массива в списке. Сложность - O(1).

Функция вывода структуры данных. В нее передается по ссылке объект stringstream, куда и записывается вывод. Композиция предыдущих. Пример - [1, 2] -> [2] -> [3] -> [4, 5] -> [6]

По сути это объединение первой и второй структуры. Соответственно, преимущества и недостатки будут относительно других структур.
Преимущества:

1. Относительно быстрое добавление и удаление.
2. Кусочное хранение данных.
3. Поиск быстрее, чем в обычном списке, но медленнее, чем в массиве.

Недостатки:

1. Большой объем дополнительной памяти - O(n/k).

Данная структура данных лучше других подходит для раздельного логгирования множества устройств и сохранения логов.

Тесты функциональности приведены в папке tests в файле structures.cpp
Они все в одном файле, используется библиотека catch для их удобного написания. Чтобы запустить тесты нужно ввести команду make array_tests.

Для начала на примере теста подтвердим сложности реализованных алгоритмов. Для этого генерируется 10000 различных данных(данные - последовательности команд). На основе этого путем реализации линейной регрессии вычисляется примерный вид выходной функции. Ниже представлены графики тестирования для всех функций всех структур:

1. Массив 
2. Список
3. Развернутый список

Как можно заметить, сложность была доказана верно, т.к. график выходной функции имеет линейный вид(синий).

Следующий этап тестирования заключается в разработке сценариев для структур данных. Для псевдослучайной последовательности комманд тесты были приведены выше, так что специализированных сценариев будет немного.

В трех кейсах просиходят проверки основных фунции каждой структуры. Одна функция - одна секция. Для добавления: структура заполняется данными, далее сравниваются элементы структуры с значениями, которые должны быть на соответствующих местах. Для удаления сначала структуры заполняются, затем происходит удаление из структуры и сравниваются очередные элементы структуры с элементами, которые по логике программы должны быть на соответствующих местах. Для поиска структура заполняется данными, затем проверяется существование элементов в структуре и несуществование других элементов соответственно. Аналогично проверяются ф-и get_min и get_max. Для ф-й print сравнивается строка, которая должна быть с возвращаемым значением stringstream::str().

Далее проведем специальные тестовые сценарии. В общем случае предыдущие графики показывают, что массив работает намного быстрее списков. Были подобраны данные, которые делают массив намного медленнее, а списки наоборот. Будем подавать 4 блока данных на вставку в структуры, причем внутри кажого блока данные распределены равномерно, а данные каждого следующего блока меньше, чем данные предыдущего. Таким образом при вставке в списки итераций прохода по списку будет минимум, и они будут работать быстрее, а массив наоборот, будет происходить сдвиг каждого следующего блока при вставке очередного.
Ниже представлены графики. На первом из них массив отображается зеленой линией, список - синей, развернутый список - красной.

1. Общий
2. Массив
3. Список
4. Развернутый список

Как можно заметить, прямая массива растет намного быстрее развернутого списка и немного быстрее обычного.

Теперь покажем, на каких данных можно "сломать" массив при удалении, а заодно покажем более ярко выраженное превосходство списков в этом случае на добавлении. Для этого будем добавлять каждый новый элемент так, чтобы он был меньше предыдущего, а удалять наоборот, каждый раз самый маленький. Вот, что получилось:

1. Общий
2. Массив
3. Список
4. Развернутый список

Видим логичную картину - массив работает намного хуже, т.к. при каждой вставке или удалении нужно сдвигать все остальные элементы. Списки, соответственно, просто создают элемент в начале и переприсваивают указатели, работают константно, как и видно по графикам.

В программе есть несколько исполняемых файлов. Если пользователь хочет запустить тесты общего вида, он должен запустить скрипт test.sh, передав первым параметром количество данных, вторым - название тестируемой структуры. Исполняемый файл test_strectures - это основная программа. Первым параметром она принимает на вход имя файла с входными данными, вторым - с выходными.
Кроме того, в папке stress_tests есть два файла: первый - main_tests.py, параметром которому передается количество входных данных, файл, куда записать сгенерированные данные и структура данных, которую тестируем. И файл read_tests.py, которыя считывает выходные данные основной программы, а затем строит по ним соответствующие графики и выводит коэффициенты линейных завиисимостей.

Входные данные поступают в следующем формате:

• Первая строка файла - название структуры(array, list, elist)
• Количество производимых операций
• Операции - "min" "max" "push k n" "pop k" "search k" "print"(одна из них)

Выходные данные выходят в следующем формате:

• Операции - {} + "time"