AOP_Tom3 (1021738), страница 80
Текст из файла (страница 80)
8.) С другой стороны, не так уж трудно построить конструкции, асимптпошически оптимальные для любого фиксированного Т. Пусть Кт(п) — минимальная длина внешнего пути, достижимая в Т-!11о-дереве с и внешними узлами. Используя теорию, развитую в разделе 2.3.4.5, несложно доказать, что Кт(п) > нд — '(((Т вЂ” 1)е — н)/(Т вЂ” 2)~, д = (!о8т 1 п1, (9) так как зто минимальная длина внешнего пути любого дерева с и внешними узлами и степенью любого узла < Т. К настоящему моменту известны относительно немногие точные значения Кт(п). Ниже приведены верхние оценки, которые, вероятно, точны. и = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Кз(п) < 0 2 5 9 12 16 21 25 30 34 39 4о 50 56 61 (10) К4(п) ( 0 2 3 6 8 11 14 17 20 24 27 31 33 37 40 Карл обнаружил, что любое дерево с внутренними узлами степени < Т является почпш Т-'шо-деревом в том смысле, что оно может быть превращено в Т-Ио путем замены некоторых внешних узлов однопутевыми слияниями.
Фактически создать подходящую расстановку меток довольно просто. Пусть Л вЂ” конкретное имя ленты. Необходимо выполнить следующие действия. Шаг 1. Присвоить имена лент ребрам схемы дерева любым способом, совместимым с условием 1а), которое приведено выше, однако так, чтобы специальное имя А использовалось только в крайнем слева ребре ветви. Шаг 2. Заменить каждый внешний узел вида на для любого В Ф А. Шаг 3. Пронумеровать внутренние узлы в прямом порядке. Результатом будет расстановка меток, удовлетворяющая условиям (а), (Ь) и 1с).
Например, если начать с дерева и трех лент, то зта процедура расставит метки следующим образом: Нетрудно проверить, что конструкция Карпа удовлетворяет дисциплине "последним образован — первым растет" в силу свойств прямого порядка (см. упр. 12). Заметим, что результатом такого построения является схема слияния, в которой все начальные серии появляются на ленте А. Это предполагает следующую схему распределения и сортировки, которую можно назвать слиянием е прямом порядке. Р1.
Распределить начальные серии на ленту А, пока ввод не будет исчерпан. Пусть 5 — число всех начальных серий. Р2. Выполнить описанное выше построение, используя (Т вЂ” 1)-арное дерево с 5 внешними узлами и минимальной длиной пути, и получить Т-111о-дерево, длина внешнего пути которого превышает нижнюю границу (9) не более чем на 5. РЗ. Слить серии в соответствии с этой схемой. $ Результат в указанной схеме получается на какой угодно ленте.
Но эгаа схема имеет один серьеэиыб иэвли. (Видит ли читатель, что именно здесь будет неправильно работать?) Дело в том, что схема требует, чтобы первоначально одни серии на ленте А были восходящими, а другие -- нисходящими в зависимости от того, где появляется соответствующий внешний узел: на нечетном или четном уровне. Не зная 5 заранее, эту проблему можно разрешить путем копирования серий, которые должны быть нисходящими, на вспомогательную ленту (или ленты) непосредственно перед тем, как они потребуются.
Тогда суммарное количество операций, измеряемое в длинах начальных серий, окажется равным 51оат ~ 5 + 0(5). Таким образом, слияние в прямом порядке определенно лучше многофазного илн каскадного при 5 -+ оо. В действительности оно аснмптотически оптимально, так как (9) показывает, что 5 1оят, 5+ 0(5) .-- это наименьшая оценка времени, на которую мы вообще можем надеяться при работе с Т лентами.
С другой стороны, для сравнительно небольших значений 5, обычно встречающихся на практике, слияние в прямом порядке весьма неэффективно; многофазный или каскадный метод проще и быстрее, если 5 относительно мало. Возможно, удастся изобрести простую схему распределения и слияния, которая сравнима с многофазной и каскадной при небольших 5 и асимптотически оптимальна при больших 5. Ниже, в упражнениях части 2, демонстрируется, как Карп аналогичным образом поставил вопрос для слияния с прямым чтением.
Теория оказывается в этом случае значительно более сложной, хотя были получены некоторые весьма интересные результаты. УПРАЖНЕНИЯ (часть 1) 1. (17) Прн слиянии с прямым чтением часто удобно отмечать конец каждой серии на ленте путем добавления искусственной "концевой" записи с ключам +со. Как следует видоизменить этот метод ирн обратном чтении? 2. [Я0) Будут ли столбцы таблицы, аналогичной табл. у, всегда неубывающими или возникают ситуации, когда приходится "вычитать' серии с некоторой ленты прн переходе от одного уровня к другомуэ ь 3. (20) Докажите, что при использовании метода многофазного слияния, описанного для распределения (Ц, после завершения сортировки на ленте Т1 всегда оказывается и серия А, если первоначально на Т1 было АРА..., а на лентах Т2 — Т5 было РАР. 4.
[М22( Как вы оцениваете идею выполнения многофазного слияния с обратным чтением после распределения всех серий в порядке воэрасгаанил, если предположитгч что все позиции Р первоначально заполнены фиктивными сериямиз 5. [28[ Какие формулы для цепочек слияния чисел вместо (8)-(1Ц из раздела 5.4.2 будут справедливы для многофазного слияния с обратным чтением? Оцените числа слияний для распределения пятого уровня на шести лентах, нарисовав диаграмму, аналогичную показанной на рис. 71, (а).
б. [07] Каково векторное представление схемы щзияния, представлением которой в виде дерева является (8)? 7. [1б) Нарисуйте представление в вцде дерева схемы слияния с обратным чтением, определенной такой последовательностью векторов 8. (22( Докажите, что (8) — оптимальный способ слияния с обратным чтением при 5 = 7 и Т = 4 и что все методы, избегающие однопутевого слияния, хуже.
9. [М22[ Докажите справедливость нижней оценки в (9). 10. [41( При помощи компьютера составьте таблипу точных значений Кг(п), ь 11. (20( Берне ли утверждение, что для любой схемы слияния с обратным чтениелз, не использующей ничего, кроме (Т вЂ” Ц-путевого слияния, необходимо, чтобы серии на каждой ленте чередовались: А РАР... (т. е. такая схема не будет работать, если две соседние серии окажутся одинаково упорядоченными)? 12. (22( Докажите, гго конструкция с прямым порядком Карпа всегда порождает поме- ченное дерево, удовлетворяющее условиям (а), (Ь) и (с).
13. [1б) Улучшите процедуру (12), сделайте ее более эффективной, удалив как можно больше однопутевых слияний, однако так, чтобы прямой порядок все еше приводил к правильной расстановке меток у внутренних узлов, 14. [40[ Придумайте алгоритм, который выполняет слияние в прямом порядке без явного построения дерева на шагах Р2 и 1'3, используя только О(1о8 2) слов памяти для улравле- НИЯ СЛИЯНИЕЛ4. 15. [Мбд) Конструкция Карпа с прямым порядком порождает деревья с однопутевым слиянием в некоторых терминальных узлах Доказките, что если Т = 3, то можно постро- ить асимптотические оптимальные З-ЬТо-деревья, в которых используется только двухпу- тевое слияние. „(зз) (зз) (22) (зц (зо) (22) (2В) (ы) Щ4) „(зз) (20, 9, 5) (+1, — 1, +Ц (+1, +1, -Ц (+1, +1, -Ц (+1, +1, — Ц (+1, -1, +Ц ( — 1,+1,+Ц (+1, — 1, +Ц (+1, — 1, +Ц (+1, +1, — Ц (+1, -1, +Ц (+1, -1, +Ц у(22) = (+1 1 +ц у(") = (-1,+1,+Ц (2о) (+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, +1, +Ц "" =(+,—,+ц '" =(-,+,+) (2) (+1 1 +ц у(') = ( — 1, +1, 4 ц д(" = ( 1, 9, 9) Другими словами, пусть Кт(п) будет минимальной длиной внешнего пути среди всех Т-!!1о-деревьев с п внешними узлами, таких, что каждый внутренний узел имеет степень Т вЂ” 1.
Докажите, что Кз(п) = и!Вп+ О(п). 16. [М46[ (Сохраняются обозначения, принятые в упр. 15.) Верно ли, что Кт(п) п !ойт, и + О(п) для всех Т > 3, если и г— я 1 (по модулю Т вЂ” 2)? ь 17. [Ву[ (Ричард Д. Пратт (ВгсЬагс! 1Э. Рта!1).) Чтобы получить возрастающий порядок в каскадном слиянии с обратным чтением, можно потребовать чешнога числа проходов слияния. Таким образом, предполагается, что метод начального распределения несколько отличен от метода, приведенного в алгоритме 5.4.3С.
а) Измените 5.4.3-(1) так, чтобы были представлены только точные распределения, для которых требуется четное число проходов слияния. Ь) Постройте схему начального распределения, осуществляющую интерполяцию между этими точными распределениями. (Иначе говоря, если число начальных серий накодится между точными распределениями, то желательно слить некоторые (ио не все) серии дважды, чтобы получить точное распределение.[ ь 1В. [МИ[ Предположим, что имеется Т ленточных устройств для некоторого Т > 3 и что на Т1 содержится !г' записей, в то время как остальные ленты пусты.
Возможно ли обратить порядок записей на ленте Т1 за число шагов, меньшее П(Х!ойгч?), бег обратного чтения? (Эта операция является, конечно, тривиальной, если допускается обратное чтение.) В упр. 5.2.5-14 приводится класс таких алгоритмов, которые, однако, шратляш порядка Ю !об !г' шагов, УПРАЖНЕНИЯ (часть 2) В следующих упражнениях теория слияния на лентах с прямым чтением распространяется на случай, когда каждая лента действует, как очередь, а не как стек. Схему слияния можно представить последовательностью векторов у!~!... уы!у! ! точно так же, как в тексте раздела,но когда мы преобразуем векторное представление в представление в виде дерева, правило "последним образован — первым растет" заменяется правилом "первым образован — первым растет'! Таким образом, недопустимая конфигурация (4) должна быть заменена конфигурацией (4') А и 4 или А и А Дерево, которое мажет быть помечено так, чтобы изображались слияния с прямым чтением на Т лентах, называется Т-6(о-деревом по аналогии с термином "Т-!!(ог в случае обратного чтения.
Если ленты можно прочесть в обратном направлении, значит, они образуют очень хорошие стеки. Но, к сожалению, они не могут образовать очень хорошие универсальные очереди. Если в произвольном порядке зшгнсывать и считывать по правилу "первым включается — первым исключается", то придется тратить много времени иа переход от одной части ленты к другой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
