Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 82
Текст из файла (страница 82)
Но, к сожалению, они не могут образовать очень хорошие универсальные очереди. Если в произвольном порядке записывать и считывать по правилу "первым включается — первым исключается", то придется тратить много времени на переход от одной части ленты к другой. Хуже того, мы вскоре проскочим конец ленты! Здесь возникает та же проблема, что н в случае выхода очереди за границу памяти (см. соотношения 2.2.2-(4) и (5)), но решение в виде 2.2.2-(6) и (7) не применимо к лентам, так шш их нельзя закольцевать.
Поэтому дерево будем называть сильным Т-!Чо-деревом, если оио может быть помечено так, чтобы соответствующая схема слияния использовала ленты, подчиняясь особой дисциплине: "записать, перемотать, прочитать все, перемотать; записать, перемотать, прочитать все, перемотать и т. д,". ь 19, [22] (Р. М. Кири.) Найдите бинарное дерево, которое не является З-бзо. ° 20, [22] Сформулируйте условие "сильного Т-Й(о-дерева" в терминах достаточно простого правила относительно недопустимых конфигураций меток лент, аналогичного (4'), 21.
[18] Нарисуйте представление в виде дерева схемы слияния с прямым чтением, опре. деленной посредством векторов в упр. 7. Можно ли считать его сильным 3-ЙГо-деревом? 22. [28] (Р. М. Карп.) Докажите, что представления в виде дерева многофазного и каскадного слияний с точным распределением полностью одинаковы как в случае обратного чтения, так и в случае прямого чтения, за исключением номеров, которымн помечены внутренние узлы. Найдите более широкий класс векторных представлений схем слияния, для которых верно сказанное.
23. [24] (Р. М. Карп.) Будем говорить, что серия ры)... ры) схемы слияния являетск сшадисй, если никакая выводная лента не используется в дальнейшем как вводная, т. е. если не существует Й у, к, таких, что д > 1 > й > г и рз ы -1, р„= +1. Назначение и) й) этого упражнения — доказать, что прн каскадном слиянии мннимнзнруется число стадий среди всех схем слияния с тем же числом лент и начальных серий. Удобно ввести некоторые обозначения. Будем писать о -+ ш, если е и ш такие Т- векторы, что существует схема сливина, которая иа своей первой стадии переводит ю в о (т.
е. существует схема слияния р1м)... р~~), такая, что р~ )... р) +') является стадией, ю = р~ ') + +у~О) и о = рр) + ° + рш).) Будем писать о < ш, если о и ш — т-векторы, такие, что сумма наибольших к элементов вектора о < не превышает суммы наибольших )г элементов вектора ю прн 1 < к < Т, 'Гак, например, (2,1,2,2,2,1) .< (1,2,З,О,З,Ц, поскольку 2 < 3, 2+2 ~ 3+3, ..., 2+2+2+2+1+1 < 3+3+2+1+1+0. Наконец, если е = (сп..., ет), то пусть С(о) = (аг, ет-ю ат-з, „ем 0), где вь есть сумма наибольших?с элементов векторов о. а) Докажите, что с -э С(о). Ь) Докажите, что о Ч ю влечет С(е) < С(ш).
с) Считая известным результат упр, 24, докажите, что при каскадном слиянии миинмизнруется число стадий. 24. [ИЗЗ] Используя обозначения, принятые в упр. 23, докажите, что е -+ ю влечет ю -с С(И. 23. [Мур] (Р. М. Кари.) Будем говорить, что сегмент рм) ., . ры) схемы слияния является фазой, если ни одна из лент не используется и для ввода, и для вывода, т, е. если не существует 1, у,?с, таких, что д > 1 > г, д > й > г, рп) = +1, н ры) = -1. Назначение этого упражнения — исследовать схему слияния, которая минимизирует число фаз.
Вудем писать о ю ю, если ю может быть преобразовано в о за одну фазу (ср. с подобным обозначением, введенным в упр. 23), и пусть Рь(о) = (эь+1ь+и вь+1ь+з, ..., аь+1т, О, ..., О), где 1, обозначает 3-й в порядке убывания элемент е н эь = 11+ + 1м а) Докажите, что о ю Рь(е) при 1 <?с < Т. Ь) Докажите, что нз о .< ю следует Рь(и) < Ре(ю) прн 1 < к < Т. с) Докажите, что из о ю ю слепует ш "с Рь(о) для некоторого й, 1 < й < Т. с)) Следовательно, схема слияния, сортирующая максимальное число начальных серий на Т лентах за д фаз, может быть изображена пскледовательностью целых чисел й, кз... /сю такой, что начальное распределение есть Рь, (... (Рь (Ргч (к)))...
), где и = (1,0,...,0). Эта стратегия минимума фаз имеет сильное Т-ЙГо-представление и входит в класс схем из упр. 22. Когда Т = 3, это многофазнал схема, а при Т = 4, 5, б, 7 это вариация сбалансированной схемы. 26. [М46] (Р. М. Карп,) Верно ли, что оптимальная последовательность?с~?сз... йю упомянутая в упр. 25, всегда равна 1[Т/2] [Т/2] [Т/2] Т/2] ... для всех Т > 4 и всех достаточно больших д? Т2 ТЗ Т4 Т5 Стоимость Операция Распределение Слияние Распределение Слияние Распределение Слияние Распределение Слияние Слияние Т1 А1 4 774 4 А1 .0»А1 4 — Р» 4 А1 17»А1 4 — .О» 4 А, ЮА —,Р» 4 А14 16 Фаза 1 Фаза 2 Фаза 3 Фаза 4 Фаза 5 Фаза 6 Фаза 7 Фаза В Фаза 9 А1 А1 1 14 12»А1 В» 17»А1 17» О» 27»А1 274 Здесь, как и в разделе 5.4.4, А„и 17, применяются для обозначения соответственно восходящих и нисходящих серий относительной длины г.
При использовании рассматриваемого метода сначала начальные серии по одной записываются на каждую из четырех лент и сливаютсв (чтение выполняется в обратном направлении) на пятую ленту. Затем распределение возобновляется, на этот раз циклически сдвинутое на одну позицию вправо по отношению к лентам, и в результате второго слияния образуется еще одна серия .04. Когда этим способом будут сформированы четыре серии 774, дополнительное слияние приведет к созданию Аы. Процесс можно продолжать, создав еще три А ы, слив их в П»», и так до тех пор, пока не исчерпаются исходные данные. При этом заранее знать длину исходных данных не нужно.
Если число начальных серий 5 есть 4', то нетрудно заметить, что этот метод обрабатывает каждую запись ровно »п + 1 раз (один раз во время распределения и ш раз во время слияния). Если 5 лежит между 4 ' н 4, можно с помощью фиктивных серий увеличить Я до 4; следовательно, весь процесс сортировки потребует ~)ой»51 + 1 проходов по всем данным. Это именно то, что достигается при сбалансированной сортировке на восьми лентах. В общем случае осциллирующая сортировка с Т рабочими лентами эквивалентна сбалансированному слиянию с 2(Т вЂ” 1) лентами, так как при этом выполняется ~!ойт 1 51 + 1 проходов по данным. Если Я оказываетси степенью Т вЂ” 1, то это самое лучшее, что можно получить ПРИ ЛК1паи методе с Т лентами (здесь достигается нижняя оценка из оютношения 5.4.4-(9)).
С другой стороны, если Я равно (Т вЂ” 1)™ 1 + 1, т. е. ровно на единицу больше степени Т вЂ” 1, при этом методе теряется почти целый проход. В упр. 2 показано, как, используя специальную программу завершения, устранить часть этой лишней работы для случая, когда Я вЂ” — не степень Т. Еще одно усовершенствование было предложено в 1966 году Деннисом Л. Бенчером (Вепш» Е, ВепсЬег), который назвал свою процедуру перекрестным слиянием. (См. «5.4.5. Осциллирующая сортировка Еще один подход к сортировке методом слияния был предложен Шелдоном Собелем (БЬе16оп БоЬе1) в Х4СМ 9 (1962), 372-375.
Вместо того чтобы начинать с распределения прохода, когда все начальные серии распределяются по лентам, ои предложил алгоритм, который переключается то на распределение, то на слияние, так что ббльшая часть сортировки происходит еще до того, как вся исходная информация полностью проанализирована. Предположим, например, что для слияния используются 5 лент. По методу Собеля 16 начальных серий будут сортироваться следующим образом. Н, Жеа(еЫпо, Васелогбшиэагаол (Бег11п: %. де Огиувег, 1970), 164-166; см.
также Г Я. Расела 3540000 (1970).) Основная идея состоит в том, чтобы отложить слияние до тех пор, пока не будет накоплено больше сведений о Я. Мы обсудим несколько измененную форму первоначальной схемы Бенчера. Этот усовершенствованный метод осцнллирующей сортировки действует следуюацим образом. Т1 Т2 ТЗ Т4 Тб Стоимость Фаза 1 Фаза 2 Фаза 3 й» Фаза 4 В4.41 Фаза 5 Ва Фаза 6 ВаА1 Фаза 7 В4 Фаза 8 ВаА1 Фаза 9 йа В этот момент слияние всех В4 в Аав исходные данные исчерпаны), Лишь А1 А1 А1 А1 А1 А1А1 А1А1 А1А1 А1 А1 А1 А1 А1А1 А1А1 В~а — 41 А1 В4А1 — - А1 А1А1 йа Ва — А1 ВаА1 .В4.41 — А1 йа В4 йа не выполняется (если только не после того, как закончится окажется, что Фаза 15 Слияние будет получена первая серия А,в Фаза 16 Слияние В4 Ва Ва — Аш 16.
Вторая серия Агв появится после создания еще трех В4, Фаза 22 Слияние Фаза 23 Слияние и т. д. (ср, с фазами 1-5). Преимущества схемы Бенчера можно видеть, если имеется, например, только лять начальных серий: оспиллирующая сортировка (ее модификация нз упр. 2) выполняла бы четырехпутевое слияние (на фазе 2), за которым следовало бы двухпутевое слияние с общей стоимостью 4+ 4+ 1 + 5 = 14., тогда как схема Беичера выполняла бы двухпутевое слияние (на фазе 3), за которым следовало бы четырехлутевое слияние с общей стоимостью 4+ 1+ 2 + 5 = 12. Оба метода также требуют неболыпих дополнительных затрат, а нмевио — однократной перемотки перед окончательным слиянием. Точное описание метода Бенчера содержится ниже, в алгоритме Б.
К сожалению, соответствующую процедуру, по-видимому, трудней понять, чем запрограммировать; легче объяснить данный метод компьютеру, чем программисту! Частично это происходит по той причине, что рекурсивный метод выражен в итеративном виде и затем подвергнут некоторой оптимизации; читатель, возможно, обнаружит, что приходится несколько раз проследить эа работой алгоритма, прежде чем станет понятно, что же происходит. Алгоритм В (Осиил.аиррюивал соршироака с "пврекрвсглнмм" распределением). Этот алгоритм берет первоначальные серии и распределяет их по лентам, время от времени прерывая процесс распределения, чтобы слить содержимое некоторых Операция Распределение Распределение Слияние Распределение Слияние Распределение Слияние Распределение Слияние ВВ йй ВВ й 4, Вайа Вайа В4 Аавйа 4 В» Ва Аав А14 16, лент (рис. 77).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
