Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 95
Текст из файла (страница 95)
Например. мы могли бы достичь состояния, в котором Р буферов заполнены на У Р и Р— 1 буферов полны, если бы в файле 1 находились ключи 1, 1+ Р, 1+ 2Р, ... при 1 < 1 < Р. Этот пример показывает, что, даже если разрешить одновременное чтение, необходимо иметь 2Р буферов ввода для подпержания иепрерывного вывода, если только мы ие перераспределяем память для частей буферов и ие исполъзуеч каким-либо образом "чтение вразброс" ! [Вообще говоря, если в блоках содержится меньше Р— 1 записей, требуется меиьше 2Р буферов, ио этот случай маловероятен.) 4. Раньше устаиавливать 8 (на шахах Г1 и Р4, а ве РЗ).
6. Если бы, например, все ключи во всех файлах были равны, то мы ие могли бы просто делать произвольный выбор во время прогнозярования; прогноз должен быть совместим с решениями, принимаемыми процессом слияния. Возможный безопасный путь состоят в том, чтобы найти на шахах г 1 и г 4 наименьшее возможное т, т. е. считать, что все записи из файла С(») меньше, чем все записи, имеющие тот же ключ в файле С[Я, если» < 11 (В сущности, номер файла присоединяется к ключу.) 6.
На шаге С1 установить также Т5РЕ(Т+ 1) +- Т+ 1. На шаге С8 слияние должно идти на Т5РЕ(р+ 2) вместо Т5РЕ(р+ 11. На шаге С9 установить (Т5РЕ(1),...,Т5РЕ(Т+1))»- (Т4РЕ(Т+11,...,ТЛРЕШ). Т. Метод, показанный на диаграмме А, есть (А»Р») АеВе(А»Р»)'АоВе(А»Р»)'Ае, Р»(А»В») АеРе(А»Р»)'АеРеоАеРеАе, Р»АеРе(А»Р») АоВеоА»Р»Ае, Р»А»Р»аА»Р»Ае, где а = (АеРе)~А»Р»АеРо(А»Р»)~(АаРо)~А»Р»(АоРо)~А»Р»АеВе. На первой фазе слияния записывается РеА»РзА»Р»А»Р»АеРеА»Р»А»В»А»Р»АеР»А»Х»АеРо(А»Р») валенту 5; на следующей записывается А»В» А»Р» А»Р» А»В»АеРоА» Р» А»Р» Аг на ленту 1, на следу- ющей -- Р»»А»Р»АоРеА»е на ленту 4. Последние фазы таковы; А»Р»А» — ВшА»В»Аи Р»зА»В»А» Р».4з А» Рг»А»» РшАз ВмА» Рез Рш Р»з Рш ' Аю 8.
Нег, так как экономится самое большее о стартстопных операций, н, кроме того, время начального распределения, в основном, зависит от скорости обработки щюдной ленты (а ие выводных лент). Другие преимущества схем распределения, приведенных на диаграмме А, компенсируют этот незначительный недостаток. 9.
Х =5, В=8300, В' =;34, Я= Г(3+1ХР)АУ(бр'))+1= 14, =1ЛЕ4, о =0.295, 6 - -1.136, а' = 11' = О, Значение формулы (9) = 85Ь с, к которому мы добавляем время начальной перемотки, получая в итоге 958 с Экономна примерно одной минуты во время слияния не компенсирует потерю времени нз-за начальной перемотки и смены ленты (если мы не работаем в мультнпрограммном режиме). 10. Во время стандартного многофэзного слияния перематывается около 54»У» файла (стол- бец»Проходы/фазы" в табл.
5.4.2-1), а саман длинная перемотка в стандартном каскадном слиянии охватывает примерна а»а„»/о - (4Х(2У вЂ” 1)) с»м~(яХ(4Т вЂ” 2)) < —,", файла (из упр. 5.4.3-5 н соотношения 5.4.3-(13)). 11. Только лля начальной и конечной перемоток имеет смысл использовать быструю пе- ремотку, так как бобина, содержащая весь файл примера, заполнена лишь немногим более чем на 10/23. Применяя в примере 8 значения к = (.946!по — 1,204) и л' = 1/8, получаем следующие итоговые оценки для примеров 1-9: 111Ь, 1296, 1241, 1008, 1014, 967, 891, 969, 856.
12. (а) Очевидное решение с 4Р + 4 буферами состоит в том, чтобы просто одновременно выполнять чтение и запись на спаренные ленты. Заметим, однако, что достаточно трех буферов вывода (в любой момент мы выполняем вторую половину операции записи из одного, первую половину операции записи нз второго и заполняем третий), Это наводит на мысль о соответствующем улучшении ситуации с буферамн ввода. Оказывается, что необходимо и достаточно 3Р буферов ввода и 3 буфера вывода, если испольэовать несколько ослабленный метод "прогнозирования". Лучший н более простой подход, предложенный Дж. Сю (3.
Еве), позволяет добавить к каждому блоку "опережающий ключ", который определяет последней ключ следующего блока. Метод Сю требует 2Р + 1 буферов ввода и 4 буфера вьпюда и является видоизмененным алгоритмом Р. (См. также раздел 3.4.9.) (Ь) В этом случае большое значение а означает, что число проходов по всем данным, которое мы должны выполнить, лежит между пятью и шестью, что сводит на нет преимущество слияния с двойной скоростью. Эта идея значительно лучше работает на восьми или девяти лентах.
13. Нет. Рассмотрите, например, положение непосредственно перед А1оА~»А1оАи. Однако две поляые бобины могртл быть обработаны. ') 0 -рог 0 14 бес О 1 — Рьг Ро 1 0 0 0 0 0 г — 1 1 — р>1г -рог 0 — 1 /~, -рэлг 1- р1г -рог О !ас О 1 1 1 0 О 0 13. Матрица А имеет внд Вюг В11г В~э 1 — г Вю+Вм+'' +В~» 1 А= В»ог Вшг 0 ... 0 0...0 (1Ц В г 1 — г 1 О 0 В»о+ В.1+ "+ В»» = 1 О 0 0 Следовательно, 1- В1ог -В11г ... -Вц„цг -В~»г бес(г — А) = дог -В»ог — В,г ... 1 — В„,„цг -В..* 0 0 -1 1 и можно прибавить все столбцы к первому, а затем вынести (1 — г). Значит, ро(г) имеет вид Ла(г)/(1 - г) н паз~ = Лп(Ц, поскольку Лп(Ц»4 0 н с)ег(Х вЂ” А) р 0 для [г[ с 1.
РАЗДЕЛ 5.4.7 1, Выполняйте сортировку от младших цифр к старшим поочередно в сисгемах счисления с основанниячи Р и Т вЂ” Р, (Если сгруппированы пары цифр, то получим, в сущности, чистое основайне Р. (Т вЂ” Р). Так„если Р = 2 и Т = 7, то система счисленяя — двоичнопятернчная, которая очевидным образом связана с десятичными обозначениями.) 2. Если К вЂ” ключ, находящийся в диапазоне от 0 до Є— 1, то пусть фнбоначчиевым представлением Р» — 1 — К будет.а»-эР»-~ + .. + а~ Рэ, где аз равны 0 нлн 1 и нет двух последовательных единиц.
после фазы у на ленте (у+ Ц шоб3 находятся ключи с ау = О, а на ленте (у — Ц глоб 3 — ключи с а; = 1 в порядке убывания значений а; г... аь [Представьте сортировальную машину для перфокарт с карманами "0" и "1" и рассмотрите процедуру сортирсмки Р„карт; иа которых перфорированы ключи а э... аг в и-2 колонках. Обгочная процедура нх сортировкп в порядке убивания, которая начинается с младшей цпфрм, может быть упрощена, поскольку все, что находится в кармане "1" в конце одного пршсода, попадает на следующем проходе в карман»0".) 4. Если бы на уровне 2 находился внешний узел, то иам не удалось бы построить такое хорошее дерево.
В противном случае на уровне 3 имеется самое большее трн внешних узла, на уровне 4 — шесть, так как предполшвется, что каждый внешний узел оказывается на одной и той же ленте. т а 9 а 6. 09, 08...,, 00, 19, ..., 10, 29, , 20, 39„ ..., 30, 40, 41, ..., 49, 59, :, 50, 60, 61, ..., 99. у. Да. Сначала распределяем записи во все меньшие в меиьшие подфайлы, пока не получим файлы на одной бобике, которые могут быть рассортированы отдельно. Этот процесс является двойствениым по отношеиию к сортировке файлов на одной бобине с последующим слиянием их во все болыпие и большие файлы на нескольких бобинах. РАЗДЕЛ $.4.6 1. Да.
Пусть направления файла и дерева выбора чередуются от возрастающего к убывающему, тогда в результате получим шейкер-сортировку Р-го порядка (см. упр, 9). 2. Пусть Ял = Р г — Хл; решим рекуррентные соотношения для лл, заметив, по (%+ ЦФЛл~.~ = Ф(Ж вЂ” 1)Ял + й' + )т'; следовательно, Я = 1()У+ 1) + 1 )/Ю(Х вЂ” 1) при йг > М. М+2 Теперь исключим Уи и получим Хл 20 У 1 1 — = — (ЖЧ+1-НМ~.2)+2~ — —— 01+1 3 + ~Л+1 М+г) 2 1'М+2'1 1' 1 1 1 ЗМ+4 3 1 3 / ~(Ф+1)Ж(У-1) (М+2)(М+1)М/ М+2 ' 3.
Да. Найдите элемент, который является медианой, за О(Ут') шагов, используя построение, аналогичное приведенному в теореме 5.3,3Ь, и с его помощью разделите файл. Еще один интересный подход, предложенный Р. У. Флойдом (К. 1т'. Р1оуд) и Э. Дж. Смитом (А. Ю. Бшйп), состоит в том, чтобы слить две серии из Х элементов за О(Ж) единиц времени следующим образом. Раздвиньте элементы иа лепте, оставив между ними промежутки, затем последовательно занесите в каждый такой промежуток число, которое определяет конечное положение элемеита, предшествующего этому промежутку.
4. Можно объединить график для этажей (1,..., р+ 1) с графиком для этажей (9,..., и): когда по первому графику лифт впервые достигает этажа р+ 1, то подняться на этаж 9 я действовать в соответствии со вторым графиком (считая текущих пассавгиров лифта "дополнительными" людьми в алгоритме теоремы К). После выполнения этого графика вернуться па этаж р+ 1 и возобновить прежний график. б. Рассмотрим Ь м 2, гп = 4 и следующее поведение алгоритма. Э ~: — гр — — ~Р~ $667 4566 В б- '— 13 — ~гг ЭВ 5667 2345 Э 1 — * — ~гг — — ~~г1 — ~ —— 5667 1234 2345 Э ~: — — +гг — — — М, 5566 Э аж 3: — 63 — +23 2556 Этаж 2. "— 62 — +ОО ОО55 Э 1: -55 — +оо оооо ! Теперь 2 (в лифте) меньше, чем 3 (на третьем этаже). (После построения примера, подобного этому, читателю должно быть ясно, как устзно.
вить справедливость более слабого свойства, используемого в доказательстве теоремы К.) 6. Найдем минимальные 1, 7', такие, что Ь; < Ь', и Ь > Ь'. Введем нового человека, который хочет переехать с этажа 1 на этаж у. При любом Й это не увеличит шах(нэ, г)аз п 1) или шах(Ью Ьь ). Продолжим процесс, пока не получим Ь, = Ь' при всех у. Теперь заметим, что алгоритм в тексте раздела, если изменить Ь на Ьэ нв шагах К1 и КЗ, по-прежнему работает. 6. Пусть нх чжло будет Р„и пусть ߄— число перестановок, для которых нь = 1 при 1 < Ф < и, Тогда Р„ш Ц,Р„~ + ЯгР„э+ + 1'„1„Ро, Ре = 1.
Можно показать, что ф, = 3" з при и > 2 (см. ниже), поэтому, используя пронзводящяе функции, получим ) Р„э" — — (1 — Зз)/(1 — 4х+ 2э ) = 1+ э+2з +ох +20з +ббэ + 2Ре ы (2+ 42) + (2 — Л) Чтобы доказать, что Я„= 3", рассмотрим тернарную последовательность х ~хз... х~, такую, что хг = 2, хе ж 0 и 0 < хь < 2 прн 1 < Ь < гь Следующее правило определяет взаимно однозначное соответствие между такими последовательностями я требуемыми перестановками агат... о: оэ = Ь, 1 шах(у ) (у < Ь илв х, = О) или 2 = 1 ), если хэ = О; если хэ = 1; пйп(у ) (у > Ь илн хз = 2) или у = и ), еглн хь = 2. (Это соответствие было получено автором совместно с Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
