Алгоритм частичной сортировки

Question

Скажем, у меня есть 50 миллионов функций, каждая функция приходит с диска.

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

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

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

Как алгоритм частичной сортировки или что-то в этом роде?

Answer 1

В общем, класс алгоритмов, который вы ищете, называется внешняя сортировка . Пожалуй, наиболее широко известный пример такого алгоритма сортировки называется сортировка слиянием .

Идея этого алгоритма (внешней версии) состоит в том, что вы разбиваете данные на части, которые можно сортировать по месту в памяти (скажем, 100 тысяч), и сортировать каждый блок независимо (используя некоторый стандартный алгоритм, такой как ). Быстрая сортировка ). Затем вы берете блоки и объединяете их (таким образом, вы объединяете два блока по 100 КБ в один блок по 200 КБ), что можно сделать, считав элементы из обоих блоков в буферы (поскольку блоки уже отсортированы). В конце вы объедините два меньших блока в один блок, который будет содержать все элементы в правильном порядке.

Answer 2

Если вы работаете в Unix, используйте sort;)

Может показаться глупым, но инструмент командной строки был запрограммирован для обработки этого случая, и вам не придется его перепрограммировать.