Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 90
Текст из файла (страница 90)
Если бы имелось полное совмещение, как в алгоритме с (2Р + 2) буферами, то суммарное время включало бы только и единиц, так что а~'З~ Р представляет время задержки чтения. Пусть Ао — вероятность того, что мы переходим из состояния ( в состояние у в атом процессе при О < 1,у < Д + 1, где ь) + 1 — новое состояние "остановки". Например, при малых 9 матрицы А будут следуюшими: Р>~» Ре» 1 — » О=1: 1 О О а о о Р>1» Р»т» о о Из упр. 2.3.4.2 — 26(Ь) имеем, что Ро(») = со(ассе»Од(1-А))бег(1 — А). Так, например, е:ли ь) = 1, имеем О -Ре»» — 1 / 1 — Р>1» — Ро»» — 1 У1(») = де» 1 О О / бес -1 1 О » ,о о О О Ро» Ре» = — = з про» (1 — »)1 1 — Р1» — Ре» 1 — » ь>0 так что а„= про Это, конечно, очевидно»арене», так как прн Я = 1 задача очень о) проста.
Аналогичное вычисление для Я = 2 (см. упр. 14) дает менее очевидную формулу: ОО Реп Ре(1 Р1) (10) 1-Р1 (1-Рв)» ' в об ~ем .у чо о по а, о(® им д ~о~ +о(1) при и - °, где константу о~'~~ не слишком трудно вычислить (см. упр. 15). Как оказывается, ') = И(1-Р)'- ° .) Псходя из природы слияния, довольно разумно предположить, что л = 1/Р, и мы имеем биномнальное распределение Ро» О 1 — » Р1» Ре» 1 О О о о о Р, о а Р1» Ре» О Р»» Р1» Ро» О 1 О О О О 1-» 1 †1 » 0 о Например, если Р = 5, то Ре = .32768, р! = .4096.
Рз = .2048, рз — — .0512, ра = .0064 и рэ — — .00032„следовательно, а0) — 0.328, а'з) — 0.182 и а(з) 0.125. Другими словами, если мы используем 5+ 3 вводных буферов вместо 5+ 5, то можно ожидать дополнительного времени "задержки чтения" порядка 0.125/5 2.5%. Конечно, зта модель — только очень грубое приближение. Мы знаем, что прн („'3 = Р вообще нет времени задержки, но если судить по модели, то есть. Дополнительное время задержки чтения для меньших Я почти точно уравновешивает выигрыш в накладных расходах, получаемый от использования более крупных блоков, так что выбор простой схемы с Ц = Р кажется оправданным.
УПРАЖНЕНИЯ 1. «13] Выведите формулу для вычисления точного числа символов на ленте, если в каждом блоке содержится и символов. Считайте, что лента могла бы вместить ровно 23 ООО ООО символов, если бы не было междублочных промежутков. 2. «15] Объясните, почему первый буфер файла 2 в строке б на рнс, 84 совсем пуст.
3. [88] Будет лн алгоритм Р работать должным образом, если вмегто 2Р буферов ввода имеется только 2Р— 1? Если да, дгжажите это; если нет, приведите пример, когда алгоритм ие выполняется. 4. «80] Как изменить алгоритм Р, чтобы он работал и при Р = 1? б. «31] Если в различных файлах имеются равные кличи, необходимо в процессе прогнозирования действовать очень аккуратно. Объясните, почему. Покажите, как избежать трудностей, если более строго ипрелелнть операции слияния и прогнозирования в алгоритме р. б. «33] Какие изменения при работе с Т+ 1 лентами следует сделать в алгоритме 5,4,3С, чтобь! преобразовать его в алгоритм каскадного слияния с сова!еп!ением перемотки? 7.
«Об] Начальное распределение в примере 7 диаграммы А порождает (.4,Р,)" Р!(Агп!)' .Р!(АгР!) .Р!(А!Р!) на лентах 1. 4, где (А!Р!)! означает А!Р!А!Р!АгП!А,Р,А,Р А Р!А,Р,. Покажите, как всчввить дополнителыгьге серии Ае и Ро наилучшим нз воз!!ожных способов (в том смыгле, что общее число обрабатываемых во время слияния начальных серий будет минимальным), чтобы привести распределение к следующему виду: А(ПА)" (ПА)" (ПА)" (РА)".
Указание. Чтобы сохранить четность, необходимо вставлять серии Ае и Ре в виде соседних пар. Числа слияния для каждой начальной серии могут быть подсчитаны, как в уор. 5.4.4-о; здесь появляется некоторое упрощение, так как соседние серии всегда имеют соседние числа слияния. 8. «30] На диаграмме А видно, что большинство схем началыюго распределения серий (за исключением нси!ального распределения для каскадного слияния) имеет тенденцию к помещению последовательных серий на различные ленты. Если бы последовательные серии попали на одну ленту, то мы ма~ли бы сэкономить стартстопное время. Можно ли поэтому считать продуктивной идею изменения алгоритмов распределения так, чтобы они реже переключали ленть!? 9.
«88] Оцените, сколько времени заняло бы выполнение мнагофазного алгоритма с обратным чтением из показан!ых на диаграмме А, если бы лля сортировки использовалнсь все Т ж б лент, а не Т = 5, как в примере 7. Было ли разумно избегать использования вводной ленты? 10. [МЯУ] Используя анализ.
проведенный в разделах о.4.2 и 5.4.3, покажите, что длина каждой перемотки во время стандартного многофазного слияния с шестью лентами илн каскадного слияния редко превьппает 54% длины файла (исключая начальную и конечную перемотки, которые охватывают весь файл). 11. [23] Откорректировав соответствующие злементы табл, 1, оцените, сколько времени заняло бы выполнение первых девяти примеров на диаграмме А, если бы мы имели двухскоростную перемотку (быструю и медленную). Считайте, что Р = 1, если лента заполнена меньше чем на одну четверть, а для более заполненной ленты время перемотки разно приблизительно 5 с плюс то время, которое получилось бы при Р = 1.
Измените пример 8 так, чтобы в нем использовалось каскадное слияние с копированием, поскольку перемотка и прямое чтение в зтам случае происходят медленнее копирования, [Указание. Используйте результат упр. 10.] 12. [40] Рассмотрим разбиение шести лент на три пары лент, где каждая пара играет роль одной ленты в многофазном слиянии с Т = 3.
Одна лента каждой пары будет содержать блоки 1, 3, Ь,..., а другая — блоки 2,4, б,...: таким способом мы, по существу, добиваемся того, чтобы во все время слияния лве вводные и две выводные ленты оставались активными, причем зффективная скорость слияния удваивается. а) Найдите подходящий способ распространения алгоритма г на зтот случай. Ь) Оцените общее время выполнения, которое получилось бы, если бы зтот метод использовался лля сортировки 100,000 записей по 100 символов, рассмотрев случаи как прямого, так и обратного чтения.
13. [30] Может ли метод осциллирующей сортировки с пятью лентами в том виде, в котором он определен в алгоритме 5.4.5В, использоваться для сортировки четырех полных бобин исходных данных до момента окончательного слияния? 14. [М19] Выведите (10). 15. [ИМИ] Докажите, что де(х) ж 50(г)/(1 — з), где ЙО(з) является рациональной функцией з, не имеющей особых точек внутри единичного круга, следовательно, а„= Йо(1) и+ %1 0(1) прн и -+ оо. В частности, покажите, что 0 -Ро О 0 1 -Ро Ьз(1) = с(ес Р' Ро ~ с(ег 1 0 О 0 0 О 16.
[41] Детально изучите сортировку 100,000 записей по 100 символов, нарисуйте диа граммы, подобные диаграмме Л, в предположении, что имеется 3, 4 н 5 лент. *5.4.7. Внешняя поразрядная сортировка В предыдущих разделах раглматрнвалась сортировка методом слияния файлов на лентах. Но существует и другой способ сортировки на лентах, основанный на принципе поразрядной сорти)ювки, который ранее использовался в механических сортировальных машинах для перфокарт (см. раздел 5.2.5).
Этот метод иногда называют распределяющей сортировкой, сортировкой по колонкам, карманной сортировкой, цифровой сортировкой, сортировкой методом разделения и т. д. Он, как оказывается, по существу, прогпивополошсен слияникй Предположим, например, что в нашем распоряжении имеются четыре ленты, а ключей может быть только восемь: О, 1, 2, 3, 4, 5, б, 7. Если исходные данные сгдержатся на ленте Т1, то начнем с переписи всех четных ключей на ТЗ и всех нечетных — на Т4. Т2 Т1 (О, 1, 2, 3, 4, 5, б, 7) Т4 Дано Проход 1 (0,2,4,6) (1,3,5,7) Теперь перематываем ленты и читаем сначала ТЗ, а затем — Т4, переписывая (О, 1,4,5) наТ1и(2,3,6,7) наТ2.
Проход 2 (О, 4Ц1,5) (2, 6ЦЗ, 7) (Строка "(0,4Ц1,5)" обозначает файл, содержащий записи только с ключами 0 и 4, за которыми следуют записи только с ключами 1 и 5. Заметим, что на Т1 теперь находятся те ключи, средний двоичный разряд которых содержит 0.) После еще одной перемотки и распределения ключей О, 1, 2, 3 на ТЗ и ключей 4, 5, б, 7 на Т4 получаем следующее. Проход 3 (ОЦ1Ц2ЦЗ) (4ЦЗЦОЦ7) После копирования Т4 в конец ТЗ работа завершается, В общем случае для ключей и диапазоне от 0 до 2" — 1 можно аналогичным образом рассортировать файл за Ь проходов, после которых следует фаза окончательной "сборки": На этом этапе примерно половина данных копируется с одной ленты на другую. Имея шесть лент, можно так же использовать представления по основанию 3 для сортировки ключей от О до Зь — 1 за Й проходов.
Существуют модификации этого метода с частичными проходами. Предположим, например, что допускается десять ключей (0,1,...,9), и рассмотрим следующую процедуру, авторство которой принадлежит Р. Л. Эшенхерсту (К. 1.. АэЬепЬогвэ) ~ТЬеогу ог'8ибгсЬ1л8, Ргойтшв Верогг В1 7 (Нвгтагб Пшт. Сошр. ЬаЬогагогу: Мау, 1954), Ь1-1.76]. Фаза Т1 Т2 ТЗ Т4 Проход (0,1,...,9» (0,2,4,7) (1,5,6) (3,8,9) (О) — (1,5,6Ц2,7) (3,8,9Ц4) (ОЦ1Ц2) (ОЦ7) — (3,8,9Ц4Ц5) (ОЦ1ЦЗЦЗ) (б) (7Ц8) (9) (4Ц5) (ОЦ1Ц2ЦЗЦ4)...
(9) 1 2 3 4 С 1.0 0.4 0.5 0.3 О.б 2.8 Здесь С представляет фазу сборки. Если каждое значение ключа встречается примерно в одном из десяти случаев, то эта процедура для сортировки десяти ключей затрачивает только 2.8 прохода, в то время квк в первом примере требуется 3.5 прохода для сортировки всего восьми ключей.
Таким образом, продуманая схема распределения влечет за собой значительное различие в показателях эффективности для поразрядной сортировки точно так же, как для слияния. Схемы распределения из предыдущих примеров представим, как и обычно, древовидными структурами. Пример 1 Пример 2 в а т т Круглые внутренние узлы этих деревьев пронумерованы 1, 2, 3, ... в соответствии с шагами процесса 1, 2, 3, .... Имена лент А, В, С, Р (вместо Т1.
Т2, Т3, Т4) помещены рядом с ребрами дерева, чтобы указать, куда попадают записи. Квадратные внешние узлы изображают фрагменты файла, содержащие только адин ключ, и этот ключ выделен полужирным шрифтом под соответствующим узлом. Ребра, расположенные над квгдратными узлами, помечены именем выводной ленты (С в первом примере, А — во втором). Таким образом, на шаге 3 примера 1 выполняется считывание с лепты Р н запись ключей 1 и 5 на ленту А и ключей 3 и 7 на ленту В. Нетрудно видеть, что число выполняемых проходов равно длине внешнего пугли дерева, деленной на число внешних узлов в предположении, что все ключи равновероятны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
