/joom-home-task

A repository for home task in Joom hiring process

Primary LanguageC++

Внешняя сортировка

В коде (файл sort.cpp) реализован стандартный алгоритм внешней сортировки.

Параметры для этой внешней сортировки -- это размер оперативной памяти в байтахRAM_BYTES и количество одновременно сливаемых отрезковBLOCKS_PER_LAYER. Из этих параметров, кроме прочего, получается параметр BLOCK_BYTES -- размер одного блока данных.

Используется, по сути, сортировка слиянием, но сливаются одновременно не два отрезка, а BLOCKS_PER_LAYER. Ещё одно отличие заключается в том, что в листьях дерева сортировки слиянием находятся не единичные строки, а эти блоки данных, которые сортируются уже в оперативной памяти.

Такой алгоритм работает за $O(\frac{N}{B}\log_{\frac{M}{B}}\frac{N}{B})$, где $N$ -- количество строк, $M$ -- размер оперативной памяти в байтах, $B$ -- размер одного блока данных в байтах.

По окончанию работы алгоритма результат сохраняется в файл result.txt.

Кроме sort.cpp в репозитории лежит файл generator.cpp -- это как раз генератор нужного файла и check.cpp, который проверяет файл result.cpp на корректность, то есть отсортированность.

Результаты

Внешняя сортировка работает, возвращает отсортированный файл.

Производительности есть, куда расти. Вот результаты времени работы алгоритма:

RAM lines max_len BPL=2 BPL=5 BPL=10 BPL=50 BPL=100 BPL=500 BPL=1000
4MB 1000000 20 5.27s 4.65s 4.01s 4.3s 4.57s 6.11 6.67
500MB 100000000 20 41.07m N/A N/A N/A N/A N/A N/A

При 500MB оперативной памяти замерялся только случай BPL (это BLOCKS_PER_LAYER)=2, так как тестировать все случаи вышло бы дорого по времени.

Как улучшать?

Тут есть несколько идей, для реализации которых не хватило времени:

  • Многопоточность. Внешняя сортировка хорошо параллелизуется, так как по сути это и есть сортировка слиянием. С помощью многопоточности можно примерно на порядок улучшить время работы.
  • С помощью хешей сортировать строки за $O(N(K + \log K\log N))$, где $N$ -- количество строк, а $K$ -- максимальная длина. Это улучшит сортировку блоков, которые находятся в листьях дерева. По ощущениям, эта часть алгоритма, особенно при невысоком дереве, занимает достаточно много времени и ресурсов.
  • Увеличить буфер с определённого в iostream по умолчанию до BLOCK_BYTES, чтобы читать разом набор строк. Должно тоже ускорить. Была попытка увеличить буфер с помощью собственных классов (см. ветку buffer-experiment), но это лишь замедлило программу примерно в 60 раз. Тем не менее, я верю, что этим тоже можно ускорить программу.