Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 79
Текст из файла (страница 79)
1, сравните каскадное слияние с описанной в разделе 54.2 версией мяогофазного слияние с "расщеплением лент". Какой метод лучше? (Временем перемотки пренебречь.) 2. [22] Сравните метод каскадной сортировки с тремя лентами, использующий алгоритм С, н метод многофазной сортировки с тремя лентами, использующий алгоритм 5.4.20. Какие сходства н различия вы заметите? 3. [ЙЗ] Составьте табшщу, показывающую„что происходит при сортировке на шести лентах ста начальных серий при помощи алгоритма С.
4. [Ьгйр] (Дж, Н. Райки (С. 1Ч. Навеу).) "Каскадное распределение и-го уровня" муаьтимножество, определенное следующим образом (длв шести лент): (1,0, 0,0, 0) есть каскадное распределение 0-го уровня; если на последующих уровнях (о, Ь, с, И, е) — каскадное распределение и-го уровня, го (а+Ь+с+И+е, а+5+с+Ы, а+6+с, а+Ь, а) будет каскадным распределением (я+ 1)-го уровня. (Так как мульткчножество не упорядочено, «5.4.4. Чтение ленты е обратном направлении Т1 Т2 ТЗ Т4 Проход 1 А1А1АгА~ А~А~А1А1 Проход 2 Проход 3 А« А4 Проход 4 Начальное распределение Слияние на ТЗ и Т4 Слияние на Т1 и Т2 Окончательное слияние на ТЗ х)з 1У2 .0« Здесь А„обозначает серию, имеющую относительную длину г и расположенную в порядке возрастания, если лента читается в прямом направлении, как в предыдущих примерах; Ю,. — аналогичное обозначение для нисходящей серии длиной г.
Во время второго прохода восходящие серии становятся нисходящими. Опи оказываются нисходящими при вводе, так как мы читаем ленты Т1 и Т2 в обратном направлении. Серии вновь изменяют ориентацию на третьем проходе. Заметим, что описанный процесс завершается формированием на ленте ТЗ результата в порядке убивания. Если это плохо (что зависит от того, должен ли результат читаться в обратном направлении или же лента, содержащая его, должна быть снята и отложена для использования в дальнейшем), можно скопировать его на другую ленту, изменив направление. Более быстрым способом была бы перемотка Т1 и Т2 после третьего прохода; при этом во время четвертого прохода получается Аэ. Еще лучше было бы начать с восьми нисходящих серий на первом проходе, так как при этом поменялись бы местами все А и;О. Однако для сбалансированного слиянии 16 начальных серий потребовачось бы, чтобы начальные серии были восходящими, но поскольку обычно заранее неизвестно, сколько начальных серий будет Многие накопители на магнитных лентах позволяют читать ленту в направлении, противоположном тому, в котором осуществлялась запись.
Рассмотренные ранее схемы слияния предполагают запись информации на ленту в прямом направлении, перемотку ленты, ее чтение в прямом направлении и еще одну перемотку. (Файлы на ленте, следовательно, ведут себя, как очереди "первым включается — первым исключается".) Чтение в обратном направлении (в дальнейшем будем для краткости называть эту операцию обратным чтением) позволяет обойтись без перемотки: запись на ленту выполняется в прямом направлении и считывается в обратном. (В этом случае файлы ведут себя, как стеки, .поскольку здесь действует правило 'последним включается — первым исключается".) Схемы сбалансированного, многофазного и каскадного слияний можно приспособить для обратного чтения. Основное отличие состоит в том, что слияние иэженлеш порядок серий, если считывш~ие происходит в прямом направлении, а запись — в обратном. Если две серии находятся на ленте в порядке возрастания, то их можно слить, выполняя считывание в обратном направлении, однако при этом серии расположатся в порядке убывания, Полученные таким образом нисходящие серии станут восходящими на следующем проходе; следовательно, алгоритм слияния должен уметь работать с сериями обоих направлений.
Программисту, впервые столкнувшемуся с обратным чтением, может показаться, что он стоит на голове! В качестве примера обратного чтения рассмотрим процесс слияния восьми начальных серий с использованией оба«ансар«ванного слияния на четырех лентах. Записать наши действия можно следующим образом. образовано, необходимо выбрать одно постоянное направление.
Следовательно, идея перемотки после третьего прохода является наилучшей. Каскадное слияние преобразуется таким же способом. Рассмотрим, например, сортировку 14 начальных серий на четырех лентах. Т1 А~ А~ Ам4~ А~ А~ Ае Т2 А~А~А~А~А~ В~ А ТЗ А~А~А~ ВЮт Аз Т4 Проход 1 Проход 2 Проход 3 Проход 4 0зВз22з Как и ранее, можно получить Аы вместо Вы, если перемотать Т1, Т2, ТЗ непосредственно перед последним проходом.
Заметим, что это 'чистое" каскадное слияние в том смысле, что все однопутевые слияния выполнены явным образом. Если бы мы запретили операции копирования, как в алгоритме 5,4.ЗС, то после второго прохода столкнулись бы с ситуацией 0зВэ1Ээ В этом случае невозможно продолжать работу, используя трехпутевое слияние, так как нельзя сливать серии противоположных направлений! Можно было бы избежать копирования Т1 на Т2, если перемотать Т1 и начать ее считывание в прямом направлении на следующей фазе слияния (в то время как ТЗ и Т4 читаются в обратном направлении). Но тогда пришлось бы вновь перемотать Т1 после слияния, так что данный прием заменяет одно копирование двумя перемотками.
Таким образом, метод распределения алгоритма 3.4.3С при обратном чтении не столь эффективен, как при прямом чтении; временные затраты резко возрастают каждый раз, когда число начальных серий проходит через *'точное" каскадное распределение. Чтобы получить более "гладкий" переход между точными каскадными распределениями, можно использовать иной метод распределения (см. упр. 17). ТЗ Т1 Фаза 1 Фаза 2 А~А~А~А~А~ А~А>А~А~А~А~А~А~ А)А)А~ Здесь мы оказываемся в тупике; можно было бы перемотать Т2 или ТЗ и затем читать нх в прямом направлении, в то время как остальные ленты — в обратном, Но это значительно запутало бы дело и преимущества от обратного чтения были бы невелики. Остроумный выход из сложившейся ситуации состоит в том, чтобы череЬеашь направления серий на каждой лемтнс, Тогда слияние может происходить вполне согласовано.
Обратное чтение в многофазвоы слиянии. На первый взгляд (и даже на второй и третий), схема многофазного слияния кажется совершенно неподходящей для обратного чтения. Предположим, например, что имеется 13 начальных серий и три ленты. Тг Т1 А1.01 А1В1 А1 АзЮз 4з Аз А1з П1 А1 П1 А|В1 А1 Ю1 А1 В1 Атй~ и А.
0ь РзАзйзАзйз ЮзАт Х~е Окончательная выводная лента Т1 Т1 Т1 Т1 (1) Т1 Т1 Т1 Т1 Т2 ТЗ Т4 Т5 Сумма 1 О О 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 30 28 24 16 129 61 120 116 108 92 497 Уровень 0 2 3 4 5 6 8 Таким образом, на Т1 всегда помещается нечетное число серий, тогда как на ленты с Т2 по Т5 — - четные числа (в порядке убывания, чтобы упростить присвоение фиктивных серий).
Такое распределение имеет то преимущество, что окончательная выводная лента известна заранее независимо от числа начальных серий, которые придется обрабатывать. Оказывается (см. упр. 3), что если используется зта схема, то результат всегда будет находиться на Т1 в порядке еоэрясгпаиил.
Этот принцип был кратко упомянут Р. Л. Гилствдом (К. Е. 61Ьсаб) в его ранней статье о многофазном слиянии. Более полное описание приводится в САСМ 6 (1963), 220-223. Рассматриваемый .4ПА...-метод прекрасно подходит для многофазного слияния с любмм числом лент; можно показать, что А и В согласуются соответствующим образом на каждой фазе, но только при условии, что на начальном проходе чередующиеся серии А и П должны быть сформированы иа каждой ленте и что каждая лента заканчивается серией А (или каждая лента заканчивается серией П). Так как последняя серия., записываемая в файл вывода во время одной фазы, имеет направление, противоположное направлению последней использованной серии нз файла ввода, то и на следующей фазе серии всегда будут иметь надлежащую ориентацию.
Далее, как в упр. 5.4.2-13, большинство точных фибоначчиевых распределений требует иечегпиого числа серий на одной ленте (окончательной выводной ленте) и чсгпиоеа числа серий на всех остальных лентах, Если Т1 предназначена для вывода конечного результата, значит, можно гарантировать, что все ленты будут заканчиваться серией А, если ленту Т1 начнем с А, а все остальные ленты — с Ю. Можно использовать метод распределения, аналогичный алгоритму 5.4.211, изменив его таким образом, чтобы распределение на каждом уровне имело в качестве выводной ленту Т1. (Мы пропускаем уровни 1, Т+ 1, 2Т+1, ..., так как на них окончательной выводной лентой является первоначально пустая леню.) Например, в случае для шести лент вместо 5.4.2-(1) можно использовать следующее распределение серий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
