AOP_Tom3 (1021738), страница 66
Текст из файла (страница 66)
Когда шла работа над первым изданием этой книги, накопители на магнитной ленте использовались повсеместно, в то время как магнитные диски считались слишком уж дорогой экзотикой. Но с начала 80-х годов цена на устройства памяти с магнитными дисками разительно снизилась, и в конце 90-х годов они практически вытеснили накопители на магнитных лентах в подавляющем большинстве компьютерных систем. Таким образом, вопрос, который еще совсем недавно считался важнейшим в проблеме сортировки (а именно — разработка и анализ методов сортировки применительно к особенностям функционирования накопителей на магнитных лентах), теперь представляется не таким уж важным.
Однако большинство подобных схем сортировки настолько изящны, а соответствующие алгоритмы так отражают результаты самых глубоких исследований. выполненных в ранние годы компьютеризации, что делать их достоянием только истории науки представляется слишком большим расточительством. Поэтому мы довольно подробно проанализируем схемы слияния н это, возможно, будет их последним появлением на сцене перед тем, как занавес за ними опустится окончательно. Мз всего, что известно нам сегодня, вполне можно сделать следующий вывод: зти методы сокпанят свою актуальность и в дальнейшем. — пАВел кеР гис О997) УПРАЖНЕНИЯ 1.
(15) В тексте раздела внешняя сортировка рассматривается после внутренней. Пачему нельзя вообще покончить с фазой внутренней сортировки, просто выполняя слияние записей во все более и более длинные серии с самого начала? 2. (10) Каким будет содержимое лент (аналогичное (1) — (3) ), если записи??1 Не .. Яееооооо сортируютси с помощью трехленточного сбалансированного метода при Р = 2? Сравните этот случай со слиянием на четырех лентах; сколько проходов по всем данным будет сделано после первоначального распределения серий? 3. (20) Покажите,что метод сбалансированного (Р, Т вЂ” Р)-путевого слияния, примененный к 5 начальных серий,приводит к 2й проходам, если Р~(Т вЂ” Р)~ ' < 5 < Р~(Т вЂ” Р)", н к 25 + 1 проходам, если Р~(Т вЂ” Р)" < 5 < Ре"ы(Т вЂ” Р)".
Дайте простые формулы для вычисления (а) точного числа проходов как функции от 5 при Т = 2Р, (Ь) приближенного числа проходов прн 5 -+ сю для любых Р и Т. 4. (НМ15) При каком значении Р, 1 < Р < Т, значение Р(Т вЂ” Р) максимально? 5.4.1. Многопутевое слияние и выбор с замещением < 087 ( 087 503 оо ( 170 908 оо 087 154 ( 154 426 653 оо ( 612 сю Шаг 1 Т?0 ( 503 087 154 170 908 оо 1г4 ) 154 426 653 оо Шаг 2 В разделе 5,2.4 рассматринались методы внутренней сортировки, основанные на двухпутевом слиянии процессе об ьединения двух упорядоченных последовательностей в одну.
Нетрудно расширить этот анализ и на Р-путевое слияние, когда Р входных серий объединяются в одну выходную. Пусть имеется Р возрастающих серий, т. с, последовательностей записей, ключи которых расположены в порядке неубывания. Очевидным способом их слияния будет следующий: просмотреть первые записи каждой серии и выбрать из них ту, которая имеет минимальный ключ; эта запись передается на выход и исключается из входных данных., затем процесс повторяется. В любой момент времени потребуется просмотреть только Р ключей (один на каждую серию) н выбрать из них наименьший. Если наименьшими окажутся два или более ключей, выбрать можно любой из них. Пока Р не слишком велико, этот выбор удобно осуществлять, просто выполняя Р— 1 сравнений для нахождения наименьшего из текуецих ключей.
Но если Р равно, скажем, 8, то можно ускорить работу, используя дерево выбора, как описано в разделе 5.2.3; затем каждый раз потребуется примерно )8Р сравнений (после начального формирования дерева). Рассмотрим, например, четырехпутевое слияние с двухуровневым деревом выбора. ~ 503 оо 087 154 170 170 908 со ~ 126 )' 426 653 оо 1612 оо Шаг 9 087 154 170 426 503 612 653 908 оо В этом примере в конце каждой серии помещен добавочный ключ "оо", чтобы слияние заканчивалось естественно. Так как внешнее слияние обычно имеет дело с очень длинными сериями, эта добавочная запись с ключом "оо" не увеличит существенно длину данных или объем работы при слиянии.
Кроме того, такая "концевая" запись часто служит удобным способом разделении записей файла. В рассматриваемом процессе каждый шаг, кроме первого, заключается в замещении наименьшего элемента следующим элементом из этой же серии и в изменении соответствующего пути в дереве выбора. Так, на шаге 2 изменяются 3 узла, которые содержали 087 на шаге 1; на шаге 3 изменяются 3 узла, содержавшие 154 на шаге 2, и т.
д. Процесс замещения в дереве выбора одного ключа другим называется амбарам с замещением. Мы можем по-разному рассматривать описанный процесс четырехпутевого слияния. С одной точки зрения он эквивалентен трем двухпутевым слияниям, выполняемым совместно, как сопрограммы; каждый узел дерева выбора изображает одну из последовательностей, используемых в процессах слияния. Дерево выбора, по существу, используется как приоритетная очередь с дисциплиной "наименьший из включенных первым исключается'! Так же, как в разделе 5.2.3, можно было бы для реализации приоритетной очереди использовать не дерево выбора, а пирамиду. (Пирамиду, конечно, лшедовало бы организовать таким образом, чтобы на ее вершине появился наименьший элемент, а не наибольший, обратив для этого порядок соотношения 5.2.3 — (3).) Так как пирамида не имеет фиксированного размера, можно избежать использования ключа "со"; слияние заканчивается, когда пирамида становится пустой.
С другой стороны, в приложениях, в которых используется внешняя сортировка, обычно имеют дело со сравнительно длинными записями и ключами, так что в пирамиду будут записаны вместо самих ключей указатели на них. Мы увидим ниже, что деревья выбора можно настолько удобно изображать с помощью указателей, что они ~деревья), вероятно, в данной ситуации лучше пирамид. Дерево "проигравших'! На рис. 62 изображено полное бинарное дерево с 12 внешними (квадратныл1и) узлами и 11 внутренними 1круглыми); во внешних узлах записаны ключи, во внутренних — — "победители", если дерево рассматривать как турнир для выбора наименьшего ключа.
Меньшие числа над каждым узлом показывают традиционный способ распределения последовательных позиций памяти для полного бинарного дерева. Чтобы определить новое состояние дерева выбора, изображенного на рис. 62, когда наименьший ключ 061 будет заменем другим ключом, нужно рассмотреть только ключи 512, 087 и 154.
Если интерпретировать дерево как турнир, последние три ключа будут представлять собой проигравших в матчах с игроком 061. Это Рис. 62. Турнир, в котором выбирается наименьший ключ; используется полное бинарное дерево, узлы которого пронумерованы от 1 до 23. Рис. 63. Тот же турнир, что и на рис. 62, но показаиы проигравшие, а не победители: чемпион находится иа самом верху. наводит на мысль, что мы в действительиости должны записать во внутренние узлы проигравшего в каждом матче, а ие победителя. Тогда информация, необходимая для изменения дерева, будет легкодоступной. На рис. 63 изображено то же дерево, что и на рис.
62, ио вместо победителей в нем представлены проигравшие. Дополнительный узел с номером "О" добавлен. на вершине дерева для указания чемпиона турнира. Заметим, что каждый ключ, кроме ключа чемпиона, является проигравшим ровно один раз (см. раздел 5.3.3). На практике внешним узлам в нижней части рис. 63 будут соответствовать весьма длинные записи, расположенные в памяти компьютера, .а внутренним узлам — указатели на эти записи. Заметим, что Р-путевое слияние требует ровно Р внешних и Р внутренних узлов — по одному в соседних группах.
Это наводит на мысль о возможности использовать известные эффективные методы распределения памяти. Нетрудно увидеть, каким образом можно применять дерево проигравших для выбора с замещением. Более детально мы обсудим этот алгоритм в настоящем разделе чуть позже. Получение начальных серий посредством выбора с замещением. Технология выбора с замещением может использоваться на первой фазе внешней сортировки, если фактически выполнить Р-путевое слияние входных данных с самими собой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
