AOP_Tom3 (1021738), страница 78
Текст из файла (страница 78)
9. [НМ26] Выведите формулы (14). ь 10. [МЯЭ] Вместо системы (4) для изучения каскадных чисел воспользуйтесь в качестве исходных тождествами *5.4.4. Чтение ленты в обратном направлении Т2 ТЗ Т4 Т1 А~А1А~А1 А~А1А|А1 Начальное распределение Слияние на ТЗ и Т4 Слияние на Т1 и Т2 Окончательное слияние на ТЗ Проход 1 Пр д2 Проход 3 Проход 4 Р2Р2 Р2Рг Аа Здесь А„обозначает серию, имеющую относительную длину г и расположенную в порядке возрастания, если лента читается в прямом направлении, как в предыдущих примерах; Є— аналогичное обозначение для нисходящей серии длиной г.
Во время второго прохода восходящие серии становятся нисходящими. Они оказываются нисходящими при вводе, так как мы читаем ленты Т1 и Т2 в обратном направлении. Серии вновь изменяют ориентацию на третьем проходе. Заметим, что описанный процесс завершается формированием на ленте ТЗ результата в порядке убмаания. Если это плохо (что зависит от того, должен ли результат читаться в обратном направлении или же лента, содержащаи ега, должна быть снята и отложена для использования в дальнейшем), можно скопировать его на другую ленту, изменив направление.
Более быстрым способам была бы перемотка Т1 и Т2 после третьего прохода; при этом во время четвертого прохода получается Аг. Еще лучше было бы начать с восьми нисходящих серий на первом проходе, так как при этом поменялись бы местами все А и Р. Однако для сбалансированного слияния 16 начальных серий потребовалось бы, чтобы начальные серии были восходящими, на поскольку обычно заранее неизвестно, сколько начальных серий будет Многие накопители на магнитных лентах позволяют читать ленту в направлении, противоположном тому, в котором осуществлялась запись. Рассмотренные ранее схемы слияния предполагают запись информации на ленту в прямом направлении, перемотку ленты, ее чтение в прямом направлении и еще одну перемотку. (Файлы на ленте, следовательно, ведут себя, как очереди "первым включается — первым исключается".) Чтение в обратном направлении (в дальнейшем будем для краткости называть эту операцию обратным чтением) позволяет обойтись без перемотки: запись на ленту выполняется в прямом направлении и считывается в обратном.
(В этом случае файлы ведут себя, как стеки, поскольку здесь действует правило "последним включается — первым исключается".) Схемы сбалансированного, многофазного и каскадного слияний можно приспособить для обратного чтения. Основное отличие состоит в том, что слияние измгняегп порядок серий, если считывание происходит в прямом направлении, а запись — в обратном.
Если две серии находятся на ленте в порядке возрастания, то их можно слить, выполняя считывание в обратном направлении, однако при этом серии расположатся в порядке убывания. Полученные таким образом нисходящие серии станут восходящими на следующем проходе; следовательно, алгоритм слияния должен уметь работать с сериями обоих направлений. Программисту, впервые столкнувшемуся с обратным чтением, может показаться,что ан стоит на голове! В качестве примера обратного чтения рассмотрим процесс слияния восьми начальных серий с использованием сбалансированного слияния на четырех лентах. Записать наши действия можно следующим образом.
образовано, необходимо выбрать одно постоянное направление. Следовательно, идея перемотки после третьего прохода является наилучшей. Хаскадное слияние преобразуется таким же способом. Рассмотрим, например, сортировку 14 начальных серий на четырех лентах. Т4 Т1 ТЗ Т2 Проход 1 Проход 2 Проход 3 Проход 4 АзАы4,АзАзАа А,АзАзАзАа Ра Аз АаАаАа РзРз Аз РзРзРз Аз Ры Как и ранее, можно получить Аза вместо Рза, если перемотать Т1, Т2, ТЗ непосредственно перед последним проходом.
Заметим, что это "чистое" каскадное слияние в том смысле, что все однопутевыс слияния выполнены явным образом. Если бы мы запретили операции копирования, как в алгоритме 5.4.3С, то после второго прохода столкнулись бы с ситуацией А, РзРзРз Рз Рз В этом случае невозможно продолжать работу, используя трехпутевое слияние, так как нельзя сливать серии противоположных направлений! Можно было бы избежать копирования Т1 на Т2, если перемотать Т1 и начать ее считывание в прямом направлении на следующей фазе слияния (в то время как ТЗ и Т4 читаются в обратном направлении).
Но тогда пришлось бы вновь перемотать Т1 после слияния, так что данный прием заменяет одно копирование двумя перемотками. Таким образом, метод распределения алгоритма 5.4.ЗС при обратном чтении не столь эффективен, как при прямом чтении; временные затраты резко возрастают каждый раз, когда число начальных серий проходит через "точное" каскадное распределение. Чтобы получить более "гладкий" переход между точными каскадными распределениями, можно использовать иной метод распределения (см. упр.
17). ТЗ Т2 Т1 Фаза 1 Фаза 2 АзАзАзАзАз АзАзАзАзАзАзАзАз А,АаА! Рз Р2Рз~ ~зР2 Здесь мы оказываемся в тупике; можно было бы перемотать Т2 или ТЗ и затем читать их в прямом направлении, в то время как остальные ленты — в обралюм. Но это значительно запутало бы дело и преимущества от обратного чтения были бы невелики. Остроумный выход из сложившейся ситуации состоит в том, чтобы чередовать каправленин серий на каждой левше. Тогда слияние может происходить вполне согласовано. Обратное чтение в многофаэном слиянии.
На первый взгляд (и даже на второй и третий), схема многофазного слияния кажется совершенно неподходящей для обратного чтения. Предположим, например, что имеется 13 начальных серий и три ленты. Т1 А,Р,АзРзЛз Р,Л,Р,А,Р,Л,Р,А, РзАзР1 Фаза 1 Фаза 2 Фаза 3 Фаза 4 Фаза 5 Фаза 6 РгАзРгАзРз РзАз АзРзЛз .4з РзАз Рз Рз Лзз Окончательная выводная лента Т1 Т2 ТЗ Т4 Т5 Сумма 1 0 0 О 0 1 1 2 2 2 2 9 3 4 4 4 2 17 7 8 8 6 4 33 15 16 14 12 8 65 31 ЗО 28 24 16 129 61 120 116 108 92 497 Уровень 0 2 3 5 6 8 Т1 Т1 Т1 Т1 (1) Т1 Т1 Т1 Таким образом, на Т1 всегда помегцаетгя нечетное число серий, тогда как на ленты с Т2 по Т5 — четные числа (в порядке убывания, чтобы упростить присвоение фиктивных серий).
Такое распределение имеет то преимущество, что окончательная выводная лента известна заранее независимо от числа начальных серий, которые придется обрабатывать. Оказывается (см. упр. 3), что если используется зта схема, то результат всегда будет находиться на Т1 в порядке возрастания. Этот принцип был кратко упомянут Р.
Л, Гилстадом (11. Е. Сйззаб) в его ранней статье о многофазном слиянии. Более полное описание приводится в САСМ 6 (1963), 220-223. Рассматриваемый ЛРА...-метод прекрасно подходит для многофазного слияния с любым числом лент; можно показать, что А и Р согласуются соответствующим образом на каждой фазе, но талька при условии, что на начальном проходе чередующиеся серии Л и Р должны быть сформированы на каждой ленте и что каждая лента заканчивается серией А (или каждая лента заканчивается серией Р).
Так как последняя серия, записываемая в файл вывода во время одной фазы, имеет направление, противоположное направлению последней использованной серии из файла ввода, то и на следующей фазе серии всегда будут иметь надлежащую ориентацию. Далее, как в упр. 5.4.2 — 13, большинство точных фибоначчиевых распределений требует нечетного числа серий на одной ленте (окончательной выводной ленте) и четного числа серий на всех остальных лентах.
Если Т1 предназначена для вывода конечного результата, значит, можно гарантировать, что все ленты будут заканчиваться серией .4, если ленту Т1 начнем с Л, а все остальные ленты — с Р. Можно использовать метод распределения, аналогичный алгоритму 5.4.2Р, изменив его таким образом, чтобы распределение на каждом уровне имело в качестве выводной ленту Т1. (Мы пропускаем уровни 1, Т+1, 2Т+1, ..., так как на них окончательной выводной лентой является первоначально пустая лента.) Например, в случае для шести лент вместо 5.4.2-(1) можно испачьзовать следующее распределение серий.
Другой способ распределения для многофазной схемы с обратным чтением был предложен в статье Р. Т. Ооос1вчп, Я. 1.. депп, САСМ Т (1964), 315. Можно распределять серии, почти как в алгоритме 5.4.2Р, начиная с Р-серии на каждой ленте. Когда ввод исчерпан, мы представляем себе фиктивную А-серию расположенной в начале единственной "нечетной" ленты, если только не достигнуто распределение со всеми нечетными числами. Остальные фиктивные серии мы представляем себе расположенными в конце лент или сгруппированными в пары в середине. Вопрос об оптимальном размещении фиктивных серий анализируется ниже, в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
