AOP_Tom3 (1021738), страница 77
Текст из файла (страница 77)
2.2.1-4 и формулу 2.3.4.4-(14)). Итак, мы предполагаем, что в случае Т-лент /2п~ 1 а 2»=~ ~ — приО<п<Т вЂ” 2; ~ ° 1 +1 (6) прн О < и < Т вЂ” 3. а2»2 —— О Чтобы проверить правильность этого предположения, достаточно показать, что (6) и (4) приводят к верным результатам для уровней О и 1. Для уровня 1 это очевидно, а для уровня О необходимо проверить, что А~ ΠΠΠ— 1 Π— 4 — 1 -14 — 7 О 1 О 2 О 5 О 14 1 для 0 < т < Т вЂ” 2. К счастью, зту сумму можно вычислить стандартными методами (это фактически пример 2 из раздела 1.2.б). Теперь можно вычислить коэффициенты при В(г) — о1(г)А(г) и т.
д. Рассмотрим, например, коэффициент при гг в Ю(г) — Вг(г)А(г). Он равен (3+ т+ Iс) +о ~х- (3+ т+ )с) (2/с) (-1) ь>о как следует из результата примера 3, приведенного в разделе 1.2.б. Таким образом, получены формулы А(г) = Во(г)А(г), В(г) = Вс (г) А(г) — до (г), /2(г) = ог(г).4(г) — Вг(г) С(г) = дг(г)А(г) — дс(г), Е(г) = Вс(г)А(г) дз(г). Кроме того, имеем ев ы = а„; следовательно, гА(г) = Е(г) и А(г) = Вг(г)/(64(г) г) (О) ((~/4 — гг + сг)/2) + ((с/4 — гг — сг)/2) Вп~ (г)— (10) Все упрощается, если теперь положить г = 2 о1пВ: (соо 9+ с о1п 9) г'"+' + (соо 6 — с сйп 9) г"'+' соо(2т+ 1) 9 9 (2з1пВ)— 2сооВ сов В (Такое совпадение приводит к мысли, что многочлены д„,(г) хорошо изучены в математике. Действительно, заглянув в соответствующие таблицы, мы видим, что о (г), по существу, является многочленом Чебышева второго рода, а именно— ( — 1)'"Уг (г/2) в обычных обозначениях.) Теперь можно определить корни знаменатели в (9): уравнение ос(2о1пВ) = 2 о1пВ сводится к соо 99 = 2 з1п 9 соз 9 = о1п 26.
Решения этого соотношения получаем, если только х96 = 26 + (2п — ! )х; все такие 9 дают корни знаменателя в (9) при условии, что соо9 ф О. (Если сооВ = О, Производящие функции были выражены при помощи В-многочленов, поэтому желательно лучше изучить 9. В этом отношении полезно упр. 1.2.9-15, так как оно дает выражение в замкнутом виде: то д~(~2) = (2гп+ 1) никогда не равно ~2.) Следовательно, получаем восемь различных корней: д4(2) — 2 = О при 2яп=вя, 221п:ггг 2в1п 2 х 2в!п=гх 2яп — ', вх 2в1п 1 в 2яп в я, 2яп в к.
14 ' ' 14 ' 14 ' 22 ' 22 ' 22 ' 22 ' 22 Так как д4(2) — многочлен степени 8, значит, учтены все корни. Первые три нз этих значений дают г72(2) = О, так что г72(2) и в4(2) — 2 имеют в качестве общего делителя многочлен третьей степени. Остальные пять корней управляют асимптотическим поведением коэффициентов А(2), если разложить (9) на элементарные дроби.
Переходя к рассмотрению общего случая для Т лент, положим В» = (4Ь + 1) х/ /(4Т вЂ” 2). Производящая функция А(2) для Т лент каскадных чисел принимает вид 4 сов2 В». (12) 2Т вЂ” 1 4-' 1 — 2/(2 вшВ») -тг 2<»<1т»2) (см. упр. 8); следовательно, а„= — 7 сов В» ~ —.— ) 2Т вЂ” 1 4 1,2япВ») — тг 2 <» < 127 21 (13) Соотношения (8) приводят теперь к аналогичным формулам: 4 / Ь„= — ~ ~сов В» сов ЗВ» ( ) 2Т вЂ” 1 4,2 япВ») — Т(2<»<Щ21 4 / 1 с„= ~~г сов В» сов 58» ~ ) 2Т вЂ” 1 1,2вшВ») — 27 2 <» < 1т 1 2. (14) 4 / 1 г/„= совВ» сов 7В» ( ) 2Т вЂ” 1 (,2япВ») — 272 < 1 <1Т/21 и т. д, В упр.
9 показано, что эти уравнения справедливы для всех и > О, а не только для больших и. В каждой сумме член с й = О значительно превосходит все остальные члены, особенно если и достаточно велико. Следовательно, "отношение роста" есть 1 2 1 гг = — Т вЂ” — + — + 0(Т 2). (15) 2 яп Во гг гг 48Т Каскадная сортировка впервые была исследована У. К.
Картером (см. Чг. С. Саг»сг, Ргос. 1Р1Р Сопйтсвв (1962), 62 66)„который получил численные результаты для небольших значений Т, и Дзвидом Э. Фергюсоном 1см. Е. Регбпвоп, САСМ 7 (1964), 297], который открыл первые два члена в асимптотическом поведении (15) отношения роста Летом 1964 года Р. У. Флойд (П. %'. Р1оуг1) получил явный вид 1/(2япбе) для отношения роста, так что точные формулы могли быть использованы для всех Т. Глубокий анализ каскадных чисел был независимо выполнен Дж.
Н. Рэйни (см. С. Х. Вапеу, Сапап5ап,7. Мвг)г. 18 (1966), 332 349), который столкнулся с ними совершенно другим путем, не имея дела с сортировкой. Рэйва заметил принцип "отношения диагоналей", представленный на рис. 73, и вывел много других интересных свойств этих чисел. Флойд н Рэйни в своих доказательствах оперировали матрицами (упр. 6). Модификация каскадной сортировки. Если добавить еще одну ленту, то почти все операции перемотки в процессе каскадной сортировки можно совместить. Например, можно выполнить слияние Т1 Т5 на Т?, Т1 — Т4 на Тб, Т1-ТЗ на Т5 (которая к этому моменту уже перемотана), Т1-Т2 на Т4 и начать следующий проход, когда на Т4 будет перемотано сравнительно немного данных. Эффективность этого процесса можно предсказать на основании изложенного выше анализа каскадного метода (подробности приводятся в разделе 5.4.6).
Схема "компромиссного слияния", которая включает многофазную и каскадную схемы как частные случаи, была предложена Д. Э. Кнутом в САСМ 6 (1963), 585-587. Каждая фаза состоит из (Т вЂ” 1)-, (Т вЂ” 2)-, ..., Р-путевого слияний, где Р— любое фиксированное число между 1 н Т вЂ” 1. Если Р = Т вЂ” 1, значит, это многофазный метод; если Р = 1, это чистый каскадный метод; если Р = 2, это каскадный метод без фаз копирования. Анализ такой схемы был проделан в работах С.
Е. На<Псе, 1ВМ Яуягетпя,1. 5 (1966), 226 — 247, и Ъ'. Н. Впгбе, Ргос. 1Р1Р Сопдгеяя (1971), 1, 454-459. Бурж нашел производящую функцию 2 Т„(х)ва для каждого (Р, Т)-компромиссного слияния, обобщающую соотношение 5.4.2-(16). Он показал, что наилучшее значение Р (с точки зрения наименьшего числа обрабатываемых начальных серий) как функции от Ь' при Ь' — > оо (еслн непосредственно использовать схему распределения и пренебречь временем перемотки) есть соответственно (2,3,3,4,4,4,3,3,4) при Т = (3,4,5,6,7,8,9,16,11). Эти значения Р с ростом Т сильнее отклоняются в сторону каскадного, а не многофазного метода, и оказывается, что компромиссное слияние никогда не станет существенно лучше каскадного. С другой стороны, при оптимальном выборе уровней и распределении фиктивных серий, как описано в разделе 5.4.2, чистый многофазный метод кажется наилучшим среди всех компромиссных методов слияния.
К сожалению, оптимальное распределение сравнительно трудно реализовать. В работе ТЬ. Е. ЛоЬпяеп, В1Т 6 (1966), 129-143, исследовано сочетание сбалансированного и многофазного слияний; модификация сбалансированного слияния с совмещением перемоток предложена в работе М. А. Гоетца (М. А. Свеся), 01я1са) Сошрпгег Няег'я Нкпс)Ьоо)г, М. К!егег, С. А. Когп (Ь[ев Уог[г: МсСгаи-Н!11, 1967), 1.311 — 1.312. Можно представить себе и многие другие гибридные схемы. УПРАЖНЕНИЯ 1.
[1О) Используя табл, 1, сравните каскадное слияние с описанной в разделе 5,4.2 версией мнагофвзяага слияния с "расщеплением лент". Какой метод лучше? (Временем перемотки пренебречь.) 2. [22) Сравните метод каскадной сортировки с тремя лентами, использующий алгоритм С, н метод мнагофвзной сортировки с тремя лентами, использующий алгоритм 5.4.21!. Какие сходства я различия вы заметите? 3. [Яу[ Составьте таблицу, показывающую, что происходит прн сортировке на шести лентах ста начальных серий прн помощи алгоритма С. 4. [МОО) (Дж.
Н. Рэйнн (С. ь?. Вавеу).) "Каскадное распределение и-го уровня" мультнмнажества, определенное следующим образом (для шести лент): (1, О, О, О, О) есть каскадное распределение О-го уровня; если на последующих уровнях (а, Ь, с, 0, а) — каскадное распределение и-га уровня, та (а+Ь+с+а+а, а+Ь+с+д, а+5+с, а+Ь, а) будет каскадным распределением (и+ 1)-га уровня, (Так как мультимнажества не упорядочено, из единственного распределения п-го уровня можно образовать до о! различных распределений (п + 1)-го уровня.) а) Докажите, что любое мультнмножество (а, Ь, с, 0, е) из взаимно простых чисел является каскадным распределением и-го уровня при некотором и. Ь) Докажите, что распределение, используемое в каскадной сортировке, опто.малько в том смысле, что егли [а, Ь, с„И, е) — любое распределение н-го уровня, причем а > Ь > с > 0 > е, то будем иметь а < а„, Ь < Ь„, с < с„, 4 < д, с < е„, где (о„, Ь„, с, 0, е„)— распределение, определенное в (1).
б. [20] Докажите, что каскадные числа, определенные в (?), удовлетворяют закону оьа„ь+ ЬьЬ„ь+ сьс„ь+ 4ьд„ь+еье ь = а„при О < Ь < и. е/г(~)а !/С(,) а„~ — (з) а„-з, ?7Г(,)о ~ — (~~)а -з — („)о -ь е„= а„ 0„= 2ае ~ — е -з с = Зо„-~ -0 -з — 2е„-з = и т. д. Полагая выразите через зти г-миогочлеиы А(х), В(х) и т, д. 11.
[МЭЭ] Пусть Докажите, что производящая функция А(х) для Т-ленточных каскадных чисел есть 1т-з(я)(1т-~ (з), причем числитель и знаменатель этого выражения не имеют общих делителей. 12. [М40) Докажите, что схема распределения Фергюсона оптимальна в том смысле, что при любом другом методе размещения фиктивных серий, удовлетворяющем (2), во время первого прохода будет обрабатываться не меньше начальных серий нри условии, что во время этого прохода используется стратегия шагов С7 — СО. 13. [40] В тексте раздела предполагается большую часть времени перемотки совмещать путем добавления дополнительной ленты, Попытайтесь развить эту идею. (Например, схема, приведенная в тексте, включает ожидание перемотки ленты Т4. Не будет ли лучше исключить Т4 из первой фазы слияния следующего прохода?) [Указанае. Для лучшего понимания этого соотновгения рассмотрите, сколько серий различной длины выводится в течение й-го прохода полной каскадной сортировки.) 6.
[МЭО] Найдите матрицу Я размера о х 5, такую, что первая строка Я" содерясит каскадные числа для шести лент а„Ь„с„0„е„при всех п > О. 7. [М20] При условии, что каскадное слияние применяется к точному распределению а„ начальных серий, найдите формулу для величины сэкономленной работы, когда исключается однопутевое слияние. 8. [ИПЭ] Выведите формулу (12).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
