Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 74
Текст из файла (страница 74)
Каждый элемент данной таблицы (кроме элементов первой строки) является суммой пяти элементов, расположенных в предыдущей строке непосредственно левее него. Число серий в "точном" распределении и-го уровня равно Т„(1), а общее количество обрабатываемых серий в процессе их слияния равно производной Т„'(1). Далее, Х;Т.():— 52+ 422 + 322 + 224 + 24 "и)"- (1 .(2+22+22+24+24))2 4>1 полагая х = 1 в (16) н (18), получаем, что число слияний для точного распределения и-го уровня есть коэффициент при 2" в а(2)1(2); см. (7).
Это согласуется с нашими предыдущими рассуждениями. Функции Т„(х) можно использовать для определения объема работы, когда фиктивные серии добавляются оптимальным образом. Пусть Е„(п4) есть сумма наименьших п4 ЧИСЕЛ СЛиянИй в раепрвдвлвнии и-го уРовня, Посмотрев на столбцы (17), мы без труда вычислим эти суммы Ев(п2). в2 ш 1 2 3 4 5 б 7 8 9 10 и 12 13 14 15 16 17 18 19 29 21 в=112345ооо>аа в = 2 1 2 3 4 б 8 10 12 в = 3 1 2 3 5 7 9 11 13 в=4 1 2 4 б 8 10 12 14 в=513579111315 в=б 2 4 б 8 10 12 14 1б вю7 2 4 б 8 10 12 14 1б Например, для сортировки 17 количество операций составит 14 Оо ОО оо со 15 17 19 21 24 16 18 20 22 24 17 19 21 23 25 18 20 22 24 26 18 20 23 26 29 серий с помощью Х(17)=36 Н, 27 ЗО 33 Зб Оо оо ос оо 2б 29 32 35 38 41 44 47 (19) 27 29 32 35 38 41 44 47 28 ЗО ЗЗ Зб 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-го уровня! В самом деле, по мере возрастании о' оптимальный номер уровия оказывается значительно больше номера, используемого в алгоритме 11. В упр. 14 показано, что существует неубывающая последовательность М„, такая, что уровень и оптимален для М„< л < М г4, ио не для 5 > М„.ьс. В случае для шести лент только что вычисленная таблица Е„(пг) дает Мо = О, Мг = 2, Мг = б, Мг = 10, М4 = 14, Выше рассматривался толысо случай для шести лент, однако ясно, что те же идеи применимы к миогофазноа сортировке с Т леитами для любого Т > 3; просто в соответствующих местах необходимо заменить 5 иа Р = Т вЂ” 1. В табл. 2 представлены последовательности М„, полученные для различньсс значений Т.
Табл. 3 и рис. 72 дают представление об общем количестве обрабатываемых начальных серий после оптимального распределения фиктивных серий. (Формулы внизу табл. 3 следует принимать с осторожностью, так как это приближение по методу наименьших квадратов на области 1 < о < 5000 (1 < о < 1ОООО для Т = 3), что приводит к отклонекию (данная область значений о' ие являетсн одинаково подходящей для всех Т).
По мере того„как о' -г ос, число обрабатываемых начальных серий после оптимального многофазного распределения асимптотически приближается к о 108~ о, но это приближение происходит крайне медленно.) При помощи табл. 4 можно сравнить метод распределения алгоритма П с результатами оптимального распределения„приведенными в табл. 3. Ясно, что алгоритм В 1 2 2 2 2 3 4 5 3 4 б 8 4 6 10 14 5 9 18 23 6 14 32 35 7 22 55 76 8 35 96 109 9 56 173 244 10 90 280 359 11 145 535 456 12 234 820 П97 13 378 1635 1563 14 611 2401 4034 15 988 4959 5379 16 1598 7029 6456 17 2574 14953 18561 18 3955 20583 22876 19 6528 44899 64189 2 2 б 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 Мг 32 Мг 37 Мг 41 Мг 44 Мг 199 Мг 243 Мьг 295 Мц 330 Мгг 1499 57гг 1818 М14 2116 Мм 2374 Мьг 2576 Мм 2709 Мгг 15787 Мгг Т 5 Т=б Т 7 Т-В т-)о е ) 2 5 И»чели»ем серии, е Рис.
72. Эффективность многофазиого слияиви с оптимальным начальным распределе- нием при тех же прели)иожеииих, что и и» рис, 70. Таблица 3 числО НАчАльных сеРЙЙ, ОБРАБАтыБАемых пРН Оптимлльнсм МНОГОЕАЗНОМ СЛИЯНИИ б т=з т=4 т=5 т=б т=? т=з т=о т=10 )' !1.51 ) (-.и не очень близок к оптимальному при больших о н т; однако непонятно, можно ли поступить в этих случаях существенно лучше алгоритма Р, не прибегая к значительным усложнениям, особенно если Я заранее неизвестно. К счастью, заботиться о больших Я приходится довольно редко )см, раздел 5.4.6), так что алгоритм Р на практике не тик уж плох (а на самом деле — даже весьма неплох!).
10 Зб 2О 9О 5О 294 100 ?02 500 4641 1000 ГОЗ?1 5000 63578 24 19 17 60 49 44 194 158 135 454 З62 325 3041 2430 2163 6680 5430 4672 41286 32905 28620 0.951 0.761 0.656 +.14 +.16 +.19 15 38 128 285 1904 4347 26426 О. 589 +.21 14 13 Зб 34 121 113 271 263 1316 1734 3872 3739 23880 23114 0.548 0.539 +.2О +.О2 12 зз 104 254 1632 3632 22073 0.488) к о!»5+ +.18) х о Таблица 4 ЧИСЛО НАЧАЛЬНЫХ СЕРИЙ, ОБРАБАТЫВАЕМЫХ ЖРИ СТАНДАРТНОМ МНОГОФАЗНОМ СЛИЯНИИ 3 Т=З Т=4 Т=5 Т=б Т=7 Т=б Т=9 Т=10 10 36 20 90 50 294 100 714 500 4708 1000 10730 5000 64740 24 19 62 49 194 167 459 393 3114 2599 6920 5774 43210 36497 13 12 34 33 120 114 292 277 2047 2025 4597 4552 28817 28080 17 15 14 44 41 37 143 134 131 339 319 312 2416 2191 2100 5370 4913 4716 32781 31442 29533 Математически многофазнвя сортировка впервые проанализирована У.
К. Картером (Ж. С. Саггег) (Ргос. 1РХР Сопбгеяя (1962), 62-66). Многие из приведенных им результатов относительно оптимального размещения принадлежат Б. Сэкману (В, Басилан) и Т. Зингеру (Т. 91пйег) ("А гесгог шобе1 гог шегбе эогг апа)уэ1э", неопубликованный доклад, представленный на симпозиуме АСМ Богг Бушроашп (71отешЬег, 1962), 21 рабез). Позднее Сэкман предложил метод распределения по горизонтали, используемый в алгоритме П. Дональд Шелл (ПопаЫ БЬе11) [САСМ 14 (1971), 713-719; 15 (1972), 28), независимо развив эту теорию, указал на озотношеиие (10) и подробно изучил несколько различных алгоритмов распределения. Дальнейшие полезные усовершенствования и упрощении были получены Дереком Э.
Ззйвом (Веге(г А. Еаге) (31СОМР 6 (1977), 1-39); некоторые из результатов Зэйва рассматриваются в упр. 15-17. Производящая функция (16) впервые была исследована У. Буржем (%. Впгбе) (Ргос. 1Р1Р Сопягеяз (1971), 1, 454-459). А как обстоит дело с временем перемотки? До сих пор мы использовали число начальных обрабатываемых серий как единственную меру эффективности для сравнения стратегий слияния на лентах. Но после каждой из фез 2-6 в примерах в начале этого раздела компьютер должен ожидать перемотки двух лент; обе выводные ленты — как предыдущая, так и новая текущая — должны быть перемотаны в начало, прежде чем сможет выполняться следующая фаза. Это может вызвать существенную задержку, твк как в общем случае на предыдущей выводной ленте содержится значительный процент сортируемых записей (см.
столбец "Проходы/фазы" в табл. Ц. Досадно, когда компьютер простаивает при перемотке, тогда как в это время можно было бы, используя иную схему слияния, выполнять полезную работу с остальными лентами. Данную задачу можно решить с помощью простой модификации многофазной процедуры, хотя она требует не менее пяти лент (см, диссертацию И. Сезари (У. Сеэап) (П, о( Рвг1з (1968), 25-27), в которой эта идея приписывается Ж. Карону (3.
Сагоп)). Каждая фаза схемы Карона сливает серии с Т вЂ” 3 лент на любую другую ленту, в то время как оставшиеся две ленты перематыввются. Рассмотрим, например, случай для шести лент и 49 начальных серий. В следующей таблице буквой В обозначены ленты, перематывающиеся во время данной фазы; предполагается, что на ленте Т5 содержатся первоначальные серии. Время записи Фаза Т1 Т2 ТЗ 1 1м 117 1!3 2 (К) 1э 1 3 1 1" 1Р— К 5 — В. 7 6 К И2 К 7 151 К 7' 8 К И' 7 9 15' 11 10 (15о) — К 49 8 х 3 = 24 5 х 3 = 15 4 х 5 = 20 2х 7=14 2 х 11 = 22 1 х 15 = 15 1 х 23 = 2З ОхЗЗ= 0 1 х49 = 49 Здесь все перемотки, по существу, совмещены, за исключеиием фазы 9 ("фиктивиая фаза", которая подготавливает окоичательиое слияиие) и перемотки после начальиой фазы распределения (когда перематываются все лепты).
Если ! есть время„ необходимое для слияиия стольких записей, сколько содержится в одной иачальиой серии, а г — время перемотки иа одну начальную серию, то этому процессу необходимо около 182! + 40г плюс время начального распределения и завершающей перемотки. Соответствующие выражеиия для стандартного миогофазиого метода, использующего алгоритм П, есть 1401+ 104г, что иесколько хуже, если г = зс, и иесколько лучше, если г = 11. Все сказанное о стандартном миогофазиом методе приложимо к миогофазиому методу Кароиа; например, последовательвость а„теперь удовлетворяет рекурреитному соотношению (20) и„ = о„-т + о -э + а„ 4 вместо (3).
Читателю будет полезно проанализировать этот метод таким же образом, как мы анализировали стандартный мвогофазиый, поскольку это улучшит понимание обоих методов (см., иапример, упр. 19 и 20). В табл, 5 сведены данные о миогофазиом методе Карона, аналогичные данным об обычном миогофазяом методе, приведепиым в табл, 1. Заметим, что иа самом деле при восьми и более лентах метод Кароиа становится лучше миогофэзиого как по числу обрабатываемых серий, так и по времени перемотки, несмотря иа то что ои выполняет (Т вЂ” 3)-путевое слияиие вместо (Т вЂ” 1)-путевого! Таблица $ ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ КАРОНА Проходы Прохины/ фазы, % Отношение роста 1.463 !и Я+ 1.016 0.951 !и б + 1.014 0.781 !и б+ 1.001 0.699 1и3+ 0.980 0.654 1и 5 + 0.954 0.626 !и о + 0.922 0.575 (и Я+ 0.524 5 б 7 8 9 10 20 3.556!но+ 0.158 2.616 1и б- 0.166 2.337 !и о — 0.472 2.216 1и Б — 0.762 2.156 !и и — 1.034 2,124 !и 8 — 1,290 2.078 !и о — 3.093 Т4 Т5 Тб 1" — (К) — к з' к з' к 5' К З' к з' з' 5 3' 5~ — К вЂ” К 2З' в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
