AOP_Tom3 (1021738), страница 88
Текст из файла (страница 88)
Данное преимущество нескачько ослабляется в случае многофазной сортировки с обратным чтением, так как должен быть порожден ряд убывакицнх серий; на самом деле Р. Л. Гнлстад (Рь 1,. О11эсас1) (он первым опубликовал описание метода многофазного слияния) первоначально по этой причине отверг метод обратного чтения. Но позднее он заметил, что чередование направлений будет все же давать длинные возрастающие серии. Кроме того, многофазный метод с обратным чтением — это единственный стандартный метод, который благосклонен к убывающим входным файлам в той же степени, что и к возрастающим.
° Другое преимущество выбора с замещением состоит в том, что этот метод допускает совмещение процессов чтения, записи и вычислений. Если бы мы просто выполняли внутреннюю сортировку очевидным способом --- заполнили память, расссортировали данные в ней и затем записывали данные гю мере того, как память заполняется новым содержимым, — то проход распределения занял бы примерно вдвое больше времени. Из рассмотренных нами методов внутренней сортировки еще только один можно приспособить к одновременному чтению, записи и вычислениям — пирамидальную сортировку. (Эта идея была использована при подготовке примера 10 диаграммы А.) Предположим для удобства, что внутренняя память содержит 1 000 записей, а каждый блок на ленте — по 100.
Действовать можно следующим образом (через Вэ .., Вш обозначено содержимое памяти, разделенной на 10 блоков по 100 записей). Шаг О. Заполнить память и сделать так, чтобы элементы Вэ... В~э удовлетворяли неравенствам пирамиды (с наименьшим элементом в вершине). Шаг 1. Свести Вы .. Вээ в пирамиду, затем выбрать наименьшие 100 записей и переписать их в Вш. Шаг 2. Записать из В~э, в то же время выбрать наименьшие 100 записей из Вэ .,. Вэ и поместить их в Вэ. Шаг Я. Прочитать в В~э и записать в Вэ, в то же время выбрать наименьшие 100 записей из Вэ... Вэ и поместить их в Вэ. Шаг 9.
Прочитать в В4 и записать из Вэ, в то же время выбрать наименьшие 100 записей из Вэ Вэ, поместить их в Вэ и сделать так, чтобы неравенства пирамиды были справедливы для Вэ... Вш. Шиг 1О. Прочитать в Вг и записать из Вг, сортируя В<, в то же время сделать так, чтобы неравенства пирамиды были справедливы для В<... В<о. Шиг 11. Прочитать в Вг и записать из В<, в то же время сделать так, чтобы Вз...
Вш удовлетворяли неравенствам пирамиды. Шаг 12. Прочитать в В<, делая так, чтобы Вг... В,и удовлетворяли неравенствам пирамцды. Верну.ться к шагу 1. $ ° Мы предполагаем, что число сортируемых записей ?ч' заранее неизвестно. На самом же деле болыпинство компьютеров позволяет постоянно следить за числом записей во всех файлах и можно считать, что наша вычислительная система способна сообщить значение ?г'. Насколько существенно нам бы зто помогла'? К сожалению, не очень! Мы видели, что выбор с замещением весьма выгоден, но он ведет к непредсказуемому числу начальных серий.
В сбалансированном слиянии мы могли бы использовать информацию о <г' для установления такого размера буфера В, чтобы В оказалось. скорее всего, чуть меньше степени Р; в многофазном распределении с оптимальным размещением фиктивных серий мы могли бы использовать информацию о <1< чтобы решить, какой уровень выбрать (см. табл. 5.4.2 — 2). ° НМЛ часто оказываются наименее надежными устройствами в вычислительной технике.
Следовательно, можно принять за аксиому, что исходная вводная лапти ни о коем случае не должна изменяться, пока не станет известно, что вся сортпировка удоолеплооритеяьно гиеершени. В некоторых примерах на диаграмме А существует досадное "время, пока оператор сменит ленту", но было бы слишком рискованно затирать исходные данные ввиду возможности появления какого-либо сбоя во время длинной сортировки. ° При переходе от прямой записи к обратному чтению мы можем сэкономить некоторое время, вовсе не записывая последний буфер на ленту; он в любом случае будет вновь прочитан.
Диаграмма й показывает, что этот прием в действительности экономит сравнительно немного времени, за исключением случая осциллирующей сортировки, когда направления меняются часто. ° Хотя в большинстве вычислительных систем имеется достаточно много НМЛ, было бы слишком рискованно все их использовать в процессе сортировки. Рекомендуемое процентное отношение находится в диапазоне между 1окг Я и 1ояр+< Я и не очень велико при достаточно большом Р. Более высокий порядок сортировки влечет за собой, как правило, использование небольп<их по размеру блоков. Подумайте также о бедном операторе компьютера, который должен устанавливать все эти рабочие ленты! С другой стороны, в упр. 12 описан интересный способ использования дополнительных НМЛ, группируемых так, чтобы совместить время ввода и вывода без увеличения порядка слияния.
в При использовании компьютеров, подобных М1Х, которые имеют фиксированный и довольно маленький размер блоков, для слияния едва ли требуется много внутренней памяти. Здесь осциллирующая сортировка более предпочтительна, потому что становится возможным сохранять дерево выбора с замещением в памяти во время слияния.
На салюм деле в этом случае можно усовершенствовать осциллирующую сортировку (как предложил К. Дж. Белл (С. д. Вей) в 1962 году), сливая новую начальну<о серию с выводом каждый раз. когда выполняется слияние с рабочих лент! ° Мы видели, что файлы на нескольких бобинах должны сортироваться последовательно бобина за бобиной, чтобы избежать чрезмерной работы, связанной с перестановкой лент. Иногда такого рода приложения называются многобобинными.
Фактически сбалансированное слияние с шестью лентами, если оно тщательно запрограммировано, может сортировать три бобины до момента окончательного слияния. Для слияния относительно большого числа отдельно рассортированных бобин лучше всего использовать дерево глияния с минимальной длиной пути (ср. с разделом 5.4.4). Этот подход впервые был реализован Э. Г. Френдом (Е. Н.
Ебепй) [,УАСМ 3 (1956), 166-167) и затем — У. Г. Буржем (%. Н. Впгйе) [1!Ногтабоп апд Сопгго! 1 (1958), 181--197), которые отметили, что оптимальный способ слияния серий данных (возможно, неравных длин) получается путем построения дерева с минимальной еаеешеняов длиной пути и использования длины серий в качестве весов (см. разделы 2.3.4.5 и 5.4.9), .если пренебречь временем уч:тановки лент. Но файлы, занимающие несколько бобин, вероятно, следует хранить на дисках или друтом запоминающем устройстве большой емкости, а не на лентах. ° В нашем обсуждении мы, не особенно задумываясь, предполагали, что имеется возможность использовать непосредственно инструкции ввода-вывода и что никакой сложный системный интерфейс не мешает нам использовать ленты с такой эффективностью, на какую рассчитывали конструкторы оборудования.
Эти идеальные предположения позволили нам проникнуть в суть проблем слияния, и они могут дать некоторый подход к разработке соответствующих операционных систем. Однако следует понимать, что мультипрограммирование и мультипроцессирование могут значительно усложнить ситуацию. ° Обсуждаемые нами вопросы впервые были рассмотрены в работах Е. Н. Рг1епс1, ЛАСМ 3 (1956), 134-168; 1з'.
ХоЬегЪ|ег, Е!е(гсгоп!всйе ВагепъегагЬе!Сипя 5 (1960), 28-44, и М. А. Ооегх, В!6йа! Сотрпсег Ьвег'в НавдЬоо!с (Меж Уогйп МсОгав-Н111, 1967), 1.292-1.320. Резюме. Мы можем следующим образом вкратце подытожить все, что узнали о сравнении различных схем слияния. Теорема А.
Трудно решить, какая схема слияния является наилучшей в конкретной ситуации. ! Примеры, которые мы видели на диаграмме А, показывшот, как 100000 записей по 100 символов (или миллион записей по 10 символов), расположенных в случайном порядке, могли бы быть рассортированы г помощью шести лент при достаточно реалистических предположениях. Эти данные занимают около половины ленты и могут быть рассортированы приблизительно за 15 — 19 мин при использовании НМЛ И1ХТ. Однако существующее ленточное оборудование сильно различается по возможностям, и время выполнения такой работы на разных машинах изменяется в диапазоне приблизительно от 4 мин до 2 ч. В наших примерах около 3 мин расходуется на начальное распределение серий и внутреннюю сортировку, около 4- 1 мин — на окончательное слияние и перемотку выводной ленты и приблизительно 7- -11- мин — на промежуточные стадии слияния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
