66 lines
6.8 KiB
Markdown
66 lines
6.8 KiB
Markdown
# Yadro TATLIN Data Services - Задание
|
||
|
||
Устройство хранения данных типа лента (```Tape```) предназначено для последовательной записи и чтения
|
||
данных. Считывающая/записывающая магнитная головка неподвижна во время чтения и записи, а лента имеет возможность двигаться в обоих направлениях. Запись и чтение информации возможны в ячейку ленты, на которой в данный момент находится магнитная головка. Перемещения ленты – затратная по времени операция – лента не предназначена для произвольного доступа. Имеется входная лента длины _N_ (где _N_ – велико), содержащая элементы типа ```integer``` (2^32). Имеется выходная лента такой же длины. Необходимо записать в выходную ленту отсортированные по возрастанию элементы с входной ленты. Есть ограничение по использованию оперативной памяти – не более _M_ байт (_M_ может быть < _N_, т.е. загрузить все данные с ленты в оперативную память не получится). Для реализации алгоритма можно использовать разумное количество временных лент, т.е. лент, на которых можно хранить какую-то временную информацию, необходимую в процессе работы алгоритма.
|
||
|
||
Необходимо создать проект ```С++```, компилируемый в консольное приложение, которое реализует алгоритм сортировки данных с входной ленты на выходную. Необходимо сделать следующее:
|
||
|
||
- Определить интерфейс для работы с устройством типа лента.
|
||
- Написать класс, реализующий этот интерфейс и эмулирующий работу с лентой посредством обычного файла. Должно быть возможно сконфигурировать (без перекомпиляции – например, через внешний конфигурационный файл, который будет прочитан на старте приложения) задержки по записи/чтению элемента с ленты, перемотки ленты, и сдвига ленты на одну позицию.
|
||
- Файлы временных лент можно сохранять в директорию ```tmp```.
|
||
- Написать класс, реализующий алгоритм сортировки данных с входной ленты на выходную.
|
||
- Консольное приложение должно принимать на вход имя входного и выходного файлов и производить сортировку.
|
||
- Желательно написать юнит-тесты.
|
||
|
||
# Описание
|
||
|
||
Проект использует CMake для сборки. Некоторый функционал проекта несовместим с _Windows_ и _MacOS_ (получение используемой памяти, создание временных файлов и т. п.) Проект успешно собирался на _Linux_ _x86_64_ и _aarch64_. Документация реализована посредством этого __README__ файла, а также подробными комментариями в коде
|
||
|
||
Структура проекта:
|
||
- ```bin``` - Исходный код исполняемых файлов
|
||
- ```ftsort``` - Исходный код основной программы проекта
|
||
- ```include``` - Директория для заголовков
|
||
- ```tapelib``` - Директория для заголовков библиотеки ```tapelib```
|
||
- ```src``` - Исходный код библиотек
|
||
- ```tests``` - Исходный код unit-тестов
|
||
|
||
# Сборка
|
||
|
||
## Linux
|
||
1. Склонируйте данный репозиторий и перейдите в него
|
||
```
|
||
git clone https://git.obamna.ru/erius/yadro-task.git
|
||
cd yadro-task
|
||
```
|
||
2. Сгенерируйте файлы сборки CMake
|
||
```
|
||
cmake -S . -B build
|
||
```
|
||
3. Соберите проект с помощью CMake
|
||
```
|
||
cmake --build build
|
||
```
|
||
Список CMake целей, которые можно собрать:
|
||
- ```tapelib``` - Библиотека ```tapelib```, в которой определены структуры данных и алгоритм сортировки
|
||
- ```filetape_tests``` - Unit-тесты, проверяющие работоспособность класса ```FileTape```
|
||
- ```filetape_sort_tests``` - Unit-тесты, проверяющие корректность работы алгоритма сортировки ```FileTape```
|
||
- Unit-тесты можно запустить следующей командой:
|
||
```
|
||
ctest --test-dir build -V
|
||
```
|
||
- ```ftsort``` - Исполняемый файл ```ftsort```, производящий сортировку ```FileTape```
|
||
- Отсортировать ```input.txt``` в файл ```output.txt``` с максимально разрешенным числом ячеек в памяти программы _100_, и с задержкой операции чтения из ```FileTape``` в _1_ мс, можно следюущей командой:
|
||
```
|
||
./build/bin/ftsort input.txt output.txt -m 100 -r 1
|
||
```
|
||
- Получить подробную инструкцию для ```ftsort``` можно следующей командой:
|
||
```
|
||
./build/bin/ftsort --help
|
||
```
|
||
- ```generate_input``` - Исполняемый файл ```generate_input```, генерирующий файл для ```FileTape```, заполненный ячейками со случайными значениями
|
||
- Сгенерировать файл ```input.txt``` для ```FileTape```, состоящий из _1000_ ячеек со случайными значениями, можно следующей командой:
|
||
```
|
||
./build/tests/generate_input input.txt 1000
|
||
```
|
||
|
||
Сборка и работоспособность проекта не проверялись на _Windows_ и _MacOS_
|