Приложение выполняет сортировку содержимого файла в многопоточном режиме. В качестве аргументов приложение принимает имя файла и количество используемых потоков. Пример аргументов для запуска приложения:
./multiSort input.txt 8
Отсортированные данные будут записаны в файл sorted8.txt
.
Особенности реализации:
- Для передачи задачи в отдельный поток используется
std::async(std::launch::async, ...)
. - Сортировка выполняется в два этапа:
- Содержимое сортируемого файла делится между числом M задействованных потоков (каждый кусок сортируемого файла описывается парой итераторов), в каждом потоке запускается алгоритм std::sort(). После этого этапа мы имеем M отсортированных кусков.
- На втором этапе попарно объединяем отсортированнные куски (сложность каждой такой процедуры будет O(N)). Чтобы сделать это эффективно, каждое объединение производим в отдельном потоке.
-
Нужно понимать, что, вместе с количеством используемых потоков возрастает и количество итераций объединения. Например, для 8 потоков их будет 3: 4 объединения + 2 объединения + 1 объединение. При этом 4 объединения на первой итерации проводятся параллельно в разных потоках, а следующие 2 объединения ожидают результатов первой итерации и, соответственно, будут выполняться позже.
-
После завершения сортировки в консоль выводится значение времени (мс), затраченного на сортировку.