AOP_Tom3 (1021738), страница 72
Текст из файла (страница 72)
д. Обозначение п(А„+ 1)В„п читается так: пА„, все значения которой увеличены на 1, а эа ней — В„". 3 4 5 б 7 8 9 10 20 Уровень О 1 2 3 4 5 2.078 !и 5 + 0.672 1.6411п Е+ 0.364 1.524!п8+ 0.078 1.479 1н Я вЂ” 0.185 1. 460 1и 5 — 0.424 1. 451 !в Š— О. 642 1.447 !и Š— 0.838 1.445 !и Š— 1.017 1.443 !и 8 — 2.170 1.504!п Е+ 0.992 1.015 !и Е+ 0.965 0.8631п 5+ 0.921 0.795 1п 5 + 0.864 0.762 !и Е + О 797 0.744 !п Е+ О 723 0.734!п8+ 0 646 0.728 !и 8+ 0.568 0.721 !а Š— 0.030 72 62 57 54 52 51 51 50 50 1.6180340 1 8392868 1.9275620 1.9659482 1.9835828 1.9919642 1.9960312 1.9980295 1.9999981 !4 т=з 55 !2 2! ~ 7о р я я з Д 7 о $6 х 4 3 3 Т 4 Т 5 Т= О т-з т-5о о 2 5 Ю 20 50 500 200 500 204Ю 2000 5000 Нвчекьвие серии, Я Рнс.
ТО. Эффективность многофазного слияния, использующего алгоритм 12. Еп = (Ап !) +1, (Ап зАп з) +1, (Ап зАп зА„з) + 1, (А -! 4 -зА -зАп-4) + 1, (Ап-!Ах-зАп-ЗАп-4Ап-З) + 1, Рп (9) Сп = Ап = На рис. 71, (а) изображаются снизу вверх Аз, Вз, Сз, Вз, Ез и демонстрируется, каким образом числа слияний для каждой серии появляются на ленте. Заметим, что серия в начале любой ленты будет обрабатываться 5 роз, в то время как серия в конце Т1 будет обрабатываться лишь однаждьг. Эта "дискриминация" при многофазном слиянии приводит к тому, что фиктивные серии лучше помещать в начало ленты, а не в конец. На рис.
71, (Ь) представлен оптимальный порядок распределения серий Лля пятиуровневого многофазного слияния; каждая новая серия помещается в позицию с наименьшим из оставшихся числом слияний. Заметим, что алгоритм В (см. рис. 69) несколько хуже, так как он заполняет некоторые позиции п4п до того, как будут заполнены все позиции пЗ'! Рекуррентные соотношения (8) показывают, что все Вп, Сп, В„и Еп являются начальными подцепочками Ап.
В действительности, используя (8), можно вывести формулы Начало ленты Рнс. 71. Анализ многофвзного распределения пятого уровни на шести лентах: (в) числа слияний; (Ь) — оптимальный порядок распределения. обобщающие соотношения (3), которые имеют дело только с длинами этих цепочек. Кроме того, из правил, определяющих цепочки А, следует, что структура в начале каждого уровня, в сущности, одна и та же; имеем (10) Ап=и — Дп, где Я„ — цепочка из оп значений, определяемая законом 1чп = Юч-!Мп-г + 1)(1чп-3 + 2)(1ип 4 + 3)(Юп 5 + 4) при и > 1; Яо = О; Я„= е (пустая цепочка) при и ( О. (11) ТаК КаК Ои НаЧИНаЕтСЯ С 1,1„1, МОЖНО РаССМОтРЕтЬ бЕСКОИЕЧНУЮ ЦЕПОЧКУ Я, ПЕР- вые ап элементов которой совпадают с 1,7„. Эта цепочка Я„, по существу, описывает все числа слияний в многофазном распределении.
В случае шести лент имеем 1)„ = 011212231223233412232334233434412232334233434452334344534454512232 . (12) В упр. 11 содержится интересная интерпретация этой цепочки. ПРИ УСЛОВИИ, ЧтО Ап ЕСТЬ ЦЕПОЧКИ т1тг...т,„, ОбОЗНаЧИМ ЧЕРЕЗ Ап(Х) х ' + х '+ . + х "" соответствующую производящую функцию, описывающую, сколько раз появляется каждое число слияний; аналогично введем Вп(х), Сп(х), Рп(х), Еп(х), Например, Ач(х) = х'+хг+хг+х'+хг+х'+хг+х = хз+Зхз+Зхг+х. В силу соотношений (9) при и > 1 имеем Еп(х) = х(Ап,(х)), Р„(х) = х(Ап 1(х) + Ап г(х)), Сп(х) = х(А -1(х) + Ап-г(х) + Ап-3(х)) Вп(х) =х(Ап 1(х)+Ап г(х)+Ап 3(х)+А «(х)), Ап(х) = х(Ап-1(х) + А г(х) + А -з(х) +.4п-4(х) + Ап 5(х)), (13) где Ао(х) = 1 и Ап(х) = О при и = — 1, — 2, — 3, — 4. Следовательно, 1 г г з 2 з 4 2 з з 4 3 4 4 5 (а) 1 2 4 16 7 19 гз 42 11 27 32 46 37 51 56 61 (Ь) з 17 в гв 24 4З 12 гв зз 47 зв 52 57 бг б 16 9 21 гз 44 1З 29 34 43 39 53 5В 63 А„(х) 2"— 1 1 х( + 22+ 22+ 24+ 28) ~ "( + '+2'+,4+,')", (14) п>0 ьйо Рассматривая серии на всех лентах, положим Т„(х) = А„(х) + В„(х) + С„(х) + 77„(х) + Е„(х), и > 1; (15) из (13) немедленно получаем Т„(х) = 5А„1(х) + 4А„2(х) + ЗА„з(х) + 2А„4(х) + А„з(х), а значит, и х(52 + 422 + 322 + 224 + 28) Т„(х)2"— (16) .(2+ 2+ З+ 4+28) ' в>1 Соотношение (16) показывает, что можно легко вычислить коэффициенты Т„(х).
22 28 24 28 28 22 28 28 210 211 212 2И 14 х 5 4 3 2 1 0 О 0 О О О 0 0 0 хз 0 5 9 12 14 15 10 6 3 1 0 0 0 0 хз 0 О 5 14 26 40 55 60 57 48 35 20 10 4 (17) х4 0 0 0 5 19 45 85 140 195 238 260 255 220 170 хз 0 0 0 0 5 24 69 154 294 484 703 918 1088 1168 Столбцы этой таблицы дают Т,(х); например, Т4(х) = 2х + 12хз + 14хз + 5х4. Каждый элемент данной таблицы (кроме элементов первой строки) является суммой пяти элементов, расположенных в предыдущей строке непосредственно левее него.
Число серий в "точном" распределении и-го уровня равно Т„(1), а общее количество обрабатываемых серий в процессе их слияния равно производной Т„'(1). Далее, 52 + 422 + Ззз + 224 + 28 7 Т„'(х)2"— (18) с " (1 х(2+22+22+24+28))2 ' полагая х = 1 в (16) и (18), получаем, что число слияний для точного распределения и-го уровня есть коэффициент при 2" в а(2) 2(2); см. (7). Это согласуется с нашими предыдущими рассуждениями. Функции Т„(х) можно использовать для определения объема работы, когда фиктивные серии добавляются оптимальным образом. Пусть Е„(т) есть сумма наименьших пз чисел слияний в распределении и-го уровня. Посмотрев на столбцы (17), мы без труда вычислим эти суммы Е„(пз). т = 1 2 3 4 Ь б 7 В 9 10 11 12 13 14 15 16 17 18 19 20 21 я=1 1 2 3 4 5 сс ос ос в=2 1 2 3 4 б В 10 12 в = 3 1 2 3 5 7 9 11 13 в=4 1 2 4 б 8 10 12 14 в = 5 1 3 5 7 9 11 13 15 п = б 2 4 б 8 10 12 14 1б п = 7 2 4 б 8 10 12 14 16 Например, для сортировки 17 количество операций составит 14 со со сс со 15 17 19 21 24 16 18 20 22 24 17 19 21 23 25 18 20 22 24 2б 18 20 23 26 29 серий с помощью Ез(17) = Зб.
Но, 27 30 33 36 сс со сс со 2б 29 32 35 38 41 44 47 (19) 27 29 32 35 38 41 44 47 28 30 33 36 39 42 45 48 32 35 38 41 44 47 50 53 распределения 3-го уровня общее если испольэовать распределение Таблица 2 ЧИСЛО СЕРИЙ, ПРИ КОТОРОМ ДАННЫЙ УРОВЕНЬ ОПТИМАЛЕН Уровень Т=З Т=4 Т=5 Т=б Т=7 Т=З Т=9 Т=10 4- илн 5-го уровня, общее количество операций в процессе слияния будет только Е4(17) = Ез(17) = 35. Выгоднее применять 4-й уровень, хотя число 17 соответствует "точному" распределению 3-го уровня! В самом депе, по мере возрастании о' оптимальный номер уровня оказывается значительно больше номера, используемого в алгоритме В. В упр. 14 показано, что существует неубывающая последонательность М„, такая, что уровень п, оптимален для Мо < а < М„з.з, но не дпя а ) М„з, В случае для шести лент только что вычисленная таблица В„(т) дает Мз — 10, М4 — 14.
Мо=О, М,=2, Мг=6, Выше рассматривался только случай для шести лент, однако ясно, что те же идеи применимы к мнагофазной сортировке с Т лентами для любого Т > 3; просто в соответствующих местах необходимо заменить 5 на Р = Т вЂ” 1. В табл. 2 представлены последовательности М„, полученные для различных значений Т. Табл. 3 и рис. 72 дают представление об общем количестве обрабатываемых начальных серий после оптимального распределения фиктивных серий. (Формулы внизу табл, 3 следует принимать с осторожностью, так как зта приближение па методу наименьших квадратов на области 1 < о < 5000 (1 < о < 10000 для Т = 3), что приводит к отклонению (данная область значений а не является одинаково подходящей для всех Х).
По мере того, как о -4 ао, число обрабатываемых начальных серий после оптимального многофазного распределения асимптотически приближается к а 1ойр а, но зто приближение происходит крайне медленна.) При помощи табл. 4 можно сравнить метод распределения алгоритма П с результатами оптимального распределения, приведенными в табл. 3. Ясно, что алгоритм В 1 2 3 4 5 6 7 8 9 10 11 12 13 14 И 16 17 18 19 2 3 6 9 14 22 35 56 90 145 234 378 611 988 1598 2574 3955 6528 2 2 4 5 6 8 10 14 18 23 32 35 55 75 96 109 173 244 280 359 535 456 820 1197 1635 1563 2401 4034 4959 5379 7029 6456 14953 18561 20583 22876 44899 64189 2 2 6 7 10 12 14 17 29 20 43 53 61 73 154 98 216 283 269 386 779 481 1034 555 1249 1996 3910 2486 4970 2901 5841 10578 19409 13097 23918 15336 27557 17029 2 2 8 9 14 16 20 23 24 28 27 32 88 35 115 136 148 171 168 213 640 240 792 1002 922 1228 1017 1432 4397 1598 5251 1713 5979 8683 6499 10069 30164 11259 2 Мз 10 Мг 18 Мз 26 М4 32 ЛХз 37 Мв 41 Мт 44 Мв 199 Мо 243 Мзо 295 Мзз 330 М 1499 Мзз 1818 Мм 2116 Мм 2374 Мм 2576 Мм 2709 Мзз 15787 Мм 12 1" т 4 Т= о т-7 т-в т=!о о 1 2 5 1О 20 50 100 200 500 1000 2000 5000 Нячяяъяик серия, 5 Рис.
72. Эффективность мнагафвзпого слияния с оптимальным начальным распределе- нием при тех же предположениях, что и на рис. 70. Таблица 3 ЧИСЛО НАЧАЛЬНЫХ СЕРИЙ, ОБРАБАТЫВАЕМЫХ ПРИ ОПТИМАЛЬНОМ МНОГОФАЗНОМ СЛИЯНИИ о Т=З Т=4 Т=5 Т=б Т=7 Т=8 Т=9 Т=10 !1.51 ) (-.1! не очень близок к оптимальному при больших о и Т; однако непонятно, можно ли поступить в этих случаях существенно лучше алгоритма !), не прибегая к значительным усложнениям, особенно если о заранее неизвестно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
