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