AOP_Tom3 (1021738), страница 71
Текст из файла (страница 71)
Т1 и а 5« с« 4« в Т(/с) и+ 1 а + 0 а„+ с„а„+ ««„а„+ е а 1„+ 4а„ Т(й — 1) (1) (После начального распределения лента Тб всегда будет пустой.) Из правила перехода от уровня и к уровню и + 1 ясно, что условия (2) а«> 5«> с«> «(„> е« выполняются на любом уровне.
В самом деле, легко видеть из (1), что Е« =а«1, «?« = а«1+Е«1 = а««+а«2, с« = «1« — 1 + «2«-1 = «1« — ) + «1«-2 + а«-3 5« = а«1 + с«1 = а«1 + а«-г + а«-з + а««, «1« = а«1+ 5«1 — — а««+а«-2+ а«з + а««+ а«-з, (3) где ав = 1 и где мы полагаем, что а« = 0 при и = — 1, — 2, — 3, — 4. Уровень 0 1 2 3 4 5 6 7 8 1 1 2 4 8 16 31 61 120 Т2 ТЗ Т4 Т5 0 0 О 0 1 1 1 1 2 2 2 1 4 4 3 2 8 7 6 4 15 14 12 8 30 28 24 16 59 55 47 31 116 108 92 61 Сумма 1 5 9 17 ЗЗ 65 129 253 497 Окончательный результат будет на Т1 Тб Т5 Т4 ТЗ Т2 Т1 Тб Т5 Числа Фибоначчи р-го порядка г„" определяются правилами г„( ) = Р(Р), + Р(п) + ..
+ г„( ) при п > р; Р(~)=О приО<п<р — 2; ~Г~~,=1. (4) Другими словами, мы начинаем с р — 1 нулей, затем пишем 1 и каждое следующее число является суммой р предыдущих чисел. При р = 2 это обычная последовательность Фибоначчн; для больших значений р ее впервые изучил, по-вндимому, В. Шлегель |Ч.
ЯсЫебе!) в Е( Ргойгеэо Ма(ета(гсо 4 (1894), 173-174. Шлегель вывел производящую функцию Е-""- (о) и гг г~ — ег п и 1 г гг ... сп 1 2г + ге+1 и>э (3) Формула (3) показывает, что число серий на Т1 в процессе шестнленточного многофазного слияния является числом Фибоначчи пятого порядка: а„= Ги В общем случае, если положить Р = Т вЂ” 1, распределения в многофазном слиянии для Т лент будут аналогичным образом соответствовать числам Фибоначчи Р-го порядка.
В точном распределении и-го уровня на )с-й ленте будет ~пЛ-Р— г + и-1-Р Ъ + + Рипа — г (Р) (Р) (Р) начальных серий для 1 < )с < Р, а общее количество начальных серий на всех лентах будет, следовательно., равно (и РРп+Р-г + (~ 1) п+Р-г + + Рп-1' (Р) (Р) (Р) (6) Алгоритм 1л (Сортироека методом многофаэного слияния с испольэоеанием пгориэонтпальногои распределения). Этот алгоритм (рис. 68) берет начальные серии и распределяет их одну за другой по лентам, пока запас начальных серий не исчерпается.
Затем он определяет, как необходимо сливать ленты, используя Р-путевое слияние, в предположении, что имеются Т = Р+ 1 > 3 накопителей на магнитной ленте. Ленту Т можно применять для хранения исходньгх данных, так как на нее не записывается ни одна начальная серия. В памяти хранятся следующие таблицы. (( [у), 1 < у < Т: Точное фибоначчиево распределение, к которому мы стремимся 0 (Я, 1 < у < Т: Число фиктивных серий, которые считаются присутствующими в начале ленты на логическом устройстве с номером у' Это решает вопрос о "точном фибоначчиевом распределении".
Но что мы должны делать, если 5 не равно в точности ги ни при каком п7 Как первоначально поместить серии на ленты7 Если 5 не является точным числом Фибоначчи (а чисел Фнбоначчн не так уж много), то можно действовать, как в сбалансированном Р-путевом слиянии, добавляя "фиктивные серии"; поэтому можно считать, что 5, в конце концов, будет точным.
Существует несколько способов добавления фиктивных серий, но мы еще не знаем, как это сделать наилучшим образом. В первую очередь, рассмотрим метод распределения серий и приписывания фиктивных серий, который хотя и не самый оптимальный, но зато достаточно простой и, по-видимому, лучше всех остальных методов такой же степени сложности. Рис. 68. Сортировка методом многофазного слияния.
ТАРЕ[]], 1 < ! < Т: Номер физического накопителя на магнитной ленте, соответствующего логическому устройству с номером ] (Удобно работать с номерами "логических" накопителей на магнитной ленте, соответствие которых физическим накопителям меняется в процессе выполнения алгоритма.) 1!1. (Начальная установка.] Установить А[у] г — О[Я +- 1 н ТАРЕ[!'] < — ] при 1 < у ( Т. Установить А [Т] +- 0 [Т] ~ — О и ТАРЕ [Т] +- Т.
Затем установить 1 е- 1, ] г- 1. Р2. ]Ввод на ленту Д Записать одну серию на ленту у и уменьшить О[у] на 1. Затем, если ввод исчерпан, перемотать все ленты и перейти к шагу П5. 113. !Продвижение г'.] Если О[г] ( О[1'+ Ц, то увеличить у на 1 и вернуться к шагу П2. В противном случае, если О[у] = О, перейти к шагу П4, иначе— установить ] ! — 1 и вернуться к шагу 02.
Р4. (Подняться на один уровень.] Установить 1 < — 1+ 1, а г — А [Ц, затем для у = 1, 2, ..., Р (именно в таком порядке) установить О[у] < — а + А[у + Ц вЂ” А[]] и А[]] г — о+ А[у + Ц. (См. (1). Отметим, что А[Р+ Ц всегда О. В этом месте будем иметь ОШ > 0[2] » .. Р[Т].) Теперь установить у г — 1 и вернуться к шагу П2.
Рб. (Слияние.] Если! = О, то сортировка завершена и результат находится на ТАРЕ Ш. В противном случае выполнять слияние серий с лент ТАРЕ [Ц,..., ТАРЕ[Р] на ТАРЕ[Т] до тех пор, пока ТАРЕ[Р] не станет пустой и О[Р] = О. Процесс слияния для каждой сливаемой серии должен протекать следующим образом. Если 0 [!] > О для всех у, 1 < г' < Р, то увеличить О [Т] на 1 и уменьшить каждое Р []] на 1 для 1 < ! < Р; в противном случае выполнять слияние по одной серии с каждой ленты ТАРЕ[]], такой, что о[у] = О, и уменьшить О[,!] на 1 для остальных г'. (Таким образом, считается, что фиктивные серии находятся в начале ленты, а не в конце.) Т4 Ть Рис.
69. Порядок, в котором серии 34-65 распределяются нз ленты при переходе с уровня 4 на уровень 5. (См. таблицу точных распределений (1).) Заштрихованные области соответствуют первым ЗЗ сериям, которые были распределены к моменту достижения уровня 4. Последняя строка в каждой колонке соответствует началу ленты. 34 35 зв 42 46 51 56 6! Т, 36 39 43 47 52 57 62 Тз 37 46 44 46 58 63 Тз Р6. (Опуститься на один уровень.] Установить 1 +- 1 — 1. Перемотрть ленты ТАРЕ [Р] и ТАРЕ[2'] (В действительности перемотка ТАРЕ[Р] могла быть начата на шаге 05, после ввода с нее последнего блока.) Затем установить (ТАРЕ[1], ТАРЕ[2], ...,ТАРЕ[Т]) +- (ТАРЕ[Т],ТАРЕ[1],...,ТАРЕ[Т вЂ” 1]), (9[Ц,6[2], 6[2]) 4— (9 [Т],0 [Ц,..., 0 [Т вЂ” Ц ) и вернуться к шагу 05, Правило распределения, которое так лаконично сформулировано на шаге 03 этого алгоритма, стремится по возможности уравнять числа фиктивных серий на каждой ленте.
На рис. 69 иллюстрируется распределение серий, когда мы переходим от уроння 4 (ЗЗ серии) к уровню 5 (65 серий) в сортировке с шестью лептами; если было бы, скажем, только 53 начальные серии, то все серии с номерами 54 и выше рассматривались бы как фиктивные. (На самом деле серии записываются в конец ленты, но удобнее считать, что они записываются в начало, так как предполагается, что фиктивные серии находятся в начале ленты.) Мы уже рассмотрели первые три из поставленных выше вопросов; осталось выяснить число "проходов"' по данным.
Сравнивая наш "шестиленточный пример" с таблицей (1), мы видим, что суммарное количество обработанных начальных серий при 5 = 16 составляет аз1з+а46г+оз13+аз14+аз16+аогб, если исключить начальный проход распределения. В упр. 4 выводятся производящие функции 1 а(з) = 7 а„з" = зт зЗ 64 зз' 56+ 462+ Ззз+ 264+ зз (7) 6(з) = ~~~ й~з" = 1 — з — зз — зз — з4 — зз ' л>1 Отсюда следует, что в общем случае число обрабатываемых начальных серий при Я = ьь Ранип КОЭффИЦИЕНтУ ПРИ 3" В ПРОИЗВЕДЕНИИ а(З)1(З) ПЛЮС 1„(зтО ДаЕт начальный проход распределении). Теперь вычисляем асимптотическое поведение многофазного слияния, как показано в упр.
5-7, и получаем результаты, приведенные в табл. 1. В табл. 1 "Относительный рост" есть предел 1пп„4„44/1„, показывающий, во сколько приблизительно раз возрастает число серий на каждом проходе. "Проходы" — это среднее количество обработок каждой записи, а именно — — 1/Я, умноженное на общее число начальных серий, обрабатываемых в течение фаз распреде- Таблица 1 АППРОКСИМАЦИЯ ПОВЕДЕНИЯ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ Ленты Фазы Проходы Проходы/ Относительный фазы, % Рост пения и слияния. Указанные числа проходов и фаз справедливы в каждом случае с точностью до 0(В ') при некотором е > 0 для точного распределения при  — > оо. На рис. 70 изображены в ниде функций от В средние количества слияний каждой записи с помощью алгоритма В для неточных чисел.
Заметим, что при использовании трех лент сразу после точных распределений появляются "пики" относительной неэффективности, но это явление в значительной степени исчезает при наличии четырех или более лент. Использование восьми или более лент дает сравнительно малое улучшение по сравнению с шестью или семью лентами. Более детальный анализ. В сбалансированном слиянии, требующем к проходов, каждая запись обрабатывается в ходе сортировки ровно /г раз.
Но многофазная процедура не является такой беспристрастной: одни записи могут обрабатываться намного больше раз, чем другие, и можно увеличить скорость, если помещать фиктивные серии в часто обрабатываемые позиции. По этой причине проанализируем более подробно многофазное распределение. Вместо того чтобы интересоваться только числом серий на каждой ленте, как в (1), присвоим каждой серии число слияний, т. е. определим, сколько раз она будет обрабатываться в течение всего процесса сортировки.
Вместо (1) получим следующую таблицу. Т1 Т4 ТЗ О 1 21 3221 43323221 5443433243323221 1 2 32 4332 54434332 1 21 3221 43323221 544343324332322 1 21 322 433232 544343324332 1 21 3221 4332322 54434332433232 Сп Пп Еп (Ап+ВП (А +ИЬ' Ап+1 (8) А„ (Ап + 1)Вп В (Ап т 1)Сп и н+1 Здесь Ап — цепочка из ап значений, представляющих числа слияний каждой серии на Т1, если начать с распределения и-го уровня; „— соответствующая цепочка для Т2 и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
