AOP_Tom3 (1021738), страница 89
Текст из файла (страница 89)
1 1 г Для шести лент, которые нельзя читать в обратном направлении, наилучшим методом сортировки при наших предположениях было многофазное слияние с рас- щеплением лент (пример 4), а для НМЛ, допускающих обратное чтение, наилучшим оказался многофазный метод с обратным чтением со сложным размещением фиктивных серий (пример 7). Осциллирующая сортировка (пример 9) занимает в нашей табели о рангах второе место. В обоих случаях каскадное слияние является более простым и лишь незначительно медленнее (примеры 5 и 8). В случае прямого чтения обычное сбалансированное слияние (пример 1) оказалось удивительно эффективным, частично из-за удачного сочетания параметров в данном конкретном примере, а частично из-за того, что при этом тратится сравнительно мало времени на перемотку.
Положение несколько изменилось бы, если бы в нашем распоряжении было другое число НМЛ Генераторы сортировки. В условиях большого разнообразия характеристик данных и оборудования почти невозможно написать единственную программу внешней сортировки, которая была бы удовлетворительной в подавляющем большинстве случаев. Также весьма трудно создать программу, которая в реальных условиях эффективно работает с лентами. Следовательно, разработка программного обеспечения сортировки — самостоятельная задача, требующая большой работы. Генератор соршировки — зто программа, которая, основываясь на параметрах, описывающих формат данных и конфигурацию оборудования, порождает машинную программу, специально приспособленную к конкретному применению сортировки.
Подобная программа часто связана с такими языками высокого уровня, как СОВОГО и РЕ/1, илн она может быть написана как набор макроопределений для использования совместно с макроассемблером. Одной из особенностей, обычно обеспечиваемых генератором сортировки, является возможность вставлять собственные команды — особые инструкции, которые должны включатся в первый и последний проходы программы сортировки.
Собственные команды первого прохода обычно используются для некоторой коррекции исходных записей, часто сокращая их или незначительно удлиняя, чтобы привести к форме, более простой для сортировки. Пусть, например, исходные записи должны быть рассортированы по девятисимвольному ключу, изображающему дату в формате "месяц-день-год'; ЗШ041776 007311817 80Ч081606 ЗШ141789 80Ч071917. Трехбуквенные коды месяцев можно найти в таблице и заменить чигшами, причем наиболее значащие поля могут быть помещены слева: 17760704 15171031 16081106 17890714 19171107.
Это уменьшает длину записей и упрощает последующие сравнения. (Код ключей мог бы быть сделан даже более компактным.) Собственные команды последнего прохода могут использоваться для восстановления исходного формата и/или для внесения других желательных изменений в файл, и/или для вычисления какой- либо функции от выводных записей. Алгоритмы слияния, которые мы изучили, организованы таким образом, что последний проход легко отличить от остальных фаз слияния.
Заметим, что если имеются собственные команды, то должно быть, по крайней мере, два прохода по файлу, даже если он первоначально находился в нуж- ном порядке. Собственные команды, изменяющие размер записей, могут затруднить совмещение некоторых операций ввода-вывода в осциллирующей сортировке.
Генераторы сортировки заботятся о таких системных деталях, как соглашения о метках на лентах; они также часто обеспечивают подсчет контрольной суммы илн иные проверки того, что никакая часть файла не пропала и не изменилась. Иногда имеются средства для остановки сортировки в удобных местах и возобновления ее позднее. Самые высококачественные генераторы позволяют записям иметь динамически меняющиеся длины ~см. П. 1. Ч'акэ, САСМ 6 ~1963), 267 — 272).
*Слияние с меньшим числом буферов. Мы видели, что 2Р+ 2 буферов достаточно для поддержания быстрого движения лент в течение Р-путевого слияния. В завершение этого раздела проведем математический анализ времени слияния в том случае, когда в нашем распоряжении имеется меньше 2Р + 2 буферов. Очевидно, что желательно иметь два буфера вывода — - можно будет выполнять запись из одного буфера, образуя в это же время следующий блок вывода в другом. Поэтому можно вообще не рассматривать вопрос вывода и заняться только вводом. Допустим, имеется Р+ Я буферов ввода, где 1 < й < Р.
Воспользуемся для описания нашей ситуации моделью, предложенной в работе Ь. Л. 11оос1гнш, 1ВМ Яув~ешэ Х 9 (1970), 118 — 144. Чтение одного блока ленты занимает одну единицу времени. Обозначим через рв вероятность того, что в течение этого времени ни один из буферов ввода не станет пустым, через р~ — что один буфер станет пустым, через рйэ — что два или больше буферов станут пустыми и т. д.
По завершении чтения ленты мы оказываемся в одном из („1 + 1 состояний. Состпояние 6, („~ буферов пусты, Мы начинаем читать блок подходящего файла в один из ннх, используя метод прогнозирования, описанный ранее в этом разделе. Через один такт времени мы переходим в состояние 1 с вероятностью ра, в противном случае остаемся в состоянии О.
Сосшолнне 1. С7 — 1 буферов пусты. Начинаем выполнять чтение в один из них, предсказывая подходящий файл. Через один такт времени переходим в состояние 2 с вероятностью рв, в состояние 1 с вероятностью р~ и в состояние О с вероятностью р>ш Состояние О. — 1. Один буфер пуст, Начинаем выполнять чтение в него, предсказывая подходящий файл. Через один такт времени переходим в состояние с7 с вероятностью рэ, в состояние О.
— 1 с вероятностью р,, ..., в состояние 1 с вероятностью рд 1 и в состояние О с вероятностью р>о. Состояние О. Все буфера заполнены. Чтение лент останавливается в среднем на р тактов времени, и затем мы переходим в состояние Я вЂ” 1. Начинаем с состояния О. Модель этой ситуации соответствует марковскому процессу (см.
упр. 2.3.4.2 — 26), который можно проанализировать с помощью производящих функций следующим интересным способом. Пусть в — произвольный параметр, и предположим, что каждый раз, когда мы решаем осуществлять чтение с ленты, делаем это с вероятностью -, а с вероятностью 1 — х завершаем выполнение алгоРитма. ПУсть дд(а) = 2 „>е а~~~в" (1 — г) — — сРеднее число поЯвлений в этом процессе состояния ф отаода следует, что а~'7~ — это среднее число появлений состояния Я, если было прочитано ровно и блоков.
Тогда и + а1®)г —. среднее суммарное время, затраченное на ввод и вычисления. Если бы имелось полное совмещение, как в алгоритме с (2Р + 2) буферами, то суммарное время включало бы только и единиц, так что а)О))г представляет время задержки чтения. Пусть АΠ— вероятность того, что мы переходим из состояния г в состояние г в этом процессе при 0 < г,г' < Я + 1, где Я + 1 — новое состояние 'остановки". Например, при малых Я матрицы А будут следующими: Р>г» Ро» Я=1; 1 О 0 0 0 0 ро» 0 Рг» Ро» 1 0 0 0 Р>г» Р>г» 0 0 1 †» 0 0 Из упр.
2.3.4.2 — 26(Ь) имеем, что дс) (») = согасооггуо(г' — А)/с1ег(1 — А). Так, например, если Я = 1, имеем 0 — Ро»» — 1 / 1 — Р>㻠— Ро»» — 1 дг(») = йео 1 0 0 /с$еС вЂ” 1 1 0 ~~ | ~ ~ ~ ~ ~ ~ ~ » ~ | ,0 0 1 0 0 1 — — иро» (1 — »), Ро» Ро» 1 — Р㻠— Ро» 1 — » так что а„= иро. Это, конечно, очевидно заранее, так как при Я = 1 задача очень проста. Аналогичное вычисление для 1З = 2 (см. у.пр.
14) дает менее очевидную формулу: (г) Рои РО(1 Р! ) (10) 1-Р, (1-Р,)г ' В общем случае можно показать, что ай имеет вид ано)и + 0(1) при и — > оо, где константу а1® не слишком трудно вычислить (см. упр. 15). Как оказывается, а1 ) = Ро/((1 — Рг)' — Рор ). Исходя из природы слияния, довольно разумно предположить, что Р = 1)Р, и мы имеем биномиальное распределение Р>г» Р>г» Р>г» 0 0 Ро» 0 0 1 — » Р» Ро» О 1 — » Рг» Рг» Ро» 0 1 0 0 0 0 0 О Например, ешги Р = 5, то ро —— .32768, рг —— .4096, рг — — .2048, рз = .Оо12, рг — — .0064 и р = .00032; следовательно, о('> - 0,328, а~ ) — 0.182 и а( ) — 0.125.
Другими словами, если мы используем 5+ 3 вводных буферов вместо 5+ 5, то можно ожидать дополнительного времени "задержки чтения" порядка 0.12575 2.огхш Конечно, эта модель -- только очень грубое приближение, Мы знаем, что при Я = Р вообще нет времени задержки, но если судить по модели, то есть. Дополнительное время задержки чтения для меньших Я почти точно уравновешивает выигрыш в накладных расходах, получаемый от использования более крупных блоков, так что выбор простой схемьг с б) = Р кажется оправданным.
УПРАЖНЕНИЯ 1. [12] Выведите формулу для вычисления точного числа символов на ленте, если в каждом блоке содержится и символов. Считайте, что лента могяа бы вместить ровно 23 000 000 символов, если бы не было междублочных промежутков. 2. [15] Объисните, почему первый буфер файла 2 в строке 6 на рис. 84 совсем пуст. 3. [20] Будет ли алгоритм Г работать должным образом, если вместо 2Р буферов ввода имеется только 2Р— 1? Если да, докажите это; если нет, приведите пример, когда алгоритм не выполняется. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
