Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 73
Текст из файла (страница 73)
]Начальная установка.) Установить А133 <- Щ3 +- 1 и ТАРЕЦ3 е- у при 1 < 3 < Т. Установить АТТ3 <- ВЕТ3 <- О и ТАРЕЕТ3 +- Т. Затем установить 1+- 1, 3 с- 1. 02, ]Ввод на ленту у.] Записать одну серию на ленту 3 и уменьшить И33 на 1. Затем, если ввод исчерпан, перемотать все ленты и перейти к шагу 05. 323.
]Продвижение 3.] Если И33 < ВЦ+ 13, то увеличить 3 на 1 и вернуться к шагу 02. В противном случае, если Иу3 = О, перейти к шагу 04, иначе— установить у' +- 1 и вернуться к шагу 02. 324. ]Подняться на один уровень.) Установить 1 +- 1+ 1, а <- А Ш, затем для 3 = 1, 2, ..., Р (именно в таком порядке) установить И33 <- а+ АЦ+ 13 — АЫ и АЫ ~- а+Щ+ 13. (См. (1). Отметим, что АКР+ 13 всегда О.
В ятом месте будем иметь ВП3 > ВИ » " ИТ3,) Теперь установить 3 ~- 1 и вернуться к шагу 02. 05. ]Слияние.] Если 1 = О, то сортировка завершена н результат находится на ТАРЕП3. В противном случае выполнять слияние серий с лент ТАРЕШ,-,, ТАРЕГР3 на ТАРЕГТ3 до тех пор„пока ТАРЕСР3 не станет пустой и ВГР3 = О. Процесс слияния для каждой сливаемой серии должен протекать следующим образом. Если ИЯ > Одля всский, 1 <у < Р, тоуяеличитьИТ3 на 1 и уменьшить каждое ВЦ3 на 1 для 1 < .у < Р; в противном случае выполнять слияние по одной серии с каждой ленты ТАРЕ1Я, такой, что Щ3 = О, н уменьшить ИЯ на 1 для остальных,у. (Таким образом, считается, что фиктивные серии находятся в начале ленты, а не в конце.) 22 4 $ Т Т Рис.
69. Порядок, в котором серии 34-65 распределяются на ленты при переходе с уровня 4 на уровень 5. (См. таблицу точных распределений (1).) Заштрихованные области соответствуют первым 33 сериям, которые были распределены к моменту достижении уровня 4. Последняя строка в каждой колонке иютветствует началу ленты. з4 35 Зэ 42 46 51 56 61 Т, Зле 43 47 52 57 62 Тг 37 46 44 46 53 56 63 06. [Опуститься на один уровень) Установить 1 +- 1-1. Перемотать ленты ТАРЕ [Рз н ТАРЕ[Тз.
(В действительности перемотка ТАРЕ[Р1 могла быть начата на шаге 05, после ввода с нее последнего блока) Затем установить (ТАРЕ [Ц, ТАРЕ [22, ...,ТА Е[т)) 4- (ТАРЕ[т),ТАРЕ[1),...,ТАРЕ[т- и), (й[Ц,В[2),...,В[т)) 4- (о[Т), й [1),..., о[Т вЂ” 1) ) и вернуться к шагу 05. Правило распределения, которое так лаконично сформулировано на шаге 03 этого алгоритма„стремится по возможности уравнять числа фиктивных серий на каждой ленте. На рис.
69 нллюстрируетсл распределение серий, когда мы переходим от уровня 4 (33 серии) к уровню 5 (65 серий) в сортировке с шестью лентами; если было бы, скажем„только 53 начальные серии, то все серии с номерами 54 и выше рассматривались бы как фиктивные. (На самом деле серии записываются в конец ленты, но удобнее считать, что они записываются в начало, так как предполагается, что фиктивные серии находятся в начале ленты.) Мы уже рассмотрели первые три из поставленных выше вопросов; осталась выяснить число "проходов" по данным, Сравнивая наш "шестиленточный пример" с таблицей (1), мы видим„что суммарное количество обработанных начальных серий при я = 16 составляет аз11+а472+аззз+агг4+а175+оо76, если исключить начальный проход распределения.
В упр. 4 выводятся производящие функции 1 о(г) = о„г" = зг З 24 З' ь>о 2 3 4 3 52+42 +32 + 22 + з (Т) Ф(2) = ~ ~1„2" = гг гэ 24 25 ' а>1 Отсюда следует, что в общем случае число обрабатываемых начальных серий цри 5 = Ф„равно коэффициенту прн 2" в произведении а(г)г(г) плюс з„(это дает начальный проход распределения). Теперь вычисляем асимптотическое поведение многофазного слияния, как показано в упр. 5-7, и получаем результаты, приведенные в табл. 1. В табл. 1 "Относительный рост" есть предел 1пп„,„г„.ь1/г„, пОКазЫвающнй, во сколько приблизительно раз возрастает число серий на каждом проходе. '*Проходы" — это среднее количество обработок каждой записи, а именно — 1/Я, умноженное на общее число начальных серий, обрабатываемых в течение фаз распреде- Таблнцв 1 А!1ПРОКСИМАЦИЯ ПОВЕДЕНИЯ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ Ленты Фазы Проходы Проходы/ Относительный фазы, % рост ления и слияния.
Указанные числа проходов н фаз справедливы в каждом случае с точностью до 0(о' ') прн некотором с > 0 для точного распределения прн о — ь оо. На рис. 70 изображены в виде функций от В средние количества слияний каждой записи с помощью алгоритма В для неточных чисел. Заметим, что прн использовании трех лент сразу после точных распределений появляются "пики" относительной неэффективности, но это явление в значительной степени исчезает при наличии четырех нли более лент. Использование восьми или более лент дает сравнительно малое улучшение по сравнению с шестью нлн семью лентами.
Более детальный анализ. В сбалансированном слиянии, требующем й проходов, каждая запись обрабатывается в ходе сортировки ровно и раз. Но многофазная процедура не является такой беспристрастной: одни записи могут обрабатываться намного больше раз, чем другие, и можно увеличить скорость, если помещать фиктивные серии в часто обрабатываемые позиции. По этой причине проанализируем более подробно многофезное распределение.
Вместо того чтобы интересоваться только числом серий на каждой ленте, как в (1),. присвоим каждой серии число слилнио, т. е. определим, сколько раз она будет обрабатываться в течение всего процесса сортировки. Вместо (1) получим следующую таблицу. Тз ТЗ 1 2 32 4ЗЗ2 54434332 1 21 3221 43323221 544343324332322 1 21 3221 4332322 54434332433232 1 2! З22 433232 544343324332 Е» (А„+ ЦЕ А. + 1 (8) А„ (А»+ ЦВ» В„ С» (А + ЦС» (А» + Ц17 и+1 Здесь А„— цепочка из а„значений, представляющих числа слияний каждой серии на Т1, если начать с распределения а-го уровня;  — юответствующав цепочка для Т2 и т.
д, Обозначение»(А„+ 1)В„" читается так: ".4„, все значения которой увеличены на 1, а за ней — В„". 3 4 5 6 7 8 9 10 20 УРовЕНь о 1 2 3 4 5 2.078 1и о + 0.672 1.641 1и о + 0,364 1.524 !и В+ 0.078 1.479Ъ8- Олбз 1.460!п8- 0.424 1.451 !и б — 0.642 1.447 !и о — 0.838 1. 445 !и  — 1.017 1.443 !и 5' — 2,170 Т1 0 1 21 3221 4332322! 3443433243323221 1.504 1и В+ 0.992 1.015 !и 5+ 0.965 0.863 1п и + 0.921 О. 795 !п 5 + 0.864 0,762 !п 3+ 0.797 0.744!и 5+ 0.723 0.734 1и б + 0.646 О. 728 !и и + О.
568 О. 721 !и 5' — О. 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 11 Т 6 г-а Г 16 Рне. 70. Эффективность многофизного слиянии, использующего алгоритм О. На рнс. 71, «а) изображаются снизу яверх Аа, Ва, Са, Юа, Еа н демонстрируется, каким образом числа слияний для каждой серна появляются на ленте. Заметим, что серия в начале любой ленты будет обрабатыяаться б раз, а то время как серия а конце Т1 будет обрабатываться лишь однаждьг. Эта "дискриминация" прн многофазном слиянии прнводнт к тому, что фиктивные серии лучше помещать а начало ленты, а не в конец. На рнс. 71, (Ь) представлен оптимальный порядок распределения серий для пятнуроннеаого многофазного слияния; каждая новая серия помещается в познцню с наименьшим нз оставшихся числом слняннй. Заметим, что алгоритм 0 (см.
рнс. 89) несколько хуже, так как он заполняет некоторые познцнн "4" до того, как будут заполнены все познцнн "3". Рекуррентные соотношения (8) показынаюг, что все В„, С„, Ви н Е„являются начальнымн подцепочкамн А„. В действительности, используя (8), можно вывести формулы (А„.1) + 1, (Ап-)А -2) + 1, (Аи-1Аи-2Ап-3) + 1, (А -1А -зАи-зАи-4) +1, (Ан-1Аи-2Аи-ЗА -4Аи-6) + 1~ (9) ~ 16 $ ф а й т ~ 6 4 З Ю ЗЕ Ю НЮ ЛЮ ЯЮ 1ЯЮ ЭЮЕ ЯЮЕ Начэльимв аиаии, Х Начала лепты Рнс. 71. Анализ многофазвого распределения пятого уровня на шести лептах; (а)— числа слияний; (!з) — оптимальный порядок распределения.
обобщающие соотношения (3), которые имеют дело только с длинами этих цепочек. Кроме того, из правил, определяющих цепочки А, следует, что структура в начале каждого уровня, в сущности, одна и та же; имеем (10) где ߄— цепочка из а„значений, определяемая законом Юп = Сп-!Дп-з + 1)(Яп-« +2)фп-з + 3)(Яч «+4) при и > 1; Се = О; 4„7„= с (пустая цепочка) при и С О.
(11) Тая КаК 4„1„ваЧИНастея С Я„1, МОЖНО раССМОтрЕтЬ 6ЕСКОПЕЧНрзе цЕПОЧКу Ясс, ПЕр- вые а„элементов которой совпадают с Я„. Эта цепочка Ц„, по существу, описывает все числа слияний в многофазном распределении. В случае шести лент имеем «3 = 011212231223233412232334233434412232334233434452334344534454512232 .. (12) В упр. 11 содержится интересная интерпретация этой цепочки. При условии, что А„ есть цепочки пз!пзз...пз,„, обозначим через А„(х) = х'"' + х ' + " + х ' соответствующую производящую функцию, описывающую, сколько раз появляется каждое число сликний; аналогично введем В„(х), С„(х), Р1(х), Е„(х), Например, Аз(х) = хз+хз+хз+хз+хз+хз+хз+х = х4+3хз+3хз+х, В силу соотношений (9) при и > 1 имеем Е„(х) = х(А„!(х)) „ Р„(х) = х(А„! (х) + А„з(х)), С„(х) = х(А„з(х)+ А„з(х)+ А -з(х)) В„(х) = х(А„(х) + А„з(х) + А з(х) + А -4(х)), Ач(х) = х(Ач !(х) + А„з(х) + Ап-з(х) + Ап-4(х) +.4п-«(х))~ (13) где Ае(х) = 1 и А„(х) = О при и = -1, -2, -3, -4.
Следовательно, ! 2 2 3 3 з 4 2 3 3 4 з 4 (з) 1 2 !6 !9 2З 42 !! 27 52 46 57 5! 56 6! (ь) 3 5 !7 6 20 24 45 !2 26 зз 47 Зз 522 57 62 6 !6 9 2! 25 44 !3 29 34 46 59 «З 66 6З ЕА„(х)24 Ехе(2+22+22+24+ ь)4, (14) 1 х(2 .1. 22 + 22 + 24 + 2$) в>О мЗО Рассматривая серии на всех лентах, положим Т„(х) = А (х) + В„(х) + С'„(х) + Ю„(х) + Е„(х), и > 1; (15) из (13) немедленно получаем Т„(х) = ЗА„1(х) + 4А„2(х) + ЗА„О(х) + 2А 4(х) + А„О(х), а значит, и х(52+422+ 322+ 224+ 22) ЕТ.(.): 1 — х(2+ 22+ 22+ 24+ 24) п>1 Соотношение (16) показывает, что можно легко вычислить коэффициенты Т„(х). 22 22 24 22 24 21 22 29 2!О 211 212 212 214 х 5 4 3 2 1 0 О 0 О 0 О 0 О О хз 0 5 9 12 14 15 10 6 3 1 0 0 0 0 хз О О 5 14 26 40 55 60 57 48 35 20 10 4 (17) х4 0 0 О 5 19 45 85 140 19О 238 260 255 220 170 хэ О О 0 О 5 24 69 154 204 484 703 918 1088 1168 Столбцы этой таблицы дают Т„(х); например, Т4(х) = 2х + 12х2 + 14хз + 5х4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
