Многофазная сортировка слиянием

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

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

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

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

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

В общем, для четного числа N рабочих файлов каждая итерация сбалансированной сортировки слиянием уменьшает количество запусков в N /2 раза, тогда как для нечетного числа N рабочих файлов каждая итерация уменьшает количество запусков в среднем в раз. √ ​ ( Н ² −1)/4 = √ N ² −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.

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

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

Файл 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> *

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

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

Возвращаясь к еще одной итерации, три прогона из 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.

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

«Оптимальные» алгоритмы распределения требуют заранее знать количество прогонов. В противном случае, в более распространенном случае, когда количество прогонов заранее неизвестно, используются «почти оптимальные» алгоритмы распределения. Некоторые алгоритмы распределения включают в себя перестановку прогонов. Если количество запусков известно заранее, перед началом этапов слияния необходимо только частичное распределение. Например, рассмотрим случай с тремя файлами, начиная с n запусков в File_1. Определим F _i = F _{i −1} + F _{i −2} как i- е число Фибоначчи . Если n = Fi _в , то переместите прогоны 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 - Fi _, запусков из File_1 и File_2, добавляя объединенные n - F _i запуски к запускам F _{i +1} - n уже перемещенным в File_3. Файл_1 заканчивается с оставшимися прогонами F _{i -2} , Файл_2 очищается, а Файл_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)

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

• сбалансированная сортировка слиянием → ⁠ $16\times \log _{2}(16)=64$⁠ ,
• многофазная сортировка слиянием → ⁠ $17\times \log _{2.73}(17)=48$⁠ .

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

# files
|     average fraction of data per iteration
|     |     polyphase reduction factor on ideal sized data
|     |     |     balanced 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 или более файлах.

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

• Брэдли, Джеймс (1982), Методы работы с файлами и базами данных , Холт, Райнхарт и Уинстон, ISBN  0-03-058673-9
• Рейнольдс, Сэмюэл В. (август 1961 г.), «Обобщенный алгоритм многофазного слияния», Communications of the ACM , 4 (8), Нью-Йорк, Нью-Йорк: ACM: 347–349, doi : 10.1145/366678.366689 , S2CID   28416100
• Седжвик, Роберт (1983), Алгоритмы , Аддисон-Уэсли, стр. 163–165 , ISBN  0-201-06672-6