Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 24
Текст из файла (страница 24)
2.13 можно вывестн соотношения а«в и а«1 2 ! > а1!+и ««~ 1!ЛЯ 1> ~ =а,'+а, проходе 6 серий сливаются иа 16; в конце работы на ленте 12 содержится отсортированное множество элементов (см. рис. 2.16). Миогофазная сортировка более эффективна, чем сбалансированная сортировка, поскольку, если даны М лент, она всегда имеет дело с (М вЂ” 1)-путевым слиянием вместо М/2- путевого слияния. Поскольку число требующихся проходов приблизительно равно 1опл и, где и — число сортируемых элементов, а й1 — чнсло входных лент для слияния, многофаз. ный метод обещает дать значительное улучшение по сравнению со сбалансированным слиянием.
Разумеется, в приведенных примерах было тщательно подобрано распределение начальных серий. Для того чтобы узнать, какие исходные распределения серий требуются для правильной работы алгоритма, мы пойдем обратным путем, начиная с окончательного распределения (последняя строка на рис. 2.!6).
Переписывая таблицы для этих двух примеров и поворачивая каждый ряд на одну позицию по отношению к предыдущему ряду, мы получаем табл. 2.13 и 2.14 для шести проходов и для трех и шести лент соответственно. Таблица 2.!8. Идеальное распределение серий на двух лентах а(п а)п ,'~ ап! х.а, Сортараваа аоахе<товательных фейхоа 131 и а(")=1, а<за)=0. Полагая а(<=(„мы получаем 11+)=11+11 ), для 1)1, ~1=1, 1а — — О. (2.41) Это — рекурсивные правила (или рекуррентные соотношения), определяющие так называемые числа Фибоначчщ О, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....
(2.42) Подстановка 11 вместо а)! дает 1!+! = 11+ Л1-<+ Т(-3+11-3+ )( 3 для 1~ ~4, 1,=1, (2.43) 11=0 для ! (4. Эти числа являются так называемыми числами Фибоначчи порядка 4. В общем виде числа Фибоначчи порядка р определяются следующим образом; )(е), ='1<а)+ )<<Р), + ... + 1<е) для 1~~р, 7~ф = 1„ К<1" =-0 для 0(1( р. (2.44) Заметим, что обычные числа Фибоначчи имеют порядок 1. Теперь мы убедились, что исходные числа серий для идеальной многофазной сортировки с и лентами должны быть суммами п — 1, н — 2, ..., ! (см.
табл. 2.15) последовательных чисел Фибоначчи порядка и — 2. Из этого следует, что алгоритм многофазиого слияния применим только к таким входным данным, в которых число серий есть сумма Каждое число Фибоначчи представляет собой сумму двух предшествующих чисел. Итак, для того, чтобы многофазный метод с тремя лентами работал правильно, числа начальных серий иа днух входных лентах должны быть двумя соседними в ряду Фибоначчи. А что можно сказать относительно второго примера (табл.
2.14) с шестью лентамит Правила построения чисел легко записать в таком виде: , (1+!) п(1) о<!-т!) — о<1)+ о<о — оа)+ ф- ) 3 и<! ю)=а<" +о")=а< )+а(1 ')+ а<1-3), 3 ! ! ! о(!+!) = о(п+ ()(!) ан) + а<1-!) 1 а(1-3)+ п(1 — 3) 3 <(~а<! )<1) + дщ — о(1) ( о(1 — !) 1 о(1-3) + о(1-3) ( з(1-4) ! 2 ! 1 ! ! ! 2. Сортировка Таблица 2.!б. Количество серий, прн которых воаножно идеальное распределение | п 3 4 5 6 7 8 и — 1 таких сумм Фибоначчи. Итак, возникает важный вопрос: что делать, если число начальных серий не является такой идеальной суммойр Ответ прост (и типичен для подобных ситуаций): мы предполагаем существование гипотетических пустых серий, таких, что сумма реальных и гипотетических серий дает идеальну!о сумму.
Пустые серии называются 4иктиеными сериями. Но зтот ответ на самом деле неудовлетворителен, так как сразу вызывает следующий, более трудный вопрос: как распознаются фиктивные серии при слиянии? Перед тем как ответить на него, мы вернемся к упомянутой выше проблеме распределения действительных н фиктивных серий на и†1 лентах. Однако, для того чтобы найти подходящее правило распределения, мы должны знать, как сливаются настоя!цие и фиктивные серии. Ясно, что выбор фиктивной серии с 1-й ленты означает, что тся лента не участвует в слиянии; в результате слияние происходит с менее чем и — 1 лент. Слияние фиктивных серий со всех и†1 входных лепт не предполагает никакой действительной операции слияния, а означает просто запись фиктивной серии на выходную ленту.
Из этого можно 1 2 3 4 5 б 7 8 9 10 1! 12 13 14 15 16 17 18 19 20 2 3 5 8 13 21 34 55 89 144 233 37! 610 987 1597 2584 4181 6765 10946 177И 3 5 9 17 31 57 105 193 355 653 120! 2209 4063 7473 13745 25281 46499 85525 157305 289329 4 7 13 25 49 94 181 349 673 1297 2500 4819 Я289 17905 34513 66526 128233 247177 476449 918385 5 9 17 33 65 129 253 497 977 1921 3777 7425 14597 28697 56417 110913 218049 428673 842749 1656801 б !1 2! 41 В! 16! 321 636 1261 2501 4961 9841 19521 38721 76806 152351 302201 599441 1189041 2358561 7 13 25 4Я 97 193 385 769 1531 3049 6073 12097 24097 48001 95617 190465 379399 755749 1505425 2998753 2.3. Сортировка иоследовательных файлов !33 сделать вывод, что фиктивные серии нужно распределять на и — 1 лент как можно более равномерно, так как мы заин- тересованы в активном слиянии с наибольшего возможного числа входных лент. Забудем на некоторое время о фиктивных сериях и рас- смотрим задачу распределения неизвестного числа серий па и — 1 лент.
Ясно, что в процесге распределения можно полу- чать числа Фибоначчи порядка и — 2, определяющие жела- тельные количества серий на каждой ленте. Предположив, например, что и = 6, и ссылаясь на табл. 2.14, мы начинаем с распределения серий, указанных в строке с номером 1= 1(1, 1, 1, 1, 1); если имеются еше серии, мы переходим ко второй строке (2, 2, 2, 2, 1); если входные данные еше не исчерпаны, распределение производится в соответствии со следуюшей строкой (4, 4, 4, 3. 2) и т. д. Номер строки мы будем называть уровнем. Очевидно, что чем больше число серий, тем выше будет уровень чисел Фибоначчи, который в данном случае равен количеству проходов, или переключе- нии лент, необходимых для последуюшей сортировки.
Алгоритм распределения теперь, в первом приближении, можно сформулировать следующим образом: 1. Пусть перед нами стоит цель — числа Фибоначчи порядка и — 2, уровня 1. 2. Распределяем серии согласно поставленной цели. 3. Если цель достигнута, вычисляем следующий уровень чисел Фибоначчи; разность между числами зтого уровня и числами предыдущего уровня представляет собой новую цель распределения. Возвращаемся к шагу 2.
Если цели нельзя достичь, потому что входные данные исчерпаны, распределение заканчивается, Правила вычисления следуюшего уровня чисел Фибоначчи содержатсч в их определении (2.44), Итак, мы можем со- средоточить внимание на шаге 2, где прн заданной цели последовательные серии должны распределяться поочередно на и — 1 лент. Именно здесь в наших рассуждениях должны вновь появиться фиктивные серии. Предположим, что, повышая уровень, мы записываем следующую цель с помощью разностей с!с для ! = 1, ...
..., и — 1, где с(с обозначает число серий, которые на данном шаге нужно отправить на ленту й Теперь можно считать, что мы сразу помещаем с(, фиктивных серий на ленту 1 и рас- сматриваем последующее рзспределенне как замену фиктив- ных серий действительными тзк, что прн каждой замене сй уменьшается на 1. Таким образом, с(, будет указывать число фиктивных серий на ленте й когда входные данные будут исчерпаны. 2. Сортировка 134 8 7 6 6 4 3 2 1 Рис 2,!6. <Горизонтальное распределениеа серий.
Теперь мы можем описать алгоритм в виде процедуры, называемой зе1ес((аре, которая вызывается каждый раз, когда переписана какая-либо серия н нужно выбрать ленту, с которой берется очередная серия. Мы предполагаем, что существует переменная 1, обозначающая индекс текущей выходной ленты. Переменные а; и с(; обозначают числа идеального и фиктивного распределений для ленты й ,1: гарино; а,с): атгау (сарепо1 62 1пс)ех; 1внг1: 1пгеяет (2.45) Эти переменные иницинруются следующими значениями: а,=!, с(=! для 1=! ...и — 1, а = О, с1„=0 (фнктивные), 1~1, 1вое1 1.
Отметим что ве1гс1(аре должна вычислять следующую строку табл. 2.14, т. е. значения аза1, ..., а'„'! „каждый раз при уве- Неизвестно, какой алгоритм дает оптимальное распределение, но следующий, предлагаемый нами метод оказался очень хорошим.
Он называется горизонгальныл распределением (см. [2.71, т. 3, стр. 322); этот термин становится понятным, если представить себе серии сложенными в виде пирамиды, как показано на рис. 2.15 для и = б уровня 5 (см. табл. 2.!4). Для того чтобы получить равномерное распределение оставшихся фиктивных серий как можно более быстрым способом, при замене их на действительные уменьшается высота пирамиды: фиктивные серии берутся с горизонтальных уровней слева направо. При таком способе серии распределяются на ленты в последовательности, указанной числами на рис. 2.16. л.з.
Сортировка аоеледовательнь~к файлов личении уровня, В это же время вычисляется также аочеред- наЯ цель», т, е, Разности т(т =а~и а" ,". ПРиведенный алгоритм основан на том, что результирующее значение А умень. шается при увеличении номера строки (ведущие вниз ступени на рис. 2.!6). (Отметим, что исключением является переход с уровня 0 на уровень 1; следовательно, этот алгоритм долнссн использоваться, начиная с уровня 1.) Яе!есГ!аре заканчивает работу, уменьшая д, на 1; это соответствует замена фиктивной серии на ленте ! действительной сериен: ргосейпте ве!есмаре; тат 1: горело; а: !пгеивг,' Ьея!п !1 тт(Я < еГЦ+Ц !Ьеп 7':= 7'+! е)ае Ьей!п !1 И(Я = 0 гйеп Ьея!п!етв1:= 1ете1+ 1,' х:= а(!]; Гог т: =- 1 го и — 1 йо Ьей!п Щ:= а+а!(+11 — аД; а1!1:= к+а!!+11 (2.46) епй епй ; 7':= 1 епй; а!(Я:= 4Л -1 епй Предполагая, что у нас есть процедура для переписи се.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
