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

Измените status badge сверху для отображения статуса сборки вашего проекта.

Actions > CMake > ... > Create status badge

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

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

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

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

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

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

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

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

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

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

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

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

Требования (Prerequisites)

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

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

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

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

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

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

Пример (Windows)

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

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

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

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

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-template

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

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

Опишите формат хранения (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)

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

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

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

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

Название	Описание	Метрики
random_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.

Примечание. Файл с метриками не обязателен, можете выводить данные в стандартный поток вывода (т.е. консоль).

Источники

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

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