Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 77
Текст из файла (страница 77)
Только 25 из 950 обрабатываемых серий принадлежат этому классу. Большая часть времени уходит на пятипутевое и четырехпутевое слияния. На первый взгляд может показаться, что каскадная схема проигрывает в сравнении с многофазной, так как стандартная многофазная схема всегда использует «5.4.3. Каскадное слияние Другая основная схема, называемая каскадным слиянием, на самом деле была изобретена раньше миогофазной [см. В.
К. Весе, %. С. Саггег, .4СЫ 1»аг»опв) СопГ. 14 (1959), Рарег 14). Ниже, в таблице, этот подход иллюстрируется для шести лент и 190 начальных серий с использованием обозначений из раздела 5.4.2. Таблица 1 ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ КАСКАДНОГО СЛИЯНИЯ Лепты Проходы (с копированием) Проходы (без копирования) Отношение роста (Т -1)-путевое слияние в то время как каскадная использует (Т вЂ” 1)-путевое, (Т вЂ” 2)- путевое, (Т вЂ” 3)-путевое и т. д. В действительности же для шести и более лент каскадная схема асимптотически лучше, чем многофвзная.
Как мы видели в разделе 5.4.2, высокий порядок слияния не является гарантией эффективности. В табл. 1 показаны характеристики выполнения каскадного слияния по аналогии с подобной таблицей из раздела 5.4.2. Нетрудно, рассуждая "в обратном направлении" от конечного состояния (1, О, ...,О), вывести "точные распределения" для каскадного слияния. В случае дпя шести лент имеем следующее.
Уровень Т1 Т2 ТЗ Т4 Т5 и а„ Ь„ сп с(„е„ и+1 а„+Ь„+с„+!(„+е„а„+Ь„+с„+4, а„+Ь +с а„+Ь„а„(1) Отметим интересное свойство этих чисел — их относительные величины являются также и длинами диагоналей правильного (2Т вЂ” 1)-угольника. Например, пять диагоналей одиннадцатиугольника на рис. 73 имеют относительные длины, очень близкие к 190, 175, 146, 105 и 55! Мы докажем ниже в этом разделе такой замечательный факт и увидим, что значения относитечьного времени, затрачиваемого на (Т вЂ” 1)-, (Т вЂ” 2)-,..., 1-путевое слияние, приблизительно пропорциональны кеадратпа и длин этих диагоналей, Начальное распределение серий. Если число начальных серий в действительности не есть число Фибоначчи, можно, как обычно, вставить фиктивные серии.
Даже из поверхностного анализа ситуации ясно, что метод приписывания фиктивных серий здесь работать не будет, так как при каскадном слиянии всегда выполняются О 2 3 5 3 4 5 6 7 8 9 10 20 2.078 1п й + 0.672 1.235 !и 3 + 0.754 0.946 !и 3 + 0.796 О. 796 1п 3 + 0.821 0.703 !п 8 + 0.839 0.639 !п 5 + 0.852 0.592!из + 0.861 0.555 1п 3+ 0.869 0,397!и 3+ 0.905 1 1 5 15 55 190 0 1 14 50 175 1.504 1п б+ 0.992 1.102 1пЯ+ 0.820 0.897 1п 5+ 0.800 0.773 1п 8 + О. 808 0.691 !и 3+ 0.822 0.632 !п3+ 0.834 0,587 !п 5+ 0.845 0.552!иб+ 0,854 0.397 1п5+ 0.901 О 1 3 12 41 146 1,6180340 2.2469796 2.8793852 3. 5133371 4.1481149 4.7833861 5.4189757 6.0547828 12.4174426 О О 1 1 2 1 9 5 29 15 105 55 Рнс. 73.
Геометрическая интерпретання каскадных чисел. полные проходы. Если имеется 190 начальных серий, то каждая запись обрабатывается пять рвз, как в приведенном выше примере, но если имеется 191 серия, то, очевидно, следует увеличить уровень. Теперь каждая запись будет обрабатываться шесть раз. К счастью, на практике можно избежать такого резкого скачка.
Данаид 3. Ферпосон (0ати( Е. Регйцзоп) сумел так распределить начальные серии, что многие операции во время первой фазы слияния свелись к копированию содержимого ленты. Обойдя такие копирования (просто изменив "логические" номера ленточных устройств по отношению к "'физическим" номерам, как в алгоритме 5.4.20), получим относительно плавный переход от одного уровня на другой, как изображено на рис. 74. Предположим, что (а, Ь, с, И, е), где а > Ь > с > 4 > е — точное распределение, Изменив соответствие между логическими и физическими ленточными устройствами, можно представить, что реальное распределение — (е,Ф,с,Ь,а)„т. е. а серий на Т5, Ь вЂ” на Т4 и т.
д. Следующее точное распределение — это (а+ Ь+ с+ И+ е, а+ Ь+ с+ 4, а+ Ь+ с, а+Ь, а); если же ввод исчерпывается прежде, чем мы достигаем этого следующего уровня, будем считать„что на лентах содержится соответственно (0„.0з,.0з, 0з, 0з) фиктивных серий, где .0з <а+Ь+с+И, 0з<а+Ь+с, 0з<а+Ь, 0з<а, 0з=О; .01 >0з >Юз>0з>0з. (2) Мы вольны представлять себе, что зти фиктивные серии появляются на лентах в любом удобном месте. Предполагается, что первый проход слияния сначала даст а серий посредством пятипутевого слияния, затем — Ь серий посредством четырех- путевого и т.
д. Наша цель состоит в размещении фиктивных серий таким образом, чтобы заменить слияние копированием. Удобно выполнить первый проход слияния следующим образом. 1. Если О» = а, то вычесть а из всех 0ы 0з, 0з, 0з и заявить, что Т5— результат слияния. Если 04 < а,. то произвести слияние а серий с лент Т1 по Т5, используя минимально возможное число фиктивных серий иа лентах от Т1 до Т5 Т 5 Т 4 Т 5 Т 7 т в Т Ю Рис. 24, Эффективность каскадного сляяияя с распределением ао алгоритму О.
так, чтобы новые значения .02, Рт, Рз, Рв удовлетворяли со тношениям 02 <ь+с+и, .02 <ь+с, Рз <ь, Рв =0; Рв >.02 > 05 >Рв Р) Таким образом, если Рз было первоначально < Ь+ с, ни одна фиктивная серия с этой ленты на данном шаге не используется, В то же время, если Ь+с < Х12 < а+Ь+с, используется ровно 02 — Ь вЂ” с фиктивных серий. 2. (Этот шаг аналогичен шагу 1, но с некоторым "сдвигом",) Если Х15 = Ь, то вычесть Ь из всех Ры .02, Рз и объявить, что Т4 — результат слияния. Егли,00 < Ь, то слить Ь серий с лент Т1-Т4, уменьшая, если необходимо, число фиктивных серий, чтобы достичь 3. И так далее.
Метод распределения серий по лентам Фергюсона можно проиллк1стрировать, рассмотрев переход с уровня 3 на уровень 4 в 11). Допустим, что на "логических" лентах (Т1„..., Т5) содержалось соответственно 15,9, 12, 14,15) серий и что необходимо довести это количество до (55, 50, 41, 29, 15). Данная процедура кратко описана в табл. 2. Сначала помещаем девять серий на Т1, затем 13, 12) — на Т1 и Т2 и т.
д. Если ввод исчерпывается, скажем, на шаге 13, 2), то "сэкономленная величина" составляет 15+ 9+ 5, Это означает, что мы избавляемся от пятипутевого слияния 1" я к ив Ф *1 а У 2 5 1О 20 50 160 200 МО 1000 М60 %00 Начелмом елряя, Я Р2 <Ь+с, Рз<Ь, 05=9; 02 >Рз>Рз. Таблица 2 ПРИМЕР ПОШАГОВОГО РАСПРЕДЕЛЕНИЯ Добавить Добавить Добавить Добавить Добавить "Сэкономлено" кТ1 кТ2 кТ3 кТ4 кТЬ Шаг (1,1) Шаг (2,2) Шаг (2„1) Шаг (3,3) Шаг (3,2) Шаг (3,1) Шэг «4,4) Шаг (4,3) Шаг (4,2) Шаг (4,1) 0 0 0 14 0 0 1 14 0 О 0 0 0 0 0 0 15 О 0 0 0 12 0 2 12 0 1 12 0 15+14+12+5 15+ 14+ 9+ 5 15+14+Ь ГО+12+ 5 15+9+5 15+5 14+5 12+5 9*5 5 15 серий, двухпутевого слияния 9 серий и однопутевого слияния 5 серий посредством присвоепия фиктивных серий.
Другими словами, 15+ 9+ 5 серий, присутствующих на уровне 3, не обрабатываются в течение первой фазы слияния. Следующий алгоритм детально описывает этот процесс. С1. (Начальная установка.] Установить А [А) е- АА [А) +- О [А) +- О при 2 < А < Т. Установить А[1) е- О, ААШ < — 1, ОШ е- 1. Установить ТАРЕЫ +- й при 1 < А < Т. Наконец, установить т е- Т вЂ” 2, 1' е — 1, А +- 1, «+- О, т +- 1 и перейти к шагу С5. (Эти действия являются одним из способов начать работу непосредственно во виутрением цикле, уже имея соответствующую установку управляющих перемениых.) Алгоритм С (Сарглпраека методом каскадного слилпил со спецва.и пмм распре- делением). Данный алгоритм (рис.
75) распределяет начальные серии по лентам серия за серией, пока запас начальных серий ве исчерпается. Затем ок определяет, как следует выполнять слияние лепт, предполагая, что имеется Т > 3 накопителей на магнитных лентах, при этом используется самое большое (Т -1)-путевое слияние и ленужпые однопутевые слияния устраняются. Лента Т может использоваться для храпения исходных данных, так как ва нее не попадает яи одна начальная серия. Алгоритм работает со следующими массивами, А[1), 1 < т < Т: Последиее точное каскадное распределение, которое было достигнуто АА[т), 1 < ( < Т: Точное каскадное распределение, к которому мы стремимся О [т), 1 < ( < Т: Число фиктивных серий, которые, как мы предполагаем, присутствуют на логическом накопителе на магиитной ленте с покером,3 И[тЗ, 1 < т' < Т: Максимальное число фиктивных серий, которые желательно иметь на логическом накопителе на магнитной ленте с номе1юм т' ТАРЕ[ З, 1 < т < Т: Номер физического накопителя на магиитной лепте, соответствующий логическому накопителю на магиитцой ленте с номером ( Рнс.
ТБ. Каскадное слияние со специальным распределением. С2. [Начать новый уровень.] (Точное распределение только что получено. Но так как еше имеются исходные данные, необходимо подготовиться к следующему уровню.) Увеличить 1 на 1, Установить А[23 +- ААЩ прн 1 < А < Т и АА[2' — Ф3 +- АА [Т вЂ” Й+ 13 + А [АЗ при Й = 1, 2, ..., 2"-1 (именно в таком порядке). Установить (ТАРЕШ,...,ТАРЕ[Т-13) ~ — (ТАРЕ[Т-13,..., ТАРЕ Ш) н 0 [АЗ +- АА [А+ Ц при 1 < Й < Г.
Наконец, устаиовиты +- 1, СЗ. ]Начать подуровень 1.] Установить 3 +- Е (Переменные 1 и у представляют "шаг (1,3)" в табл. 2, иллюстрирующей метод Фергюсона.) С4. ]Начать шаг (1,3).] Установить А +- 3 и гп ь- А [Т вЂ” у — 13. Если т = О и 1 =,у, то установиты ~ — Т вЂ” 2 и вернуться к шагу СЗ; если ш = 0 и 1 ~ 3, вернуться к шагу С2. (Переменная гл представляет собой число серий, которые должны быть записаны на ленту ТАРЕ [А3; т = 0 бывает равно 0 только в случае, если 1 = 1.) Сб. ]Записать части исходных данных на ленту ТАРЕ[А3.] Записать одну серию на ленту номер ТАРЕ [А3 и уменьшить 0[А3 на 1. Затем, если ввод исчерпан, перемотать все ленты и перейти к шагу С7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
