cpp_tape_sorter_2023

Симулятор сортировки данных на большой магнитной ленте (/dev/tape), которая не поместится целиком в ОЗУ

Синтаксис команды:

./tape-sorter ./input.tape.txt ./output.tape.txt

Если входной файл содержимого ленты *.tape.txt не существует, то он будет автоматически заполнен случайными числами

В выходной файл алгоритмом записываются числа с входного, отсортированные по возрастанию

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

./tape-sorter-config/tape-sorter-config.ini

Если конфигурационный файл *.ini не существует, то он тоже будет автоматически заполнен

Сборка

# устанавливаем CMake и зависимости: GoogleTest, Boost:
sudo apt install cmake libgtest-dev libboost-all-dev
# собираем:
cmake .
make

Запуск тестов

./test/tapeSorter_unitTest

Принцип работы программы

Внешняя сортировка сериями (т.к. вся лента не поместится в ОЗУ, а лента - символьное устройство, т.е. последовательный доступ)

И на первом обходе ленты в ходе внешней сортировки применяется внутренняя сортировка Хоара (для уменьшения числа итераций алгоритма внешней сортировки на k-1)

Сложность по ресурсам: входная лента, выходная лента и 2 временные ленты - все >= входной ленты по длине (лучше, если = ), а если размер входной ленты равен k*(2^x), где x-любое число, то можно брать временные ленты половины длины входной ленты (N/2) - тогда 100% пространства на временных лентах будет использовано под сортировку, и так обработка будет даже быстрее

Число проходов ленты: log(N)-k+1

Итоговая сложность алгоритма: O(N*(log(N)-k+1))

N - размер входной ленты

k-размер ОЗУ, выделяемый под сортировку

Перспективы использования на настоящих магнитных лентах

Как модернизировать программу, чтобы сортировать с её помощью настоящие магнитные лены, что для этого нужно, и оценку вариантов реализации читайте в комментарии в файле Tape.h

Если кратко, то для этого вам нужно написать свою реализацию интерфейса Tape