Сортировка полифазным слиянием - Polyphase merge sort

Полифазная сортировка слиянием - это разновидность сортировки слиянием снизу вверх, которая сортирует список с использованием начального неравномерного распределения подсписок (прогонов), в основном используется для внешней сортировки , и более эффективна, чем обычная сортировка слиянием, когда их меньше восьми. внешние рабочие файлы (например, ленточный накопитель или файл на жестком диске). Сортировка с многофазным слиянием не является стабильной .

Обычная сортировка слиянием

Сортировка слияние разбивает запись набора данных в сортированные пробеги записей , а затем повторно сливается отсортированными бегут в большие отсортированные пробеги , пока только один прогон, отсортированный набор данные, остаются.

Обычная сортировка слиянием с использованием четырех рабочих файлов организует их как пару входных файлов и пару выходных файлов. Набор данных равномерно распределяется между двумя рабочими файлами либо в виде отсортированных прогонов, либо, в простейшем случае, отдельных записей, которые можно рассматривать как отсортированные серии размером 1. После того, как весь набор данных передан в два рабочих файла, эти два рабочих файла становятся входными файлами для первой итерации слияния. Каждая итерация слияния запускает слияние двух входных рабочих файлов, чередуя объединенный выход между двумя выходными файлами, снова распределяя объединенные прогоны равномерно между двумя выходными файлами (до последней итерации слияния). После того, как все прогоны из двух входных файлов объединены и выведены, выходные файлы становятся входными файлами и наоборот для следующей итерации слияния. Количество прогонов уменьшается в 2 раза на каждой итерации, например, 64, 32, 16, 8, 4, 2, 1. Для последней итерации слияния два входных файла имеют только один отсортированный прогон (1/2 из набор данных) каждый, а объединенный результат представляет собой один отсортированный прогон (отсортированный набор данных) для одного из выходных файлов. Это также описано в разделе Сортировка слиянием § Использование с ленточными накопителями .

Если есть только три рабочих файла, то обычная сортировка слиянием слияниями отсортированных запускает два рабочих файла в один рабочий файл, а затем распределяет запуски равномерно между двумя выходными файлами. Итерация слияния уменьшает количество запусков в 2 раза, итерация с перераспределением не уменьшает количество запусков (коэффициент равен 1). Можно рассматривать каждую итерацию для уменьшения количества запусков в среднем на √ 2 ≈ 1,41. Если есть 5 рабочих файлов, то шаблон чередуется между трехсторонним и двухсторонним слиянием, в среднем √ 6 ≈ 2,45.

В общем, для четного числа N рабочих файлов каждая итерация обычной сортировки слиянием уменьшает количество запусков в N / 2, в то время как для нечетного числа N рабочих файлов каждая итерация уменьшает количество запусков на средний коэффициент. из √ ( N 2 −1) / 4 = √ N 2 −1 / 2.

Полифазное слияние

Для N <8 рабочих файлов многофазная сортировка слиянием обеспечивает более высокий коэффициент сокращения эффективного счетчика прогонов за счет неравномерного распределения отсортированных прогонов между N -1 рабочим файлом (поясняется в следующем разделе). Каждая итерация слияния запускает N -1 рабочих файлов в один выходной рабочий файл. Когда достигается конец одного из N -1 рабочих файлов, он становится новым выходным файлом, а то, что было выходным файлом, становится одним из N -1 рабочих входных файлов, начиная новую итерацию многофазной сортировки слиянием. Каждая итерация объединяет только часть набора данных (примерно от 1/2 до 3/4), за исключением последней итерации, которая объединяет весь набор данных в один отсортированный прогон. Начальное распределение настроено так, что за раз очищается только один входной рабочий файл, за исключением последней итерации слияния, которая объединяет N -1 отдельных прогонов (разного размера, это объясняется далее) из N -1 входных рабочих файлов. в один выходной файл, что приведет к единственному отсортированному запуску отсортированного набора данных.

Для каждой многофазной итерации общее количество прогонов следует шаблону, аналогичному перевернутым числам Фибоначчи последовательности более высокого порядка . С 4 файлами и набором данных, состоящим из 57 запусков, общее количество запусков на каждой итерации будет 57, 31, 17, 9, 5, 3, 1. Обратите внимание, что за исключением последней итерации, коэффициент уменьшения количества запусков равен немного меньше 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1, около 1,84 для случая с 4 файлами, но каждая итерация, кроме последней, уменьшала количество запусков при обработке около 65% набора данных, поэтому коэффициент уменьшения количества запусков на набор данных, обработанный во время промежуточных итераций, составляет около 1,84 / 0,65 = 2,83. Для набора данных, состоящего из 57 прогонов по 1 записи в каждом, затем после начального распределения многофазная сортировка слиянием перемещает 232 записи в течение 6 итераций, необходимых для сортировки набора данных, с общим коэффициентом уменьшения 2,70 (более подробно это объясняется позже. ).

После первой многофазной итерации выходной файл теперь содержит результаты слияния N −1 исходных запусков, но оставшиеся N −2 входных рабочих файлов по-прежнему содержат оставшиеся исходные запуски, поэтому вторая итерация слияния производит запуски размера ( N −1) + ( N −2) = (2 N - 3) исходных пробегов. Третья итерация производит серии оригинальных прогонов размером (4 N - 7). С 4 файлами первая итерация создает прогоны размера 3 исходных прогонов, вторая итерация 5 исходных прогонов, третья итерация 9 исходных прогонов и так далее, следуя шаблону типа Фибоначчи, 1, 3, 5, 9, 17, 31, 57, ..., поэтому увеличение размера серии следует по той же схеме, что и уменьшение количества запусков в обратном порядке. В примере с 4 файлами и 57 прогонами по 1 записи в каждой последней итерации объединяются 3 прогона размером 31, 17, 9, в результате получается один отсортированный прогон размером 31 + 17 + 9 = 57 записей, отсортированный набор данных. Пример количества запусков и размеров запусков для 4 файлов, 31 запись можно найти в таблице 4.3.

Идеальная 3-х файловая многофазная сортировка слиянием

Проще всего рассматривать многофазное слияние, начиная с его конечных условий и работая в обратном направлении. В начале каждой итерации будет два входных файла и один выходной файл. В конце итерации один входной файл будет полностью использован и станет выходным файлом для следующей итерации. Текущий выходной файл станет входным файлом для следующей итерации. Остальные файлы (только один из трех файлов) были израсходованы только частично, и их оставшиеся прогоны будут введены для следующей итерации.

Файл 1 только что очистился и стал новым выходным файлом. На каждой входной ленте остается по одному прогону, и объединение этих прогонов вместе создаст отсортированный файл. 

File 1 (out):                                           <1 run> *        (the sorted file)
File 2 (in ): ... | <1 run> *               -->     ... <1 run> | *          (consumed)
File 3 (in ):     | <1 run> *                           <1 run> | *          (consumed)

...  possible runs that have already been read
|    marks the read pointer of the file
*    marks end of file

Возвращаясь к предыдущей итерации, мы читали из 1 и 2. Один прогон объединяется из 1 и 2, прежде чем файл 1 станет пустым. Обратите внимание, что файл 2 не полностью израсходован - у него осталось одно выполнение, чтобы соответствовать окончательному слиянию (см. Выше). 

File 1 (in ): ... | <1 run> *                      ... <1 run> | *
File 2 (in ):     | <2 run> *           -->            <1 run> | <1 run> *
File 3 (out):                                          <1 run> *

Возвращаясь к другой итерации, 2 прогона объединяются из 1 и 3, прежде чем файл 3 станет пустым. 

File 1 (in ):     | <3 run>                        ... <2 run> | <1 run> *
File 2 (out):                               -->        <2 run> *
File 3 (in ): ... | <2 run> *                          <2 run> | *

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

File 1 (out):                                          <3 run> *
File 2 (in ): ... | <3 run> *               -->    ... <3 run> | *
File 3 (in ):     | <5 run> *                          <3 run> | <2 run> *

Возвращаясь к другой итерации, 5 прогонов объединяются из 1 и 2, прежде чем файл 1 станет пустым. 

File 1 (in ): ... | <5 run> *                      ... <5 run> | *
File 2 (in ):     | <8 run> *               -->        <5 run> | <3 run> *
File 3 (out):                                          <5 run> *

Распределение для многофазной сортировки слиянием

Глядя на идеальный вариант из трех файлов, количество прогонов для объединенной работы в обратном направлении: 1, 1, 2, 3, 5, ... показывает последовательность Фибоначчи. Последовательность для более чем трех файлов немного сложнее; для 4 файлов, начиная с конечного состояния и работая в обратном направлении, шаблон счетчика запусков равен {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3 , 2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ....

Чтобы все работало оптимально, последняя фаза слияния должна иметь ровно один запуск для каждого входного файла. Если какой-либо входной файл имеет более одного запуска, потребуется еще одна фаза. Следовательно, сортировка с многофазным слиянием должна быть умной в отношении начального распределения прогонов входных данных по исходным выходным файлам. Например, входной файл с 13 запусками будет записывать 5 запусков в файл 1 и 8 запусков в файл 2.

На практике входной файл не будет иметь точного количества прогонов, необходимого для идеального распределения. Один из способов справиться с этим - дополнить фактическое распределение воображаемыми «фиктивными прогонами», чтобы смоделировать идеальное распределение прогонов. Пробный запуск ведет себя как пробег без записей. Объединение одного или нескольких фиктивных прогонов с одним или несколькими реальными прогонами просто объединяет реальные прогоны, а объединение одного или нескольких фиктивных прогонов без реальных прогонов приводит к одному фиктивному прогону. Другой подход - имитировать фиктивные прогоны по мере необходимости во время операций слияния.

«Оптимальные» алгоритмы распределения требуют заранее знать количество прогонов. В противном случае, в более распространенном случае, когда количество прогонов заранее не известно, используются алгоритмы «почти оптимального» распределения. Некоторые алгоритмы распределения включают переупорядочивание прогонов. Если количество прогонов известно заранее, перед началом фаз слияния необходимо только частичное распределение. Например, рассмотрим вариант из 3 файлов, начиная с n запусков в File_1. Определим F i = F i −1 + F i −2 как i- е число Фибоначчи . Если n = F i , то перемещение F i −2 запускается в File_2, оставляя F i −1 запусков, остающихся в File_1, идеальное распределение запусков. Если F i < n < F i +1 , перемещение n - F i переходит в File_2, а F i +1 - n - в File_3. Первая итерация слияния объединяет n - F i запусков из File_1 и File_2, добавляя объединенные прогоны n - F i к F i +1 - n запускам, уже перемещенным в File_3. В конце File_1 остается F i −2 запусков, File_2 очищается, а File_3 заканчивается F i −1 запусков, что снова является идеальным распределением запусков. Для 4 или более файлов математика более сложная, но концепция та же.

Сравнение с обычной сортировкой слиянием

После начального распределения обычная сортировка слиянием с использованием 4 файлов сортирует 16 прогонов отдельных записей в 4 итерациях всего набора данных, перемещая в общей сложности 64 записи, чтобы отсортировать набор данных после начального распределения. При многофазной сортировке слиянием с использованием 4 файлов будет отсортировано 17 прогонов отдельных записей за 4 итерации, но поскольку каждая итерация, но последняя итерация перемещает только часть набора данных, перемещается всего 48 записей, чтобы отсортировать набор данных после начальной распределение. В этом случае обычный коэффициент сортировки слиянием равен 2,0, а общий коэффициент многофазности составляет ≈2,73.

Чтобы объяснить, как коэффициент уменьшения связан с производительностью сортировки, используются следующие уравнения коэффициента уменьшения: 

reduction_factor = exp(number_of_runs*log(number_of_runs)/run_move_count)
run_move_count = number_of_runs * log(number_of_runs)/log(reduction_factor)
run_move_count = number_of_runs * log_reduction_factor(number_of_runs)

Используя уравнение подсчета ходов для приведенных выше примеров:

  • обычная сортировка слиянием → ,
  • многофазная сортировка слиянием → .

Вот таблица эффективных коэффициентов уменьшения для многофазной и обычной сортировки слиянием, перечисленных по количеству файлов на основе фактических сортировок из нескольких миллионов записей. Эта таблица примерно соответствует коэффициенту уменьшения для перемещенных таблиц набора данных, показанных на рис. 3 и рис. 4 многофазного слияния sort.pdf. 

# files
|     average fraction of data per iteration
|     |     polyphase reduction factor on ideal sized data
|     |     |     ordinary reduction factor on ideal sized data
|     |     |     |
3     .73   1.94  1.41  (sqrt  2)
4     .63   2.68  2.00
5     .58   3.20  2.45  (sqrt  6)
6     .56   3.56  3.00
7     .55   3.80  3.46  (sqrt 12)
8     .54   3.95  4.00
9     .53   4.07  4.47  (sqrt 20)
10    .53   4.15  5.00
11    .53   4.22  5.48  (sqrt 30)
12    .53   4.28  6.00
32    .53   4.87 16.00

В общем, многофазная сортировка слиянием лучше, чем обычная сортировка слиянием, когда файлов меньше 8, в то время как обычная сортировка слиянием начинает улучшаться примерно при 8 или более файлах.

Рекомендации

дальнейшее чтение

Внешние ссылки