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