AOP_Tom3 (1021738), страница 76
Текст из файла (страница 76)
Фергюсон (РатЫ Е. Еегйцэоп) сумел так распределить начальные серии, что многие операции во время первой фазы слияния свелись к копированию содержимого ленты. Обойдя такие копирования (просто изменив "логические" номера ленточных устройств по отношению к "физическим" номерам, как в алгоритме 5.4.2П), получим относительно плавный переход от одного уровня на другой, как изображено на рис.
74. Предположим, что (а, Ь,с,й, е), где а > Ь > с > й > е — точное распределение. Изменив соответствие между логическими и физическими ленточными устройствами, можно представить, что реальное распределение — (е,а,с,Ь,а), т. е. а серий на Т5, Ь вЂ” на Т4 и т. д. Следующее точное распределение — это (а+ Ь+ с+ Ы+ е, а+ 5+с+И, а+ 5+с, а+Ь, а); если же ввод исчерпывается прежде, чем мы достишем этого следующего уровня, будем считать, что на лентах содержится соответственно (Рм.Рэ, Рз, Рэ, Рэ) фиктивных серий, где П~ < а+Ь+с+й, Пг < а+Ь+с, Пэ < а+Ь, Пэ < а, Пэ =0; % > Рэ > Пз > Рэ > Па (2) Мы вольны представлять себе, что эти фиктивные серии появляются на лентах в любом удобном месте.
Предполагается, что первый проход слиянии сначала даст а серий посредством пятипутевого слияния, затем — Ь серий посредством четырех- путевого и т. д. Наша цель состоит в размещении фиктивных серий таким образом, чтобы заменить слияние копированием. Ъдобно вьпюлнять первый проход слияния следующим образом. 1. Если Р4 = а, то вычесть а из всех Пм Рэ, Рэ, Р4 и заявить, что Т5— результат слияния. Если Пэ < а, то произвести слияние а серий с лент Т1 по Т5, используя минимально возможное число фиктивных серий на лентах от Т1 до Т5 Т-3 т-4 Т 5 Т 0 Т 7 т-0 Т=т Рис.
74. Эффективность каскадного слияния с распределением по алгоритму 13. так, чтобы новые значения Рм Рг, Рг, .Р» удовлетворяли соотношениям Рг < 6+с+»1 Рг < Ь+с Рг <Ь. Р» — 0 Р~ > Рг > Рг > Р» ° (3) Таким образом, если Рг было первоначально < Ь+ с., ни одна фиктивная серия с этой ленты на данном шаге не используется.
В то же время, если 6+с < Рг < а+6+с, используется ровно Рг — 6 — с фиктивных серий. 2. (Этот шаг аналогичен шагу 1, но с некоторым "сдвигом".) Если Рэ = Ь, то вычесть 6 нз всех Рм Рг, Рг и объявить, что Т4 — результат слияния. Если Х15 < 6, то слить 6 серий с лент Т1-Т4, уменьшая, если необходимо, число фиктивных серий, чтобы достичь 3. И так далее. Метод распределения серий по лентам Фергюсона можно проиллюстрировать, рассмотрев переход с уровня 3 на уровень 4 в 11). Допустим, что на "логических" лентах 1Т1,...,Т5) содержалось соответственно (5,9,12,14,15) серий и что необходимо довести это количество до (55, 50, 41, 29, 15). Данная процедура кратко описана в табл.
2. Сначала помещаем девять серий на Т1, затем (3, 12) — на Т1 и Т2 и т. д. Если ввод исчерпывается, скажем, на шаге (3, 2), то асэкономленная величина" составляет 15+ 9+ 5. Это означает, что мы избавляемся от пятнпутевого слияния и 0 и 5 5 4 У 3 2 5 10 20 50 100 200 500 1000 2000 5000 Неча»анна сарая, Я Р,<Ь+с, Рг<Ь, Р5=0; Р»>Рг>Р3.
Таблица 2 ПРИМЕР ПОШАГОВОГО РАСПРЕДЕЛЕНИЯ Добавить Добавить Добавить Добавить "Сэкономлено" кТ2 кТ3 кТ4 кТ5 Добавить к Т1 15 серий, двухпутевого слияния 9 серий и однопутевого слияния 5 серий посредством присвоения фиктивных серий. Другими словами, 15+ 9+ 5 серий, присутствующих на уровне 3, не обрабатываются в течение первой фазы слияния.
Следующий алгоритм детально описывает этот процесс. Алгоритм С (Свршировка мешодвм каскадного слияния со специальным распределением). Данный алгоритм (рис. 75) распределяет начальные серии по лентам серия за серией, пока запас начальных серий не исчерпается. Затем он определяет, как следует выполнять слияние лент, предполагая, что имеется Т > 3 накопителей на магнитных лентах, при этом используется самое большое (Т вЂ” 1)-путевое слияние и ненужные однопутевые слияния устраняются. Лента Т может использоваться для хранения исходных данных, так как на нее не попадает ни одна начальная серия. Алгоритм работает со следующими массивами.
А[(], 1 < (' < Т: Последнее точное каскадное распределение, которое было достигнуто АА[(], 1 < ] < Т: Точное каскадное распределение, к которому мы стремимся 0[1], 1 < ( < Т: Число фиктивных серий, которые, как мы предполагаем, присутствуют на логическом накопителе на магнитной ленте с номером ( И[]], 1 < ( < Т: Максимальное число фиктивных серий, которые желательно иметь на логическом накопителе на магнитной ленте с номе- ром ] ТАРЕ[]], 1 < ( < Т; Номер физического накопителя на магнитной ленте, соответствующий логическому накопителю на магнитной ленте с номером ( С1. (Начальная установка.) Установить А [А] +- АА[А] +- О [А] ( — О при 2 < А < Т. Установить А[1] +- О, АА[1] +- 1, О[1] +- 1. Установить ТАРЕИ] +- /с при 1 < А < Т.
Наконец, установить 1+- Т вЂ” 2, (' 4 — 1, А ( — 1, 1+- О, т +- 1 и перейти к шагу С5. (Эти действия являются одним из способов начать работу непосредственно во внутреннем цикле, уже имея соответствующую установку управляющих переменных.) Шаг (1,1) Шаг (2,2) Шаг (2,1) Шаг (3,3) Шаг (3,2) Шаг (3,1) Шаг (4,4) Шаг (4,3) Шэг (4,2) Шаг (4,1) О 12 0 2 12 0 1 2 12 0 0 0 0 14 0 0 1 14 0 0 О 0 0 0 0 0 15 о 0 0 15+ 14+ 12+ 5 15+14+9+5 15+14+5 15+12+5 15+9+5 15+5 14+5 12+ 5 9+5 5 Рис.
75. Каскадное слияние со специальным распределением. С2. [Начать новый уровень.] (Точное распределение только что получено. Но так как ен1е имеются исходные данные, необходимо подготовиться к следующему уровню.) Увеличить 1 на 1. Установить А [й) < — АА [Ц при 1 < А < Т и АА[Т вЂ” Ц +- АА[Т вЂ” А+ Ц + А[Ц при А = 1, 2, ..., Т вЂ” 1 (именно в таком порядке). Установить (ТАРЕ[Ц,...,ТАРЕ[Т-1)) +- (ТАРЕ[Т-1), ТАРЕ[И) и ОЫ +- АА[й+ П при 1 < А < Т.
Наконец, установиты + — 1. Са. [Начать подуровены.] Установить у е- 1. (Переменные 1 и у представляют "шаг (г, у')" в табл. 2, иллюстрирующей метод Фергюсона.) С4. [Начатыпаг (г.,у).) Установить й ~- 1 и т +- А[Т вЂ” у' — Ц. Если т = О и 1 = у, то установнты с — Т вЂ” 2 и вернуться к шагу СЗ; если гп = О и 1 ф у', вернуться к шагу С2. (Переменная т представляет собой число серий, которые должны быть записаны на ленту ТАРЕ[К; т = О бывает равно О только в случае, если 1 = 1,) Сб.
[Записать части исходных данных на ленту ТАРЕ[А].] Записать одну серию наленту номерТАРЕ[к1 и уменьшить О[из на1. Затем, если вводисчерпан, перемотать все ленты и перейти к шагу СТ. СВ. [Продвижение.) Уменьшить т на 1. Если ги > О, вернуться к шагу С5. В противном случае уменьшить Й на 1: если Й ) О, установить т ~— А[Т вЂ” у' — Ц вЂ” А [Т вЂ” Я и вернуться к шагу С5, если т > О. В противном случае уменьшить ( на 1; если у > О, перейти к шагу С4, в противном случае увеличиты на 1; если 1 < Т вЂ” 1, вернуться к шагу СЗ.
В противном случае перейти к шагу С2. СТ. [Подготовка к слиянию.) (К этому моменту начальное распределение завершено и таблицы АА, О и ТАРЕ описывают состояние всех лент в данный момент.) Установить И[А] +- АА[А+ Ц при 1 < й < Т и установить Г1ЕБТ с — 1. (Переменная Р1ЕБТ принимает ненулевое значение толька во время первого прохода слияния,) СБ. [Каскад.] Если ( = О, остановиться; сортировка завершена, вывод находится на ТАРЕ [Ц.
В противном случае при р = Т вЂ” 1, Т вЂ” 2, ..., 1 (именно в такам порядке) выполнять р-путевое слияние с лент ТАРЕ [Ц, ..., ТАРЕ [р] на ТАРЕ [р -~- Ц следующим образом. Если р = 1, моделировать однопутевое слияние посредством обычной перемотки ТАРЕ[2] и замены ТАРЕ [Ц ~+ ТАРЕ[2]. В противном случае, если Р1ЕБТ = 1 и Р[р — Ц = И[р — Ц, моделировать р-путевое слияние, просто поменяв ТАРЕ[р] <-э ТАРЕ[р + Ц, перемотав ТАРЕ[р) и выполнив вычитание И[р — Ц из каждого О[Ц,.,., О[р — Ц, ИШ, ...,И[„-Ц. В противном случае вычесть И[р — Ц из всех ИШ,...,И[р — Ц, Затем слить по одной серии с каждой ТАРЕ [у), такой, что 1 < у < р и О [)) < И [Я; вычесть единипу из каждого О [у), такого, что 1 < ] < р и О[]) > И []), и помесить выводную серию на ТАРЕ[р+ Ц.
Продолжать работу, пока ТАРЕ[р] не станет пустой. Затем перемотать ТАРЕ[р] и ТАРЕ[р + Ц . С9. [Опуститься на уровень.] Уменьшить 1 на 1, установить Р1ЕБТ +- О и установить (ТАРЕ[Ц,..., ТАРЕ[Т]) е — (ТАРЕ[Т],...,ТАРЕ[Ц). (К этому моменту все О и И вЂ” нули; таковыми они и останутся.) Вернуться к шагу С8.. 1 На шагах С1-Сб алгоритма С выполняется распределение, на шагах СТ вЂ” С9— слияние.
Эти две части совершенно независимы одна от другой, и можно было бы хранить И[А] и АА [А + Ц в одних н тех же ячейках памяти. Анализ каскадного слияния. Каскадное слияние поддается анализу с ббльшим трудом, чем мнагофазнос. Но этот анализ особенно интересен, поскольку содержит много замечательных формул.
Настоятельно рекомендуем читателям, интересующимся дискретной математикой, самостоятельно проанализировать каскадное распределение прежде, чем чишашь дальше. Ведь числа имеют так много необычных свойств, открывать которые для себя — — одно удовольствие! Мы обсудим здесь лишь один из многих подходов, обращая особое внимание на методы получения результатов. Для удобства рассмотрим гтучай для шести лент.
При этом будем стараться получить формулы, которые обобщаются для любого Т. Соотношения (1) позволяют получить первую основную систему: (о) а (О) и (2) (о) а» (2) а» 2+ (4) а» 4' = (о)а»-(4)а» 2+( )а» 4-(о)а» о, а»=а» Ь»=а»-е» 2 ໠— а» 2 Ь„- 1„, Ь» а»-2 Ь»-2 с»вЂ” (4) с» — е» с» а»-2 Ь»-2 с»-2 е» =И„-Ь» а» 2 Ьп 2 С» 2 ~(~ 2 (О)ап (2)ап 2+(4)а» 4 (О)а» О+(О)ап-В' ОбаэиаЧИМ А(2) = 2 п>еа»2", ..., Е(2) = 2» Е»2» И ОнрсдЕЛИМ МНОГОЧЛЕНЫ - =()-( )".( )"-— — )( — 1)2222 = ~ ( )( — 1) ~2~ 2". (5) ь 2=0 Результат (4) кратко можно истолковать так, что В(2) — д2(2)А(2), С(2) -й2(2)А(2) П(2) — » (2)А(2) и Е(2) — О4(2)А(2) сводятся к конечным суммам, соответствующим граничным условиям, а именно — значениям а „а 2, а 2,..., которые появляются в (4) (при небольших и), но не в А(2).
Чтобы получить подходящие граничные условия, применим рекуррентное соотношение в обратную сторону для отрицательных уровней вплоть до уровня -8. ап Ь« сп е» О 1 ΠΠ— 1 О О О -2 1 -1 Π— 3 О О О -4 2 — 3 1 — 5 О О 1 — 6 5 — 9 5 -7 О -1 6 -8 14 -28 20 (Для семи лент таблица была бы аналогичной, однако строки с нечетными и были бы сдвинуты вправо на один столбец.) Тайна последовательности ао,а з,а 4,... = 1, 1,2,5, 14,... мгновенно раскрывается специалистам по информатике, так как эта последовательность встречается в связи с очень большим числом рекурсивных алгоритмов (см., например, упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
