5.4. ВНЕШНЯЯ СОРТИРОВКА

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

Предположим, например, что предназначенный для сортировки файл состоит из 5 ООО записей R1R2 ... д5000000 длиной по 20 слов (хотя ключи Ri не обязательно должны иметь такую длину). Как быть, если во внутренней памяти данной машины помещается одновременно только 1 ООО из этих записей?

Сразу напрашивается такое решение: рассортировать каждьгй из пяти подфай-лов i?i... Дюооооо, .Rioooooi • •-.2000000) •••> Л4000001 • • •-Rsoooooo по отдельности и затем слить полученные подфайлы. К счастью, слияние оперирует только очень простыми структурами данных, а именно - линейными списками, обрабатывать которые можно последовательно, как стеки или очереди. Поэтому для реализации метода слияния годятся самые непритязательные устройства внешней памяти.

Только что описанный процесс - внутренняя сортировка с последующим "внешним слиянием" - весьма популярен, и наше изучение внешней сортировки сведется, в основном, к вариациям на эту тему.

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

Рассмотрим сначала процесс внешней сортировки, использующей в качестве вспомогательной памяти накопители на магнитных лентах (в дальнейшем для краткости будем употреблять термин "магнитные ленты"). Вероятно, простейшим и наиболее привлекательным способом слияния с помощью лент служит сбалансированное двухпутевое слияние, в основе которого лежит идея, использовавшаяся ранее в алгоритмах 5.2.4, N, S и L. В процессе слияния нам потребуются четыре "рабочие ленты" На первой фазе восходящие серии, получаемые при внутренней сортировке, помещаются поочередно на ленты 1 и 2 до тех пор, пока не исчерпаются исходные данные. Затем ленты 1 и 2 перематываем к началу и выполняем слияние серий, которые находятся на этих лентах, получая новые серии, вдвое длиннее исходных. Эти новые серии записываются по мере их формирования попеременно на

ленты 3 и 4. (Если на ленте 1 на одну серию больше, чем на ленте 2, то предполагается, что лента 2 содержит дополнительную "фиктивную" серию длиной 0.) Затем все ленты перематываются к началу и содержимое лент 3 и 4 сливается в серии удвоенной длины, записываемые поочередно на ленты 1 и 2. Процесс продолжается (при этом длина серий каждый раз удваивается) до тех пор, пока не останется одна серия (а именно - весь упорядоченный файл). Если после внутренней сортировки было получено S серий, причем 2*" < 5 < 2*, то процедура сбалансированного двухпутевого слияния произведет ровно fc = "lg S] проходов по всем данным.

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

Лента 1 Ri ... JRiooooooi Jf?20ooooi • • Дзоооооо! Д4000001 • • • д5000000 Лента 2 Д1000001 • • • Д2000000; Д3000001 • • • Д4000000 Лента 3 (Пустая) Лента 4 (Пустая)

После первого прохода слияния на лентах 3 и 4 получатся более длинные серии, чем на лентах 1 и 2:

Лента 3 Ri... JR2000000; Д4000001 • • д5000000 Лента 4 JR2000001 • • • Л4000000

(В конец ленты 2 неявно добавляется фиктивная серия, так что серия JR4000001 • • • д5000000 просто копируется на ленту 3.) После перемотки всех лент к началу следующий проход по данным приведет к такому результату:

Лента 1 JRi ... JR4000000 Лента 2 Д4000001 • • ?5оооооо

(Серия JR4000001 • • • Д5000000 снова копируется, но если бы мы начали с 8 млн записей, в этот момент на ленте 2 содержалось бы JR4000001 • • • Дзоооооо •) Например, после еще одной перемотки на ленте 3 окажется серия JRi... JR5000000 и сортировка закончится.

Сбалансированное слияние легко обобщается для Г лент при любом Г > 3. Выберем произвольное число F, 1 < F < Г, и разделим Т лент на два "банка": Р лент в левом банке иТ - Р лент в правом банке. Распределим исходные серии как можно равномернее по Р лентам левого "банка", затем выполним F-путевое слияние слева направо, после этого - CP - Р)-путевое слияние справа налево и так до тех пор, пока сортировка не завершится. Обычно значение Р лучше всего выбирать равным \Т/2] (см. упр. 3 и 4).

При Г = 4, Р = 2 имеем частный случай - сбалансированное двухпутевое слияние. Вновь рассмотрим предыдущий пример, используя большее количество лент; положим Г = 6 и F = 3. Начальное распределение теперь будет таким;

Лента 1 Ri . JRiooooooi Jfsoooooi • • • Д4000000

Лента 2 JRioooooi • • • ?2оооооо; .R4000001 • • • Д5000000 (4)

Лента 3 Д2000001 • • • J??3oooooo

Первый проход слияния приведет к следующему результату: Лента 4 Ri... JR3000000

Лента 5 Д3000001 • • • Д5000000 (5)

Лента 6 (Пустая)

(Предполагается, что на ленте 3 помещена фиктивная серия.) На втором проходе слияния работа завершается и серии JRi... JR5000000 помещаются на ленту 1. Этот частный случай для Т = 6 эквивалентен случаю для Г = 5, поскольку лента 6 используется лишь при S >7.

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

Сбалансированное слияние кажется очень простым и естественным. Но если приглядеться внимательнее, то сразу видно, что это не наилучший способ для рассмотренных выше частных случаев. Вместо того чтобы переходить от (1) к (2) и перематывать все ленты, нам следовало остановить первое слияние, когда на лентах 3 и 4 содержались соответственно i?i... Д2000000 и Д2000001 • • • .R4000000, а лента 1 была готова к считьшанию Д4000001 • • • 5000000- Затем ленты 2-4 могли быть перемотаны к началу и сортировка завершилась бы трехпутевым слиянием на ленту 2. Общее число записей, прочитанных с ленты в ходе этой процедуры, составило бы 4000000 + 5000000 = 9000000 против 5000000 + 5000000 + 5000000 = 15,000000 в сбалансированной схеме. Сообразительная машина могла бы постичь и это!

Имея пять серий и четыре ленты, можно поступить еще лучше, распределив серии следующим образом:

Лента 1 Ri... Дюооооо; Д3000001 • • Jf?4oooooo Лента 2 Д1000001 • • • Д2000000; Д4000001 • • Jfsoooooo Лента 3 Д2000001 • • • J??30ooooo Лента 4 (Пустая)

Теперь, выполнив трехпутевое слияние на ленту 4 и перемотку лент 3 и 4 с последующим трехпутевым слиянием на ленту 3, можно было бы завершить сортировку, прочитав всего 3000000 + 5000000 = 8000000 записей.

Наконец, если бы мы имели шесть лент, то могли бы, конечно, записать исходные серии на ленты 1-5 и закончить сортировку за один проход, выполнив пятипутевое слияние на ленту 6. Анализ этих случаев показывает, что простое сбалансированное слияние не является наилучшим и было бы интересно поискать более удачные способы слияния.

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