AOP_Tom3 (1021738), страница 90
Текст из файла (страница 90)
[20] Как изменить алгоритм Р, чтобы он работал и при Р = 1? б. [21] Если в различных файлах имеются равные ключи, необходимо в процессе прогнозирования действовать очень аккуратно. Объясните, почему Покажите, как избежать трудностей, если болев строго определить операции слияния и прогнозирования в алгоритме Г. 6. [22] Какие изменения нри работе с Т+ 1 лентами следует сделать в алгоритме 5,4.3С, чтобы преобразовать его в алгоритм каскадного слияния с совмсщеняем псреэштхи? 7. [20] Начальное распределение в примере 7 диаграммы Л порождает (Агрг)" Рг(Агрг)ш Вг(Агрг)э Вг(дгВг)г на лентах 1 — 4, где (Агрг) означает.4гргАгргдгргАгргдгргдгргдгрг.
Покажите, как вставить дополнительные серии Ааи Вэ наилучшим из возможных способов (в том смысле, что общее число обрабатываемых во время слияния начальных серий будет минимальны и), чтобы привести распределение к следующему виду: 4(р 4)ы (рд)гэ (Рд)ге (рд)гг Указание. Чтобы сохранить четность, необходимо вставлять серии Ао и Вэ в виде соседних пар.
Числа слияния для каждой начальной сории могут быть подсчитаны, как в упр. о.4.4 — 5; здесь появляется некоторое упрощение, так как соседние серии всегда имеют соседние числа слияния. 8. [20] На диаграмме А видно, что большинство схем начального распределения серий (за исключением начального распределения для каскадного слияния) имеет тенденцию к помещению последовательных серий на различные ленты. Если бы последовательные серии попали на одну ленту, то мы могли бы сэкономить стартстопное время. Можно лн поэтому считать продуктивной идею изменения алгоритмов распределения так, чтобы они реже переключали ленты? 9. [22] Оцените.
сколько времени 'заняло бы выполнение многобгазного алгоритма с обратным чтением из показанных на диаграмме А, если бы для сортировки использовались все Т = 6 лент, а не Т = 5, как в примере 7 Было ли разумно избегать использования вводной ленты? 13. [80] Может ли метод осциллируквцей сортировки с пятью лентами в том виде, в котором он определен в алгоритме 5 4.5В, использоваться для сортировки четырех полных бобин исходных данных до момента окончательного слияния? 14. [М19] Выведите [10).
15. [НМ89] Докажите, что дп[г) = Ьо[з)/[1 — з), где НО[з) является рациональной функцией з, не имеющей особых точек внутри единичного круга; следовательно, а = Йо(1)п+ (ос 0(1) при и -+ оо. В частности, покажите, чэо 0 — ре )сз[1) = с)ег 0 1 — рс 0 — рэ 1 0 0 0 1 — ро 0 0 -ро 0 / 1 1-рс -ра 0 суес 1-р~ -ро ?с 1 -рэ 1-рс -ре 0 0 0 0 — 1 1 16. [41] Детально изучите сортировку 100„000 записей по 100 символов, нарисуйте диа- граммы, подобные диаграмме А, в предположении, что имеется 3, 4 и 5 лент. *5.4.7. Внешняя поразрядная сортировка В предыдущих разделах рассматривалась сортировка методом слияния файлов на лентах.
Но существует и другой способ сортировки на лентах, основанный на принципе поразрядной сортировки, который ранее использовался в механических сортировальных машинах для перфокарт [см. раздел 5.2.5). Этот метод иногда называют распределяющей сортировкой., сортировкой по колонкам, карманной сортировкой, цифровой сортировкой, сортировкой методом разделения и т. д. Он, как оказывается, по существу, протиеополозссен слиянию! Предположим, например, что в нашем распоряжении имеются четыре ленты, а ключей может быть только восемь: О, 1, 2, 3, 4, 5, б, 7.
Если исходные данные 10. [М80] Используя анализ, проведенный в разделах 5.4.2 и 5.4.3, покажите, что длина каждой перемотки во время стандартного многофазпого слияния с шестью лентами или каскадного слияния редко превышает 54% длины файла [исключая начальную и конечную перемотки, которые охватывают весь файл). 11. [83] Откорректировав ссютветствующие элементы табл. 1, оцените, сколько времени заняло бы выполнение первых девяти примеров на дваграмме А, если бы мы имели двухскоростную перемотку [быструю и лседленную). Считайте, что р = 1, если лента заполнена меньше чем на одну четвертач а для более заполненной ленты время перемотки равно приблизительно 5 с плюс то время, которое получилось бы при р = —.'. Измените прилгер 8 так, чтобы в нем использовююсь каскадное слияние с копированием, поскольку перемотка и прямое чтение в этом случае происходят медленнее копирования.
[Указание. Используйте результат упр. 10.] 12. [40] Рассмотрим разбиение шести лент на три пары лент, где каждая пара играет роль одной лгзсты в многофазном слиянии с Т = 3. Одна лента каждой пары будет содержать блоки 1, 3, 5,..., а другая — блоки 2, 4, 6,., .; таким способом мы, по существу, добиваемся того, чтобы во все время слияния две вводные и две выводные ленты оставались активными, причем эффективная скорость слияния удваивается. а) Найдите подходящий способ распространения алгоритма Г на этот случай. Ь) Оцените общее время выполнения, которое получилось бы, если бы этот метод использовался для сортировки 100,000 записей по 100 символов, рассмотрев случаи как прямого, так и обратного чтения. содержатся на ленте Т1, то начнем с переписи всех четных ключей на ТЗ и всех нечетных — на Т4.
Т2 Т1 (0,1,2,3,4,5,6,7) ТЗ Т4 Дано Проход 1 (0,2,4,6) (1,3,5,7) Теперь перематываем ленты и читаем сначала ТЗ, а затем — Т4, переписывая (О, 1,4,5) наТ1и (2,3,6,7) наТ2. (2, 6) (3, 7) Проход 2 (0,4Ц1,5) (Строка "(0,4Ц1, 5)" обозначает файл, содержащий записи только с ключами 0 и 4, за которыми следуют записи только с ключами 1 и 5. Заметим, что на Т1 теперь находятся те ключи, средний двоичный разряд которых содержит О.) После еще одной перемотки и распределения ключей О, 1, 2, 3 на ТЗ и ключей 4, 5, 6, 7 на Т4 получаем следующее.
(ОЦ1Ц2ЦЗ) (4)(5Ц6Ц7) Проход 3 После копирования Т4 в конец ТЗ рабата завершается. В общем случае для ключей в диапазоне от 0 до 2" — 1 можно аналогичным образом рассортировать файл за 1г проходов, после которых следует фаза окончательной "сборки". На этом этапе примерно половина данных копируется с одной ленты на другую. Имея шесть лент, можно так же использовать представления по основанию 3 для сортировки ключей от О до 3" — 1 зал проходов. Существуют модификации этого метода с частичными проходами. Предположим, например, что допускается десять ключей (0,1,...,9), и рассмотрим следующую процедуру, авторство которой принадлежит Р. ЗЬ Эшенхерсту (В.
Ь. АэЬеп1пггэг) [Тйеогу оу Яябгс51п8, Ргойгеээ ВерогС ВЬ-7 (Нагхагб 11шпо Сошр. Ьаоога1огу: Мау, 1954), 1.1 — 1.76~. Т2 ТЗ Т4 Проход Здесь С представляет фазу сборки. Если каждое значение ключа встречается примерно в одном из десяти случаев, то эта процедура для сортировки десяти ключей затрачивает только 2.8 прохода, в то время как в первом примере требуется 3.5 прохода для сортировки всего восьми ключей.
Таким образом, продуманая схема распределения влечет за собой значительное различие в показателях эффективности для поразрядной сортировки точно так же, как для слияния. Схемы распределения из предыдущих примеров представим, как и обычно, древовидными структурами. Фаза Т1 (0,1,...,9) 1 2 (0) 3 (ОЦ1Ц2) 4 (ОЦ1Ц2ЦЗ) С (ОЦ1Ц2) (ЗЦ4)... (9) (0,2,4,7) (1,5,6) (3,8,9) — (1, 5, 6) (2, 7) (3, 8, 9) (4) (6Ц7) — (3, 8, 9Ц4Ц5) (6Ц7Ц8) (9) (4Ц5) 1.0 0.4 0.5 0.3 0.6 2.8 Пример 1 Пример 2 4 6 в т 7 Круглые внутренние узлы этих деревьев пронумерованы 1, 2, 3, ... в соответствии с шагами процесса 1, 2, 3, .... Имена лент А, В, С, В (вместо Т1, Т2, ТЗ, Т4) помещены рядом с ребрами дерева, чтобы указать, нуда попадают записи. Квадратные внешние узлы изображают фрагменты файла, содержащие только один ключ, и этот ключ выделен полужирным шрифтом под соответствующим узлом.
Ребра, расположенные над квадратными узлами, помечены именем выводной ленты (С в первом примере, А — во втором). Таким образом, на шаге 3 примера 1 выполняется считывание с ленты О н запись ключей 1 и 5 на ленту А и ключей 3 и 7 на ленту В. Нетрудно видетгь что число выполняемых проходов равно длине внешнего пути дерева, деленной на число внешних узлов в предположении, что все ключи равновероятны.
В свизн с последовательной природой ленты и в соответствии с пранилом 'первым включается — первым исключается", которому подчиняетгя прямое чтение, нельзя взять за основу схемы распределения любое помеченное дерево. В дереве примера 1 данные записываются на ленту А на шагах 2 и 3; данные, записанные в течение шага 2, необходимо использовать раньше данных, записанных в течение шага 3.
В общем случае, если осуществляется запись на ленту в течение шагов 1 и 1', где 1 ( у, первыми следует испольэовать данные, записанные в течение шага й Ксли дерено содержит две ветви нида л л, г<з, то должно выполняться условие к с 1. Кроме того, нельзя ничего записывать на ленту А между шагами к и 1, поскольку между чтением и записью необходима перемотка. Те читатели, которые внимательно проработали упражнения из раздела 5.4.4, сразу поймут, что допустимые деревья для поразрядной сортировки с прямым чтением на Т лентах — это в точности сильные Т-Яо-деревья, описывающие сортировку методом слияния на Т лентах с прямым чтением! (См. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
