Шаг 10. Прочитать в Вз и записать из Вг, сортируя Bi; в то же время сделать так, чтобы неравенства пирамиды были справедливы для В4.. .Вю-

Шаг 11. Прочитать в Вг и записать из Bi; в то же время сделать так, чтобы Вз ... Вю удовлетворяли неравенствам пирамиды.

Шаг 12. Прочитать в Bi, делая так, чтобы Вг.. .Вю удовлетворяли неравенствам пирамиды. Вернуться к шагу 1.

• Мы предполагаем, что число сортируемых записей N заранее неизвестно. На самом же деле большинство компьютеров позволяет постоянно следить за числом записей во всех файлах и можно считать, что наша вычислительная система способна сообщить значение N. Насколько существенно нам бы это помогло? К сожалению, не очень! Мы видели, что выбор с замещением весьма выгоден, но он ведет к непредсказуемому числу начальных серий. В сбалансированном слиянии мы могли бы использовать информацию о N для установления такого размера буфера В, чтобы S оказалось, скорее всего, чуть меньше степени Р; в многофазном распределении с оптимальным размещением фиктивных серий мы могли бы использовать информацию о 7V чтобы решить, какой уровень выбрать (см. табл. 5.4.2-2).

• НМЛ часто оказываются наименее надежными устройствами в вычислительной технике. Следовательно, можно принять за аксиому, что исходная вводная лента ни в коем случае не должна изменяться, пока не станет известно, что вся сортировка удовлетворительно завершена. В некоторых примерах на диаграмме А существует досадное "время, пока оператор сменит ленту" но было бы слишком рискованно затирать исходные данные ввиду возможности появления какого-либо сбоя во время длинной сортировки.

• При переходе от прямой записи к обратному чтению мы можем сэкономить некоторое время, вовсе не записывая последний буфер на ленту; он в любом случае будет вновь прочитан. Диаграмма А показывает, что этот прием в действительности экономит сравнительно немного времени, за исключением случая осциллирующей сортировки, когда направления меняются часто.

• Хотя в большинстве вычислительных систем имеется достаточно много НМЛ, было бы слишком рискованно все их использовать в процессе сортировки. Рекомендуемое процентное отношение находится в диапазоне между logp S и \ogp+i S и не очень велико при достаточно большом Р. Более высокий порядок сортировки влечет за собой, как правило, использование небольших по размеру блоков. Подумайте также о бедном операторе компьютера, который должен устанавливать все эти рабочие ленты! С другой стороны, в упр. 12 описан интересный способ использования дополнительных НМЛ, группируемых так, чтобы совместить время ввода и вывода без увеличения порядка слияния.

• При использовании компьютеров, подобных MIX, которые имеют фиксированный и довольно маленький размер блоков, для слияния едва ли требуется много внутренней памяти. Здесь осциллирующая сортировка более предпочтительна, потому что становится возможным сохранять дерево выбора с замещением в памяти во время слияния. На самом деле в этом случае можно усовершенствовать осциллирую-ц;ую сортировку (как предложил К. Дж. Белл (С. J. Bell) в 1962 году), сливая новую начальную серию с выводом каждый раз. когда выполняется слияние с рабочих лент!

• Мы видели, что файлы на нескольких бобинах должны сортироваться последовательно бобина за бобиной, чтобы избежать чрезмерной работы, связанной с перестановкой лент. Иногда такого рода приложения называются многобобинны-ми. Фактически сбалансированное слияние с шестью лентами, если оно тщательно запрограммировано, может сортировать три бобины до момента окончательного слияния.

Для слияния относительно большого числа отдельно рассортированных бобин лучше всего использовать дерево слияния с минимальной длиной пути (ср. с разделом 5.4.4). Этот подход впервые был реализован Э. Г. Фрейдом (Е. Н. Friend) [JACM 3 (1956), 166-167] и затем - У. Г. Буржем (W. Н. Burge) [Information and Control 1 (1958), 181-197], которые отметили, что оптимальный способ слияния серий данных (возможно, неравных длин) получается путем построения дерева с минимальной взвешенной длиной пути и использования длины серий в качестве весов (см. разделы 2.3.4.5 и 5.4.9), если пренебречь временем установки лент. Но файлы, занимающие несколько бобин, вероятно, следует хранить на дисках или другом запоминающем устройстве большой емкости, а не на лентах.

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

• Обсуждаемые нами вопросы впервые были рассмотрены в работах Е. Н. Friend, JACM 3 (1956), 134-168; W. Zoberbier, Elektronische Datenverarbeitung 5 (I960), 28-44, и M. A. Goetz, Digital Computer Users Handbook (New York: McGraw-Hill, 1967), 1.292-1.320.

Резюме. Мы можем следующим образом вкратце подытожить все, что узнали о сравнении различных схем слияния.

Теорема А. Трудно решить, какая схема слияния является наилучшей в конкретной ситуации. I

Примеры, которые мы видели на диаграмме А, показывают, как 100000 записей по 100 символов (или миллион записей по 10 символов), расположенных в случайном порядке, могли бы быть рассортированы с помощью шести лент при достаточно реалистических предположениях. Эти данные занимают около половины ленты и могут быть рассортированы приблизительно за 15-19 мин при использовании НМЛ MIXT. Однако существующее ленточное оборудование сильно различается по возможностям, и время выполнения такой работы на разных машинах изменяется в диапазоне приблизительно от 4 мин до 2 ч. В наших примерах около 3 мин расходуется на начальное распределение серий и внутреннюю сортировку, около 4 мин - на окончательное слияние и перемотку выводной ленты и приблизительно 7-11 мин - на промежуточные стадии слияния.

Для шести лент, которые нельзя читать в обратном направлении, наилучшим методом сортировки при наших предположениях было многофазное слияние с рас-

щеплением лент (пример 4), а для НМЛ, допускающих обратное чтение, наилучшим оказался многофазный метод с обратным чтением со сложным размещением фиктивных серий (пример 7). Осциллирующая сортировка (пример 9) занимает в нашей табели о рангах второе место. В обоих случаях каскадное слияние является более простым и лишь незначительно медленнее (примеры 5 и 8). В случае прямого чтения обычное сбалансированное слияние (пример 1) оказалось удивительно эффективным, частично из-за удачного сочетания параметров в данном конкретном примере, а частично из-за того, что при этом тратится сравнительно мало времени на перемотку.

Положение несколько изменилось бы, если бы в нашем распоряжении было другое число НМЛ.

Генераторы сортировки. В условиях большого разнообразия характеристик данных и оборудования почти невозможно написать единственную программу внешней сортировки, которая была бы удовлетворительной в подавляющем большинстве случаев. Также весьма трудно создать программу, которая в реальных условиях эффективно работает с лентами. Следовательно, разработка программного обеспечения сортировки - самостоятельная задача, требующая большой работы. Генератор сортировки - это программа, которая, основываясь на параметрах, описывающих формат данных и конфигурацию оборудования, порождает машинную программу, специально приспособленную к конкретному применению сортировки. Подобная программа часто связана с такими языками высокого уровня, как COBOL и PL/I, или она может быть написана как набор макроопределений для использования совместно с макроассемблером.

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

JUL041776 0СТ311517 N0V051605 JUL141789 N0V071917.

Трехбуквенные коды месяцев можно найти в таблице и заменить числами, причем наиболее значащие поля могут быть помещены слева:

17760704 15171031 16051105 17890714 19171107.

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