Частичный алгоритм сортировки
Скажите, что у меня есть 50 миллионов функций, каждая функция прибывает из диска.
В beggining моей программы я обрабатываю каждую функцию и в зависимости от некоторых условий, я применяю некоторые модификации к некоторым.
Эта точка в моей программе, я читаю функцию из диска, обрабатывая его, и записываю его обратно, потому что хорошо у меня нет достаточного количества поршня для открытия всех 50 миллионов функций сразу.
Теперь скажите, что я хочу отсортировать эти 50 миллионов функций, там какой-либо оптимальный алгоритм должен сделать это, поскольку я не могу загрузить всех одновременно?
Как частичный алгоритм сортировки или что-то как этот?
2 ответа
В общем, класс алгоритмов, который вы ищете, называется внешней сортировкой . Возможно, наиболее широко известный пример такого алгоритма сортировки называется Сортировка слиянием .
Идея этого алгоритма (внешняя версия) состоит в том, что вы разделяете данные на части, которые можно отсортировать на месте в памяти (скажем, 100 тысяч), и сортируете каждый блок независимо (используя некоторый стандартный алгоритм, такой как Быстрая сортировка ). Затем вы берете блоки и объединяете их (таким образом, вы объединяете два блока по 100 тыс. В один блок по 200 тыс.), Что можно сделать, считывая элементы из обоих блоков в буферы (поскольку блоки уже отсортированы). В конце вы объединяете два меньших блока в один блок, который будет содержать все элементы в правильном порядке.
Если вы работаете в Unix, используйте sort ;)
Это может показаться глупым, но инструмент командной строки был запрограммирован для обработки этого случая, и вам не придется его перепрограммировать.