Название семестровой работы

Краткое описание семестрового проекта. Следует отразить информацию по следующим пунктам:

• Какая структура данных реализуется?
• Что она из себя представляет (сбалансированное дерево, линейный список и пр.)?
• Где и как она используется (приложения)?
• Какие операции над ней можно выполнять (поиск, удаление, добавление, вставка и пр.)?
• Какова теоретическая сложность операций (поиск за O(log(n)), вставка за O(n^2) и т.д.)?
• Какая-то другая справочная информация о проекте.

Команда "название команды"

Группа: 00-000

Заполните таблицу с указанием вклада каждого из участников в проект.

Примечание. Преподаватель может определить вклад любого из участников команды по истории коммитов.

Фамилия Имя	Вклад (%)	Прозвище
Участник №1	50	босс
Участник №2	40	потрошитель памяти
Участник №3	10	самозванец

Девиз команды

Наши цели ясны. Задачи определены. За работу, товарищи!

Структура проекта

Описание основных частей семестрового проекта.

Пример. Проект состоит из следующих частей:

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
• examples - примеры работы со структурой данных;
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования

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

Пример. Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.7.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 8 ГБ.
5. Свободное дисковое пространство объемом ~ 2 ГБ (для входного набора данных).

Сборка и запуск

Инструкция по сборке проекта, генерации тестовых данных, запуска контрольных тестов и примеров работы.

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

Здесь можно оставить ссылку с видео-инструкцией по сборке и запуску проекта.

Пример (Windows)

Сборка проекта

Опишите процесс сборки проекта.

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности среды разработки):

git clone https://github.com/Algorithms-and-Data-Structures-2022/semester-work-template.git

Сборка и запуск проекта осуществляется через среду разработки.

Генерация тестовых данных

Опишите формат хранения (JSON, XML, CSV, YAML и т.д.) и процесс генерации тестовых данных.

Разрешается использовать собственный формат хранения данных.

Пример. Генерация тестового набора данных

Формат данных: comma-seperated values (CSV).

Инструкции по генерации:

# переход в папку генерации набора данных
cd dataset

# запуск Python-скрипта
python generate_csv_bench_dataset.py --samples 1000 <output> [args ...]

• --samples - количество генерируемых элементов;
• <output> - выходной файл и т.д.

Тестовые данные представлены в CSV формате (см. dataset/data/dataset-example.csv):

id, full_name
0, "Ramil Safin"
1, "Bulat Abbyasov"
...

Примечание. Для удобства запуска контрольных тестов рекомендуется организовывать данные в директориях, например:

dataset/data/
  add/
    01/
      100.csv
      ...
      5000000.csv
    02/ ...
    03/ ...
    ...
    10/ ...
  search/
    01/
      100.csv
      ...
      5000000.csv
    ...
    10/ ...
  ...

По названию директории /dataset/data/add можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Опишите, как запустить контрольные тесты, что они из себя представляют, какие метрики замеряют (время работы, потребление памяти и пр.).

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

Примечание. Во избежание "захламления" репозитория большим объёмом данных рекомендуется указать ссылку на архив с набором данных, который при необходимости можно скачать по ссылке.

Список контрольных тестов

Название	Описание	Метрики
search_benchmark	поиск элементов	время
add_benchmark	добавление элементов в структуру данных	время, память
...	...	...

Примеры запуска

./benchmark <input> <output> --trials 50

• <input> - входной файл с набором данных в формате CSV;
• <output> - выходной файл с результатами контрольного теста;
• --trials - количество прогонов на наборе данных и т.д.

Добавление 10000 случайных элементов в структуру данных (повторить операцию 50 раз и вычислить среднее время работы и потребляемую память):

./add_benchmark.exe ../dataset/data/add/10000.csv metrics.txt --trials 50

где <input> = ../dataset/data/add/10000.csv и <output> = metrics.txt.

Источники

Список использованных при реализации структуры данных источников.

Это не плагиат, это уважение чужого труда и помощь своим сокурсникам более подробно разобраться в теме.