Почему эта сортировка лучше всего подходит для внешней сортировки?
При изучении алгоритмов сортировки это называется сортировкой кучи, используемой для внешней сортировки. Я не могу понять, чем она отличается с точки зрения методов сортировки, когда мы имеем дело с внешним хранилищем? Или что это за то, что сортировка в куче делает уникальной, чтобы считаться полезной для внешней сортировки?
Может кто-нибудь объяснить это?
2 ответа
Давайте возьмем пример из кода ядра Linux:
Эта функция выполняет сортировку на заданном массиве. Время сортировки составляет O(n log n) как в среднем, так и в худшем случае. В то время как qsort в среднем примерно на 20% быстрее, он страдает от эксплуатируемого O(n*n) поведения в худшем случае и дополнительных требований к памяти, которые делают его менее пригодным для использования ядром.
Из Википедии:
Heapsort также конкурирует с сортировкой слиянием, которая имеет те же временные границы. Сортировка слиянием требует Ω(n) вспомогательного пространства, а для сортировки по сечениям требуется только постоянное количество. Heapsort обычно работает быстрее на машинах с маленьким или медленным кэшем данных и не требует такого большого количества внешней памяти.
Внешняя часть сортировки - это k-way merge sort. Блоки или файлы данных на внешнем носителе, например на жестком диске (дисках), повторяются слитными буквами "k" за один раз, пока не будет создан один отсортированный файл.
Мин-куча является распространенным способом реализации внутренней части k-way слияния.
Первоначальный этап создания блоков или файлов данных может быть практически любого внутреннего вида, который стабилен, если требуется стабильность. В случае сортировки записей сортировка слиянием может использоваться для сортировки массива указателей на записи, что уменьшает требования к пространству, поскольку только массиву указателей требуется второй массив, в отличие от второго массива для записей. Следует отметить, что сортировка указателей может быть медленнее, чем сортировка записей, так как сортировка через указатели приводит к случайному доступу к записям для сравнения, что неудобно для кэша.
Сортировка Gnu для больших текстовых файлов является примером внешней сортировки. Он считывает "порцию" строк за раз, создавая указатели на строки, использует сортировку слиянием по указателям, а затем создает временный файл для каждого отсортированного фрагмента. Затем он выполняет 16-стороннее (16 по умолчанию) слияние временных файлов, пока не достигнет конечного шага слияния, когда последнее слияние переходит к указанному выходному файлу.
Ссылка на источник. Это большая программа, отчасти потому, что у нее так много вариантов.
http://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort.c
Не
сортировка кучи лучше всего подходит для создания начальных прогонов во внешней сортировке,
но использование кучи для создания начальных прогонов приводит к ожидаемой начальной длине прогонов, вдвое превышающей размер кучи (для равномерного распределения ключей), следовательно, вдвое меньше начальных прогонов, чем любой метод, сортирующий каждую партию записей и записывающий ее как запустить (используя тот же объем оперативной памяти).
При двустороннем объединении вдвое меньше начальных запусков сохраняет весь проход. С продвинутыми схемами слияния, высокой степенью (количество слияний в одну) или даже числом проходов (отношение данных / объем ОЗУ) это теряет влияние.