AOP_Tom3 (1021738), страница 196
Текст из файла (страница 196)
ОЗ.[Добавить единицу.( Если 1 = 1, остановиться; результат находится на ленте ( — В)що41 т в порядке возрастания тогда и только тогда, когда ь четно. В противном случае установить АИ 4- А[П + 1, д 4- (д + 1)шоч( Т. О4. (Перенос?) Если АБ] ( Р, то вернуться к шагу 02. В противном случае выполнить слияние на ленту (д — 1) шог[Т, установить АП] 4- 0 и д 4 — (д + 1) шоч( Т, увеличить 1 на 1 и вернуться к шагу 03.
3 2. Следите за числом серий на каждой ленте. Когда исходные данные будут исчерпаны, добавляйте, если необходимо, фиктивные серии, пока не придете к такому положению, когда на каждой ленте будет находиться максимум одна серия и по крайней мере одна лента не будет занята. Затем завершите сортировку посредством еще одного слияния, перемотав сначала некоторые ленты, если это необходимо.
(Ориентацию серий можно извлечь из массива А.) 3. Операция ТО Т1 Операция Т1 Распределение — Аг Распределение Аг Слияние Вг Слияние Распределение РгАг Слияние — Ач Слияние Вг Рг — Распределение — Ач Распределение Рг РгАг Аг Копирование — А4Рг Слияние Р, Рг Рг — Копирование — Ач Слияние Рг — Ач Слияние Вэ В этот момент Т2 можно перемотать — - и окончательное слияние завершит сортировку. Чтобы избежать бесполезных операций копирования, при которых серии просто сдвигаются вперед или назад, можно в конце шага ВЗ просто сказать "Если исходные данные исчерпаны, перейти к В7" и добавить новый шаг.
В7. [Завершение.[ Установить э е- — 1 и перейти к В2 после повторения следующей операции до тех пор, пока 1 = 0 Установить в' +- АП вЂ” 1,4) и установить д' и г' равными индексам, таким, что АП вЂ” 1, д'] = -1 и АУ вЂ” 1, г'] = — 2. (Мы получим д' = г и э' < АУ вЂ” 1, Я < э' + 1, 1 ЭА д~, ) ф г'.) Если э' — э нечетно,продвинугь уровень 1, в противном случае — откатить его (см. ниже), Затем выполнить слияние на ленте г,читая в обратном порядке; установить 1 г- 1 — 1, А У,4] +- — 1, А У,г) г- э' + 1, г +- с~и повторить.
Здесь "продвижение" означает повторение следующей операции до тех пор, пока (О -~- (-1)*) шод Т = г: установить р +- (4+ ( — 1)') шоб Т и скопировать одну серию с ленты р на ленту 1, затем установить А П, е) е- э+ 1, А [1, р) г — — 1, о р. "Откат" уровня означает повторение следующей операции до тех пор„пока (4 — (-1)') шог) Т = г. установить р г — (4 — ( — 1)') шос) Т и скопировать одну серию с ленты р на ленту д, затем установить А П1, О] э- э, А П, р) +- — 1, д е- р. Нри операции копирования чтение с ленты р выполняется в обратном направлении, в результате чего направление копируемой серии изменится на противоположное.
Если окажется, что при копировании с р на е В[р[ > О, то нужно вместо копирования просто уменьшить 11[р[ и увеличить В[у[. (Основная идея состоит в том, что, если входнью данные исчерпаны, желательно исключить, по крайней мере, по одной серии на каждой ленте. Разряд четности каждого неотрицательного элемента А У, Я укажет, является ли серия восходящей или нисходящей. Наименьшее Я, при котором изменение алгоритма хоть как-то сказывается, есть Р + 1. Если Р велико, такое изменение вряд ли когда-нибудь вызовет большое расхождение, но оно позволит компьютеру не выглядеть слишком глупо при некоторых обстоятельствах.
Однако и этот алгоритм можно еще дорабатывать, чтобы более эффективно обрабатывался случай Я = 1,) 4. На самом деле можно опустить установку А(0,0) на шаге В1 и АП, д) на шагах ВЗ и В5. (Однако А П, г) должно устанавливаться на шаге ВЗ.) Новый шаг В7 в ответе к предыдущему упражнению требует значение А У, д) (если только в явном виде не учитывает, что д' = г, как отмечается в указанном ответе). 5. Реь — (Р— 1)Ры ~ < л < Р'~ при некотором )г > О.
РАЗДЕЛ 5.4.6 1. [23000480/(и + 480)] и. 2. В этот момент все записи правого буфера переданы на вывод. На шаге Р2 во время слиянии проверка "Полон ли буфер вывода?" предшествует проверке "Пуст ли буфер ввода?"; это существенно, иначе пришлось бы ввести дополнительные проверки (егли не внести изменения, как в упр 4).
3. Нет. Например, мы могли бы достичь состояния, в котором Р буферов заполнены на ЦР и Р— 1 буферов полны, если бы в файле 1 находились ключи 1, 1+ Р, 1 + 2Р, ... при 1 < 1 < Р. Этот пример показывает, что, даже если разрешить одновременное чтение, необходимо иметь 2Р буферов ввода для поддержания непрерывного выиода, если только мы не перераспределяем память для частей буферов и не используем каким-либо образом "чтение вразброс". [Вообще говоря, если в блоках содержится меньше Р— 1 записей, требуется меньше 2Р буферов, но атот случай маловероятен.] 4.
Раньше устанавливать Б (на шагах Р1 и Р4, а не РЗ). 5. Если бы, например, все ключи во всех файлах были равны, то мы не могли бы просто делать произвольный выбор во время прогнозирования; прогноз должен быть совместим с решениями, принимаемыми процессом слияния. Возможный безопасный путь состоит в том, чтобы найти на шагах Е1 и г 4 наименьшее возможное пз, т. е. считать, что все записи из файла С(») меньше, чем все записи, имеющие тот же ключ в файле С(Я, если в <,у. (В сущности, номер файла присоединяется к ключу.) 6. На»лаге С1 установить также ТАРЕ [Т+ Ц»- Т-Ь 1. На шаге С8 слияние должно идти на ТАРЕ[р+2) вместо ТАРЕ[у+ Ц.
На шаге С9 установить (ТАРЕП),...,ТАРЕ[Т+Ц)»- (ТАРЕ [Т+ Ц,..., ТАРЕ [Ц ) . 7. Метод, показанный на диаграмме А, есть (Л»В») АоРв(А»Р») ЛвВв(А»Р») Ае, Р»(А»Р»)~АвРв(А»Р») АаРеоАаВвАе, Р» АеРо(А» Р» ) АвРвоА» Р» Ае, Р» А» Р» пА»Р»Ав, где п = (АвРв) Л»Р»АеРв(А»Р») (АвРе)"А»Р»(ЛеРе) А»Р»АвРе На первой фазе слияния записывается В»А»Р»Л»Р»А»Р»АвРвА»Р»А»Р» А»Р»АвРвА»Р»АвРе(А»Р»)" на ленту 5; на следующей записывается А»Р»А»В»Л»Р» А»Р»АвРеА»Р»А»В»А» иа ленту 1, на следующей — Р»зА»Р»АвРвА»в на ленту 4. Последние фазы таковы А»Р».4» — Р»в Аз Рз А»з А» РззАы Р»вАз Рзз Рш Атв Р» 3.4» Р» А» Р»зА» Р»з РвЛз Рзз 1115, 1296, 1241, 1008, 1014, 967, 891, 969, 856.
12. (а) Очевидное решение с 4Р+ 4 буферами состоит в том. чтобьа просто одновременно выполнять чтение и запись яа спаренные ленты. Заметим, однако, что достаточно трех буферов вывода (в любой момент мы выполняем вторую половину операции записи из одного, первую половину операции записи из второго и заполняем третий). Это наводит на мысль о соответствующем улучшении ситуации с буферами ввода. Оказывается, что 8. Нет, так как чкономится самое большее о стартстопных операций, и, кроме того, время начального распределения, в основном, зависит от скорости обработки вводной ленты (а не выводных лент).
Другие преимущоства схем распределения, приведенных на диаграмме А, компенсируют зтот незначительный недостаток 9. Р = 5, В = 8300, В' = 734, Я = ((3 -Ь 1/Р)57/(6Р') (+ 1 = 74, ы 1.094, о — 0.795, /5 ш — 1.136, и' = /1' = О. Значение формулы (9) — 855 с, к которому мы добавляем время начальной перемотки, получая в итоге 958 с. Экономия прил»ерно одной минуты во время слияния не компенсирует потерю времени из-за начальной перемотки и смены ленты (если мы не работаем в мультипрограммном режил»е) 10.
Во время стандартного многофазпого слияния перематывается около 54% файла (столбец "Проходы/фазы" в табл. 5.4.2- 1), а самая длинная перемотка в стандартном каскадном слиянии охватывает примерно ава в/а„(4/(2Т вЂ” 1)) созе(л/(4Т вЂ” 2)) ч»» файла (из упр. 5.4.3-5 и соотношения 5 4.3 — (13)). 11. Только для начальной и конечной перемоток имеет смысл использовать быструю перемотку, так как бобина, содержащая весь файл примера, заполнена лишь немногим более чем на 10/23.
Применяя в примере 8 значения х = (.946 !по — 1.204) и л' = 1/8, получаем следующие итоговые оценки для примеров 1-9: необходимо и достаточно ЗР буферов ввода и 3 буфера вывода, если использовать несколько ослабленный метод "прогиозирования3 Лучший и более простой подход, предложенный Дж. Сю (3. Бпе), позволяет добавить к каждому блоку "опережающий ключ", который определяет последний ключ следующего блока. Метод Сю требует 2Р + 1 буферов ввода и 4 буфера вывода и является видоизмененным алгоритмом Г. (См.
также раздел 3.4тп) (Ь) В этом случае большое значение и означает, что число проходов по всем данным, которое мы должны выполнить, лежит между пятью и шестью, что сводит на нет преимущество слияния с двойной скоростью. Эта идея значительно лучше работает на восьми или девяти лентах. 13. Нет. Рассиотрите, например, положение непосредственно перед АооАшАыАш. Однако две полные бобины могугл быть обработаны.
О -рог О 14 с)е О 1 — Р~х Рог 1 О О О О О 1 1 — р>~х -рог О х — 1 г — 1 / — р>гх 1 — рох — рог г — 1 О /" О-1 1 О 1 О О О 1 13. Матрица А имеет вид В~ох Виг .. В~го 1 — х В~о+Вп+ +Вы =1, В +В„+ +В„„=1 Вьог Вггх ... Вг„г 1 — г О - О 1 О О О .. О О О О Следовательно, 1 — В,ох -Внг ... — Вцг Ох — Вь г 1 — в„<„В» -в.. — 1 1 с(ег(1 — А) = де» вЂ” В ог — В„~» О О и можно прибавить все столбцы к первому, а затем вынести (1 — г).