Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 75
Текст из файла (страница 75)
зз' к 49' (К) (23о) 41 36 ЗЗ 32 30 29 28 Время перемотки 17 49 — 17 = 32 шах(8, 24) ших(13, 15) (17,20) шах(11,14) шах(22,24) шах(15, 15) |пах(20, 23) 14 1.3247180 1.4655712 1.5341577 1.5701473 1.5900054 1.6013473 1,6179086 Эти данные будут казаться парадоксальными, пока мы не поймем, что высокий порядок слияния не облзеглельно означает зф4ектиеную сорпгироеку.
В качестве крайнего рассмотрим случай, когда 1 серия помещается на ленту Т1 и и серий— на Т2, ТЗ, Т4, Т5; если поочередно выполнять слияния на Тб и Т1, пока Т2, ТЗ, Т4, Т5 не станут пустыми, то время обработки будет соответствовать 12пз+ Зи) длинам начальных серий, т. е., по существу, будет пропорционалыю тз, а ие Я)оба, хотя все время производится пятипутевое слияние. Распцеплеиие лент. Эффективное совмещение времени перемотки является проблемой, возникающей во многих приложениях, а не только при сортировке. Существует общий подход, который можно использовать в быьшилстве случаев. Рассмотрим итеративный процесс, в котором ленты используются следующим обрезом, Т1 Т2 Вывод 1 Перемотка Ввод 1 Перемотка Вывод 2 Перемотка Фаза 3 Вывод 3 Ввод 2 Перемотка Перемотка Фаза 4 Ввод 3 Вывод 4 Перемотка Перемотка и т.
д. Здесь "Вывод й" означает запись в й-й выводной файл, а "Ввод й" — его чтение. Можно устранить время перемотки, если использовать три ленты, как было предложено в работе Ь. %е1епег, С4СМ 5 (1952), 102: Т1 Т2 ТЗ Фаза 1 Вывод 1.1 Вывод 1.2 Перемотка Вывод 1.3 Фаза 2 Ввод 1.1 Ввод 1.2 Перемотка Вывод 2.1 Перемотка Ввод 1.3 Вывод 2.2 Вывод 2.3 Фаза 3 Вывод 3.1 Вывод 3.2 Перемотка Перемотка Ввод 2.2 Ввод 2.3 Ввод 2,1 Перемотка Вывод 3.3 Фаза 4 Ввод 3.1 Вывод 4.1 Перемотка Ввод 3.2 Перемотка Вывод 4.2 Перемотка Ввод 3,3 Вывод 4.3 и т.
д. Здесь "Вывод к.1" означает запись у-й трети й-го выводного файла, а "Ввод й,~н — ее чтение. В конце концов, будет исключено все время перемотки, если перемотка выполняется, по крайней мере, вдвое быстрее чтении/записи, Подобная процедура, в которой вывод в каждой фазе разделяется между лентами, называется расщеплением лент, В работе В..
Ь. МсЛ))шсег, САСМ T (1964), !58-159, показано, что расщепление лент приводит к аффективному методу совмещения времени перемотки в многофазном слиянии. Этот метод можно использовать с четырьмя или более лентами, и он осуществляет (Т вЂ” 2)-путевое слияние. Предположим снова, что имеется шесть лент, и попытаемся построить схему слияния., которая работает следующим образом, расщепляя вывод на каждом уровне (буквы вГ', "0" и "К" обозначают соответственно ввод, вывод и перемотку). Уровень 7 Число выводимых серна из Фз ив ев из из из ез (21) Чтобы по окончании работы получить одну серию на ленте Т4, а остальные ленты сделать пустыми, необходимо иметь ее=1, ив + юз = О„ из+из = ио+ив1 из + ез = и~ + из + ив+ ио, из + ев = из + вз + из + из + ие + ив, ив + ез = из + ез + из + из + и1 + и~ + ие + ио из + ив = ив + ив + из + оз + из + из + и1 + и1 + ио + ио и т.
д, В общем случае требуется, чтобы ив +ив+З ив-З + ив-~ + ив-З+ ив-З + ив-в+ив в +ив-З + Ев-4 (22) при всех и > О, если считать и! = из = О при всех у < О. Эти уравнения не имеют единственного решения, В самом деле, если попо- жить все и равными нулю, то получится обычное многофазное слияние, причем одна лента будет лишней! Но если выбрать и„~и и„+ы то время перемотки будет удовлетворительно совмещено.
Т! Т2 ТЗ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 К 1 1 О к о 1 0 К к о о к о К 1 1 1 1 1 1 1 1 1 1 1 1 1 Т4 Тз Тб к о о к к о О К 1 О ! ! К 1 1 1 1 1 1 1 1 1 1 ! 1 1 1 1 1 В. 1 1 О 1 К 0 1 О К В, О 1 о к В указанной работе Мак-Аллестер предложил взять Но = Оп-1 + Вп-2 + Оп-3 + Оп-4 ! оп+1 — Нп-! + Пп-2 + Нп-3 + Нп-4! твк что последовательность (ХО,Х!.*2!ХЗ,*4,яз,".) = (Се,ивин»пз,вз,пз! ") УДОВЛЕтВОРЯЕт ОДНОРОДНОМУРЕКУРРЕНтНОМУ СООтНОШЕНИЮХп = Яп 3+Хи 6+Хи 2+ яп о. Оказалось, однако, что лучше положить Оп+! Пп-1 + 11п-1 + Нп-'1 + Сп-2~ Н„= Нп-З+ Оп-3+ Пп-4+ 113-4. (23) Эта последовательность не только немнсно лучше по времени слияния; ее большое преимущество состоит в том, что соответствующее время слияния можно проанализировать математически. Вариант Мак-Аллестера для анализа крайне труден, потому что в одной фазе могут встречаться серии разной длины; мы увидим, что такого не может случиться, если справедливо (23).
Можно вывести число серий на каждой ленте на каждом уровне, дни!вась назад по схеме (21), и получить следующую схему сортировки. Время записи Уровень тг 121 112 111 13 14 1з т1 12з 113 113 116 16 16 12 11 К 191 19'31 К 19'31 191316 191З16 (з!') К 311 З1'и' В. 311526 (52') К 526 526826 (К) 0 х 52 = 0 1 0 х 52 = О шах(36,31, 23) Ох 82 =0 1 х 82 = Вг Несовмещенная перемотка встречается только при перемотке вводной ленты Тб (82 единицы) в течение первой половины фазы второго уровня (27 единиц) и в течение окончательных фаз "фиктивного слияния" на уровнях 1 и 0 (Зб единиц).
Таким образом, время работы можно оценить величиной 2731 + 145г; для алгоритма Р соответствующий параметр 2881+ 208г почти всегда хуже. Нетрудно видеть (см. упр. 23), что длины серий, выводимых во время каждой фазы, суть (24) 4, 4, 7, 13, 19, 31, 52, 82, 133,..., К 1З' 131191 К 13'19! 191 191 ВР ВР (196) ТЗ т4 112 1!о 113 16 11 14 К вЂ” 4 4 К 4471 тз т'и 4'т К 47' т'1з' 4'т' 7'13' 7' 7'13' 7' 1з' т' 1з' т' 1З' 13' К вЂ” вг' В.
46 43 К 3 43 ,14 43 43 4! 4' тв 1!! 11144 К 13 14 1444 1344 44 4з 41 ,11 вг 4 х 4 = 16 6 х 4 = 24 3 х 4 = 12 4 х 4 = 16 1х7=7 3 х 7 = 21 1 х 13 = 13 1 х 1З = 1З 1 х 19 = 19 1 х 19 ш 19 0 х31=0 1х З1 =З1 Время перемотки гз 82 — 23 27 рз зв 17 гз 21 34 гз зг гт 19 при атом последовательность («4, «2, «3,... ) удовлетворяет закону (25) «и = «и-2 + 2«п-3+ «и-4~ если считать «„= 1 при и < О. Можно также проанализировать оптимальное размещение фиктивных серий, рассмотрев цепочки чисел слияний, как для стандартного многофазного метода (ср.
с (8)). УРо»ень Т1 Т2 тз ! 1 1 2 1 1 3 21 21 4 2221 222 Ь 23222 23222 Е ЗЗЗЗ2З222 33332З22 1 1 2 222 2322 333323 Т(й) Т(й-1) (26) А» й» «!» Е» и+1 (А»Е»+ЦВ (Ав'Е»+1)С» (А»»Е»+1)«2» А'„'Е»+1 А'„ Здесь А = А'„А'„' и А'„' состоит из последних нп чисел слияний А„. Приведенное выше правило перехода с уровня и на уровень и + 1 справедливо для любой схемы, удовлетворяющей (22). Если определить и и е, как в (23), то цепочки А,...,.Е можно выразить в следующем, довольно простом, виде (ср. с (9)): где Ип = (Ип-зИ' -4И»-2Итп-3)+ 1 пРи и > О, И'е=О и И»=с прин<0.
(28) Исходя из зтих соотношений, легко подробно проанализировать случай для шести лент. В общем случае, если имеется Т > 5 лент„положим Р = Т вЂ” 2 и определим последовательности (и„), (ип) по правилам В»+1 = Пп-1 + и»-1+ ' ' '+ Пп-т + Еп-т~ (29) ип =и»-т-1+оп-т-!+ "+ип-р+Сп-р Прнн >О, где т = )Р("4), ее = 1 и и„= е„= О при и < О. Если ш„= и»+ с„, то имеем Шп =Шп 2+ .+Ш„,+2Ш„„1+в„, 2+ .+Шп р Прн П > О; (30) !СЕ = 1 и ш„= О при и < О.
Прн начальном распределении для уровня и+1 на ленту Й ПОМЕЩастСЯ Ш„+Ш !+ ° ° +Ш„РЕ4 СЕРИВ ПРИ 1 < Й< РИШ„!+ ° ° ° +Юп „вЂ” на ленту Т; лента Т вЂ” 1 используется для ввода. Затем ип серий сливаются на ленту Т, в то время как лента Т вЂ” 1 перематывается; и„серий сливаются на Т вЂ” 1, пока Т перематывается; и ! серий сливаются на Т вЂ” 1, пока Т вЂ” 2 перематывается, и т. д. А В В1»вЂ” Еп = (И' -1И' 2Ит ЗИ' 4) + 1, (Ип-1 И'и-2Итп-3) + 1, (И' -! И' -2) + 1, (И'и !)+1, (И'и 2Ит„з) +1, Таблица б ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ С РАСЩЕПЛЕНИЕМ ЛЕНТ Фазы Проходы Проходы/ фазы, % Ленты Отношение !зос"га 2.885 !и Ь'+ 0.000 2.078 !и 8 + 0.232 2.078 1п 5 — О.
170 1.958 1а 8 — 0.408 2.9)8 1а $ — 0.762 1.972 !и Š— 0.987 2. 013 1п Š— 1.300 2.069 !и Š— 3.164 5 6 7 8 9 10 20 1,4142136 1.6180340 1.6180340 1,6663019 1.6454116 1.6604077 1 8433803 1,6214947 1. 443 1п 8 + 1.000 0.929 1п Я + 1.022 0.752 !и 8 + 1.024 0.670 !и Е + 1.007 0,624 !п Е + 0.994 0.595!и 8+ 0.967 0.580 1п Я+ 0.941 0.566 1п Е+ 0.536 50 45 36 34 31 30 29 27 УПРАЖНЕНИЯ 1. [!6] На рис, 69 указан порядок, в котором алгоритм П распределяет по пяти лентам серии 34-65. В каком порядке распределяются серии 1-33? 2.
[31] Верно ли, что после двух фаз слияния в алгоритме П, т. е. когда мы во второй раз достшвем шага Пб, эсе фиктивные серии исчезают? 3. [ЕЕ] Доказките, что по окончании шага П4 всегда выполняется условие 0111 > 0 121 > . ° > 0(Т]. Объясните важность этого условия для правильной работы на шагах 02 и ПЗ. 4. [М30] Выведите производящие функции (7). 5.
[НМ86] (Э. П. Майлс (Е. Р. М!1ев, Лг.), 1960.) Докажите, что при всех р > 2 многочлен /г(х) = х~ -з~ ' — . — х — 1 имеет р различных корней, из которых ровно один превосходит 1 по абсолютной величине. [Указание. Рассмотрите многочлен х"+' — 2хг + 1.] 6. [НМ84] Цель этого упрюкнеиия — рассмотреть способ составления табл, 1, 5 и 6, Предположим, что имеется схема слияния, свойства которой следующим образом характеризуются многочленами р(х) и 9(х), (!) Число начальных серий в "точном распределении", требующем п фаз слияния, равно [х"] р(х)/9(х). (О) Число начальных серий, обрабатываемых в течение этих и фаз гликния, равно [х"]р(х)/д(х)~. (ш) У многочлена 4(х-') есть "главный корень" а, такой, что 9(а-]) = О, а'(а-') и О, р(а-') д О, и из 9(д ') = 0 следует, что 8 = анди [д[ < [а[. Докюките, что существует с > О, такое, что если 5 равно числу серий прн точном распределении, требующая и фаз слияния, а во время выполнении этих фаз обрабатывается В табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
