21. Внешняя сортировка: сортировка двухпутевым и многопутевым челночным слиянием. Временная сложность алгоритмов.

 

§ 3. Челночное балансное слияние

 

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

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

            Резерв и пространство ближайшей части будут заполнены результатом слияния двух частей; при этом пространство второй части освободится и станет резервом, необходимым для слияния следующей пары частей и т.д. Схема процесса представлена на рис. 4.2.

 

  

            Рис. 4.2. Слияние частей размером R.

 

            По мере слияния частей резерв перемещается от начала файла к концу, потом двигается обратно и т.д., т.е. ведет себя, как челнок. Отсюда название метода - челночное слияние.

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

 

            Рис. 4.3.

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

            Отсюда вывод: в конце файла размер челнока надо всегда увеличивать не вдвое, а вчетверо.

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

            Таким образом, при слиянии частей размером 2R челнок имеет размер 4R. После слияния, при котором запись осуществляется в резерв, освобождается пространство обеих слитых частей. Оно и используется под резерв. Челнок теперь передвигается к началу файла. Схема слияния частей размером 2R представлена на рис. 4.4.

            Рис. 4.4. Схема слияния частей размером 2R.

 

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

            Прежде всего, специальным образом подбирают количество частей М, на которые разбивается файл. Конечно же, одна часть должна иметь такой размер Z, чтобы целиком помещаться в буфере оперативной памяти. Кроме этого, для числа М должно выполняться равенство:

.                                                             (2)

 

Тогда после некоторого прогона челнока в файле обязательно останутся 6 больших частей.

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

            Итак, в файле осталось 6 больших упорядоченных частей . Размер каждой части равен максимальному размеру резерва и равен D.

Часть 1

Часть 2

Часть 3

Часть 4

Часть 5

Часть 6

Резерв

            Далее проделаем следующие действия:

            а) перепишем шестую часть в резерв:

Часть 1

Часть 2

Часть 3

Часть 4

Часть 5

Резерв

Часть 6

            б) сольем части 4 и 6:

Часть 1

Часть 2

Часть 3

Резерв

Часть 5

Результат слияния частей 4 и 6

            в) сольем части 2 и 5:

Часть 1

Резерв

Часть 3

Результат слияния частей 2 и 5

Результат слияния частей 4 и 6

            г) сольем части 1 и 3:

Резерв

Результат слияния частей 1 и 3

Результат слияния частей 2 и 5

Результат слияния частей 4 и 6

 

            В результате этих действий резерв размером D находится в начале файла, после него “следуют” три упорядоченные части размером 2D каждая. Назовем эти части I, II и III соответственно:

Резерв

Часть I

Часть II

Часть III

            д) сольем первые половины частей I и II:

Результат слияния первых половин ч. I и II

Вторая половина Части I

 

Резерв

Вторая половина Части II

 

Часть III

            е) сольем вторые половины частей I и II:

Результат слияния первых половин ч. I и II

Резерв

Результат слияния вторых половин ч. I и II

Часть III

            Введем новые обозначения:

Часть А

Резерв

Часть В

Часть III

            Первая половина части А характеризуется тем, что в ней собраны элементы с наименьшими ключами среди всех элементов частей I и II, вторая половина части В характеризуется тем, что в ней собраны элементы с наибольшими ключами среди всех элементов частей I и II.

            ж) сольем вторую половину части А и первую половину части В:

Первая половина Части А

 

Резерв

 

Результат слияния

Вторая половина Части В

 

Часть III

            з) “перегоняем” резерв в начало файла:

Резерв

Упорядоченная начальная часть

Часть III

            и) сольем начальную часть и первую половину части III:

 

Упорядоченная начальная часть

 

Резерв

Вторая половина Части III

 

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

            Примеры. Для простоты разберем ситуацию на числах.

            1.         1 3 5 7 8 Р 6 9. Так как  6<8, то подслияние нужно; 6<7 и 6>5, смещаем (7 8):

                        1 3 5 P 7 8 6 9. Сливаем части (7 8) и (6 9):

                        1 3 5 6 7 8 9 Р.

            2.         1 3 5 6 7 Р 8 9. Так как  8>7, то подслияние не нужно:

                        1 3 5 6 7 8 9 Р.

            В обоих случаях резерв “вытесняется” в конец отсортированного файла. Остается только его удалить.

            Оценка сложности этого алгоритма - T(М)=O(ZM log2 M).

 

§ 4. Челночное многопутевое слияние

 

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

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

            Таким образом, с ростом N факторы, замедляющие сортировку, в некоторый момент становятся сильнее ускоряющего фактора. Практика показывает, что оптимальным значением для N является 4.

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

            Рис. 4.1. Схема N-путевого слияния при N=4.

            На следующем прогоне резерв, увеличенный в четыре раза, движется в обратную сторону.

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

            Если  файл столь велик, что затраты времени на ходы превалируют, имеет смысл последние этапы слияния делать двоичными.

            В § 4 гл. III излагался метод слияния двух упорядоченных последовательностей в одну упорядоченную. Познакомимся с эффективным методом, который позволяет осуществить слияние N частей при N>2. Этот метод использует сортирующее дерево (см. § 6 гл. III). Правда, в этом параграфе речь идет о сортирующем дереве “наоборот”, т.е. таком, у которого ключ элемента, соответствующего произвольной вершине, не больше ключей элементов, соответствующих ее потомкам. В корне этого дерева всегда находится элемент с минимальным ключом.

            Сформируем сортирующее дерево из первых элементов каждой части. Элемент с минимальным ключом соответствует корню. Пусть этот элемент взят из части r1. Перемещаем его в буфер вывода, на его место переносим второй элемент из той же части r1. Затем полученное дерево переделывается в сортирующее.  В корне снова оказывается элемент с минимальным ключом, взятый из некоторой части r2. Выводим его в буфер вывода, на его место переносим очередной элемент из той же части r2 и т.д.

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

******            1 7                   3 8                   5 6                   2 8       ******

            Сложность метода многопутевого слияния составляет T(М)=O(ZM logn M), поэтому он рекомендуется для сортировки больших и гигантских файлов.

            Иногда используют комбинированный алгоритм, в соответствии с которым:

            а) после внутренней сортировки объединяют группы полученных частей в большие части по методу поглощения;

            б) на следующих прогонах файла, кроме последнего и, возможно, предпоследнего, производят N-путевое слияние. Число путей слияния на предпоследнем этапе можно варьировать от 2 до N;

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