Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 72
Текст из файла (страница 72)
с 2.3.1-(10); верхний узел есть голова списка, пунктирными линнямн показаны прошитые связи. В этом примере мы сосредоточим внимание на сортировке с использованием структуры полного двоичного дерева, когда узел О (аналог гшювы списка) лобввляется перед узлом 1, как в "дереве пронгравшихв на рис. бЗ.) Покажите, как организовать 2"+» внутренних узлов большого дерева проигравших нв этих 2~ основных узлах так, чтобм (1) каждый главный узел удерживал точно 2" узлов болыпого дерева; (й) и большом дереве подсоединенные узлы подключались либо к одному и тому же главному узлу, либо к главным узлам, подсоединенным рядом друг с другом; (!В) никакие две пары соседних узлов и болыиом дереве не разделялись одной и той же связью в главном дереве. (Таким образом, множество виртуальных процессоров в сети большого двоичного дерева можно отобразить на реальные процессоры без нежелательной избыточной перегрузки каналов связи.) ЗО.
[МвУ) Докажите, что если п > )г > 1, то построение в предыдущем упражнении оптимально в том смысле, что любой 2"-узловой основной граф, удовлетворяющий условиям (1), (й) и (1й), должен иметь, по меньшей мере, 2" + 2~ ' — ! ребер (связей) между узлами. «5.4.2. Многофвзное слияние Теперь, после того как мы выяснили, как можно образовать начальные серии, рассмотрим различные методы распределения серий по лентам и их слияния до тех пор, пока не получится единственная серия. Предположим сначала, что в нашем распоряжении имеются три накопителя на магнитных лентах: Т1, Т2 и ТЗ; можно воспользоваться методом сбалансированного слияния, описанным в начале раздела 3.4, назначив Р = 2 и Т = 3.
Алгоритм этого метода принимает следующий вид. В1. Распределить начальные серии попеременно на ленты Т1 и Т2. В2. Выполнить слияние серий с лент Т1 и Т2 на ТЗ, затем остановиться, если ТЗ содержит только одну серию. ВЗ. Скопировать серии с ТЗ попеременно на Т1 н Т2, затем вернуться к шагу В2. 1 Если при начальном распределении получилось Я серий, то прн первом проходе слияния будет образовано (5/2) серий на ТЗ, прн втором — ) 5/4) и т. д.
Таким образом, если, скажем, 17 < 5 < 32, то произойдет 1 проход распределения, 5 проходов слияния н 4 прохода копирования. В общем случае, если Я > 1, число проходов по всем данным будет равно 2()бЯ). Проходы копирования в этой процедуре нежелательны, так как они не уменьшают числа серий. Можно наполовину сократить количество копирований, если использовать двухфазную процедуру. А1. Распределить начальные серии попеременно на ленты Т1 н Т2.
А2. Слить серии с лент Т1 и Т2 на ТЗ; остановиться, если на ТЗ содержится только одна серия. АЗ. Скопировать половину серий ТЗ на Т1. А4. Слить серии с лент Т1 и ТЗ па Т2; остановиться, если на Т2 содержится только одна серия. Аб. Скопировать половину серий с Т2 на Т1. Вернуться к шагу А2. 1 Число пРоходов по всем данным сокРатилось до гг !'18 з'! + 1, так как на шагах АЗ и А5 выполняется только "половина прохода", т. е. сэкономлено около 25% времени. Б действительности можно даже нолносвгью устранить копирование, если начать с Г„серий на ленте Т1 и Г„г серий на Т2, где Г„и Г„г — последовательные числа Фибоначчи.
Рассмотрим, например, случай, когда и = 7, Я = Г„+ Г„г = 13+ 8 = 21. Содержимое Т2 Содержимое ТЗ Содержимое Т1 Примечание Здесь 1з' обозначает 31 серию относительной длины 1 и т. д.; везде используется пятипутевое слияние. Эта общая схема была представлена в работе Н. 1. Сйзсаб, Ргос.
Баз!егл,уо!лс Сотрпсег СазЕ 18 (1960), 143-148, в которой она названа многефазнмм слиянием. Случай для трех лент был открыт Б. К. Бетцем (В. К. Ветх) !неопубликованная заметка, М!ппеаро1!з-Нопеугге!! Вейн!асог Со. (1956)). Чтобы заставить механизм многофазного слияния работать, как в предыдущем примере, необходимо после каждой фазы иметь "точное фибоначчиево распреде.
1 1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1„1,1,1,1 Начальное распределение 3 — 3,3,3,3,3 2,2,2 Слияние 5 серий на ТЗ 4 5,5,5 33 — Слияние 3 серий на Т1 5 5 8,8 Слияние 2 серий на ТЗ 6 13 8 Слияние 1 серии на Т2 7 21 Слияние 1 серии ва Т1 Здесь "2,2,2,2„2,2„2,2", например, обозначает восемь серий относительной длины 2, если считать относительную длину каждой начальной серии равной 1. Всюду в этой таблице присутствуют числа Фибоначчи! Полный проход по данным осуществляется только на фазах 1 и 7; на фазе 2 обрабатывается лишь 167'21 от общего числа начальных серий, на фазе 3 — лишь 15/21 и т. д.
Таким образом, суммарное число "проходов" равно (21+16+15+15+16+ 13+ 21)/21 = Ц, если предположить, что начальные серии имеют примерно равную длину. Для сравнения заметим, что рассмотренная выше двухфазная процедура затратила бы 8 проходов на сортировку этой 21 начальной серии. Мы увидим, что в общем случае данная схема Фябоначчи требует приблизительно 1.04!85 + 0.99 проходов, что делает ее сравнимой с четмрехленгпочнььи сбалансированным слиянием, хотя она использует только три ленты. Эту идею можно обобщить для Т лент при любом Т > 3, используя (Т вЂ” 1)- путевое слияние. Мы увидим, например, что для четырех лент требуется только около .703 !8 8+0.96 проходов по данным.
Обобщенная схема использует обобщенные числа Фибоначчи. Рассмотрим следукиций пример с шестью лентами. Фаза Т1 Т2 ТЗ Т4 Т5 Т6 Число обрабатываемых начальных серий 1гг 1го 1га 1ы 1ге 31 + ЗО + 28+ 24+ 16 = 129 1м 1ы 1 ге 1г За 16х5= 80 3 1' 1 1' — 9 5г 8х9= 72 4 1 1 — 17 9 5~ 4х17= 68 5 1' — ЗЗг 17г 9 5г 2 х 33 ьг 66 6 — 65' 33' 17 9' 5' 1хбйж 65 129' 1 х 129 ж 129 ление" серий по лентам. Читая приведенную выше таблипу снизу вверх, можно заметить, что первые семь точных фибоначчиевых распределений при Т = 6 суть (1,0,0,0,0), [1,1,1,1,1), (2,2,2,2,1), (4,4>4,3,2), (8,8,7,6,4), (16,15,14,12,8) (31,30,28,24,16).
Теперь перец нами стоят следующие важные вопросы, 1. Какое правило скрыто за этими точными фибоначчиевыми распределениями? 2, Что делать, если Я не соответствует фибоначчиевому распределению? 3. Как построить начальный проход распределения, чтобы на нем порождалось нужное расположение серий на лентах? 4. Сколько "проходов" по данным потребует Т-ленточное многофазное слияние (как функция от Я вЂ” числа начальных серий)? Мы обсудим зги четыре вопроса по очереди; сначала дадим "простые ответы", а затем займемся более глубоким анализом, Точные фибоиаччиевы распределения можно получать, "прокручивая" рассмотренную схему в обратном направлении и циклически переставляя содержимое лент. Например, при Т = 6 имеем следующее распределение серий. и а» Ь„с„д е, з» Т(Ь) я+1 а„+Ь а +с а +8» а»+с» а» З»+4а„ Т(Ь вЂ” 1) (1) (После начального распределения лента Тб всегда будет пустой.) Из правила перехода от уровня и к уровню и + 1 ясно, что условия (2) а„> Ь„> с„> з(„> е выполняются на любом уровне, В самом деле, легко видеть из (1), что е„= а„м И„= а„з +с» з = а„з+ а„з, с„=а» з+И» 1=а» з+а з+а„з, Ь» = а~-г + с»-з = а»-з + а»-з + а»-э + а»-з~ а =а„з+Ь 1=а з+а з+а„з+ач 4+а з, (3) где ае = 1 и где мы полагаем, что а = 0 при я = -1, -2, -3, -4.
Уровень 0 1 2 3 4 5 В 7 8 Т1 Т2 ТЗ 1 О 0 1 1 1 2 2 2 4 4 4 8 8 7 16 И 14 31 30 28 61 59 55 120 116 108 Т4 0 2 3 б 12 24 47 92 Т5 Сумма 0 1 1 5 1 9 2 17 4 33 8 65 1б 129 31 253 61 497 Окончательный результат будет ва Т1 Тб ТЬ Т4 ТЗ Т2 Т1 Тб Т5 Числа Фибонвччи р-во порядка Р„'~) определяются правилами Р(Р)=Р(),+~® + +~® пр п>р; (4) Р(~) = 0 прн 0 < и < р — 2; Р(Р), = 1. Другими славами, мы начинаем с р — 1 нулей, затем пишем 1 и каждое следующее число является суммой р предыдущих чисел.
При р = 2 зто обычная последовательность Фибоначчн; для болыпих значений р ее впервые изучил, по-видимому, В. Шлегель (Ъ'. ВСЫейе!) в Е! Ргойгезо Матеша((со 4 (1694), 173-174. Шлегель вывел производящую функцию Ег" 64» р-! хр-4 зр — — — — ! - 2 + р+' п>0 Формула (3) показьгвает, что число серий на Т1 в процессе шестиленточного много- фазнОГО слияния является числом Фибоначчи пятОГО порядка и» Р 4 В общем случае, если положить Р = Т вЂ” 1, распределения в многофазном слиянии для Т лент будут аналогичным образом соответствовать числам Фибоначчи Р-го порядка. В точном распределении н-го уровня на й-й ленте будет (г) (и) (г) " +»-в+ Р+) -з+'''+ Р+ь-з начальных серий для 1 < Й < Р, а общее количество начальных серий на всех лентах будет, следовательно, равно (6) Это решает вопрос о "точном фибоначчиевом распределении".
Но что мы должны делать, если О не равно в точности Г» ни при каком ну Как пврвоначальио поместить серии на ленты? Если О не является точным числом Фибоначчи (а чисел Фибоначчи не так уж много), то можно действовать, как в сбалансированном Р-путевом слиянии, добавляя "фиктивные серии"; позтому можно считать, что О', в конце концов, будет точным. Существует несколько способов добавления фиктивных серий, но мы еще не знаем, как это сделать наилучшим Образом.
В первую очередь, рассмотрим метод распределения серий и приписывания фиктивных серий, который хотя и не самый оптимальный, но зато достаточно простой и, по-видимому, лучше всех остальных методов такой же степени сложности. Алгоритм Р ! Сарншровка мвнк»)ом многа(равного слияния с использованием "горизонниьтьногв" раснре4)слепня). Этот алгоритм (рис. 66) берет начальные серии и распределяет их Одну за другой по лентам, пока запас начальных серий не исчерпается. Затем он определяет, как необходимо сливать ленты, используя Р-путевое слияние, в предположении, что имеются Т = Р+ 1 > 3 накопителей на магнитной ленте, Ленту Т можно применять для хранения исходных данных, так как на нее не записывается ни одна начальная серия.
В памяти хранятся следующие таблицы. А(Я, 1 < ! < Т: Точное фибоначчиево распределение, к которому мы стремимся РЦ), 1 < ) < Т: Число фиктивных серий, которые считаются присутствующими в начале ленты на логическом устройстве с номером у Рис, 68, Сортировка методом мвогофазиого слияния. ТАРЕ Ц3, 1 < 3 < Т: Номер физического накопителя на магнитной ленте, соответствующего логическому устройству с номером у (Удобно работать с номерами "логических" накопителей на магнитной ленте, соответствие которых физическим накопителям меняется в процессе выполнения алгоритма.) 01.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
