Программа сортировки файла, написана для работы в системе Linux, требует библиотеку pthread.
Программа сортирует входной файл, представив его в виде чисел размером 2 байта. Для компиляции release версии используйте make all. Для компиляции debug версии используйте make debug.
Запуск программы: ./{{program_name}} {{file_name}} [num_threads]
program_name - имя исполняемого файла (file_sort по умолчанию). file_name - имя файла, который необходимо отсортировать. num_threads - желаемое количество тредов используемых для сортировки (если не указано, то программа определит количество ядер в системе и автоматически выставит столько же тредов, сколько ядер).
Выходной файл будет находиться в той же директории где производится запуск программы, будет называться out.data
Описание работы:
-
Входной файл разбивается на куски размером 256 МБ.
1а) Кусок 256 МБ разбивается на более мелкие куски размером 256мб / число_тредов. 1б) Каждый мелкий кусок сортируется своим тредом посредством qsort. 1в) Мелкие кусочки сливаются в один 256 МБ многопоточной сортировкой слиянием (для примера, 8 кусочков сортируются 4 тредами, обрабатывающими по 2 кусочка. На выходе получается 4 кусочка, они сливаются 2 тредами в 2 кусочка, затем одним тредом в 256 МБ кусок). 1г) 256 МБ кусок записывается в файл на жесткий диск temp0.dat 1д) Повторяется цикл пока весь входной файл не разбит на 256 МБ куски.
-
Отсортированные куски сортировкой слиянием образуют конечный файл.
2а) Создается N+1 буферов размером 256 / (N + 1) каждый для N входных временных файлов и 1 выходного (Буферизация). 2б) Из временных файлов загружаются блоки данных и производится сортировка слиянием в выходной буфер. 2в) Когда выходной буфер заполнен - он пишет данные в выходной файл на диск. 2г) Цикл повторяется пока все временные файлы не прочитаны до конца.
-
Файл отсортирован.
Описание исходников:
file_sorter.h - описание класса, сортирующего файл. file_sorter.cpp - методы класса main.cpp - чтение аргументов командной строки, создание объекта сортирующего класса, вызов функций сортировки, замеры времени, потраченного на этапы сортировки.