Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 67
Текст из файла (страница 67)
Сбалансированное слияние легко обобщается для 'Т лент при любом Т > 3. Выберем произвольное число Р, 1 < Р ( Т, и разделим Т лент на два "банка": Р лент в левом банке и Т вЂ” Р лент в правом банке. Распределим исходные серии как можно равномернее по Р лентам левого "баню", затем выполним Р-путевое слияние слева направо, после этого — (Т вЂ” Р)-путевое слияние справа налево и так до тех пор, пока сортировка не завершится, Обычно значение Р лучше всего выбирать равным (Т(2) (см, упр. 3 и 4).
При Т = 4, Р = 2 имеем частный случай — сбалансированное двухпутевое слияние. Вновь рассмотрим предыдущий пример, используя большее количеспю лент; положим Т = б и Р = 3. Начальное распределение теперь будет таким: Лента 1 Вз ". Внюоооо, 'Взоовкн . Аоовюо Лента 2 Вцххющ " Вяюоооо; Взоооан "Взоооооо Лента 3 Вмооап ° "Взоооооо (В конец ленты 2 неявно добавляется фиктивная серия, так что серия В,юоовл ... Взвзвхю просто копируется на ленту 3.) После перемотки всех лент к началу следу- ющий проход по данным приведет к такому результату: Первый проход слияния приведет к следующему результату: Лента 4 В» Взаааааа Лента 5 Взеюаа» Взаааааа Лента 6 (Пустая) (5) В» . В»аааааа' Взаюаа» В»аоххю В»оюаа» ° ° Взооеюа:. В»ааааа» ° Взаааааа Взааааа» .
Взаааааа (Пустая) Лента 1 Лента 2 Лента 3 Лента 4 Теперь, выполнив трехпутевое слияние на ленту 4 и перемотку лент 3 и 4 с последующим трехпутевым слиянием на ленту 3, можно было бы завершить сортировку, прочитав всего 3000000+ 5000000 = 8000000 записей. Наконец, если бы мы имели шесть лент, то могли бы. конечно, записать исходные серии на ленты 1 — 5 и закончить сортировку за один проход, выполнив пятипутевое слияние на ленту 6. Анализ этих случаев показывает, что простое сбалансированное слияние не является наилучшим и было бы интересно поискать более удачные способы слияния. В последукнцих разделах этой главы внешняя сортировка исследуется более глубоко. В разделе 5.4.1 рассматривается фаза внутренней сортировки, порождающая начальные серии. Особый интерес представляет технщюгия "выбор с замещением", (Предполагается, что на ленте 3 помещена фиктивная серия.) На втором проходе слияния работа завершается и серии В»... Взохюаа помещаются на ленту 1.
Этот частный случай для Т = 6 эквивалентен случаю для Т = 5, поскольку лента 6 используется лишь при Я > 7. При трехпутевом слиянии затрачивается фактически несколько больше времени центрального процессора, чем при двухпутевом, но оно обычно пренебрежимо мало по сравнению со временем, необходимым для чтения, записи и перемотки ленты. Мы довольно хорошо оценим время выполнения сортировки, если примем во внимание только суммарную величину перемещений лент. В предыдущем примере И4) и (5)) требуются только два прохода по данным по сравнению с тремя проходами при Т = 4, Таким образом, слияние при Т = 6 займет около двух третей времени по отношению к предыдущему случаю.
Сбалансированное слияние кажется очень простым и естественным. Но если приглядеться внимательнее, то сразу видно, что это не наилучший способ для рассмотренных выше частных случаев. Вместо того чтобы переходить от (1) к (2) и перематывать все ленты„нам следовало остановить первое слияние, когда на лентах 3 и 4 содержались соответственно В»... Вяюаааа и Взааааа»" Взаааааа, а лента 1 была готова к считыванию Взо»ою» Вза»юааа.
Затем ленты 2-4 могли быть перемотаны к началу и сортировка завершилась бы трехпутевым слиянием на ленту 2. Общее число записей, прочитанных с ленты в ходе этой процедуры, составило бы 4000000+ 5000000 = 9000000 против 5000000 + 5000000+ 5000000 = 1а,000000 в сбалансированной схеме. Сообразительная машина могла бы постичь и это! Имея пять серий и четыре ленты, можно поступить еще лучше, распределив серии следующим образом: в которой используется порядок, присутствующий в большинстве данных, чтобы породить дЛинные серии, значительно превосходящие емкость внутренней памяти.
В разделе 5.4.1 обсуждаются также структуры данных, удобные для многопутевого слияния. Важнейшие схемы слияния рассматриваются в разделах 5.4.2-5.4.5. Пока мы не вступим в единоборство с грубой действительностью работающих накопителей на магнитных лентах и реальных сортируемых данных, лучше, изучая характеристики этих схем, ограничиться весьма приближенным представлением о сортировке на лентах. Например, можно с легкой душой полагать (как мы делаля до сих пор), что первоначальные исходные записи появляются волшебным образом в течение первой распределительной фазы. На самом деле они, вероятно, будут занимать одну из наших лент и, быть может, даже целиком заполнят несколько бобин, так как лента не бесконечна! Лучше всего пренебречь подобными техническими деталями до тех пор, пока не будет достигнуто "академическое"' понимание классических схем слияния.
Затеи в разделе 5.4.6 мы "вернемся на землю", рассмотрев практические ограничения, которые существенно влияют на выбор схемы слияния. В разделе 5.4.6 сравниваются основные схемы слияния из разделов 5.4.2-5.4.5 с учетом множества разнообразных предположений, которые встречаются на практике. Иные подходы к проблеме внешней сортировки, не основанные на слиянии, обсуждаются в разделах 5.4.7 и 5.4.8. Анализ разнообразных аспектов внешней сортировки заканчивается в разделе 5.4.9„в котором рассматривается важная проблема сортировки с использованием таких устройств внешней памяти, как магнитные диски и барабаны.
Когда шла работа над первым изданием этой книги, накопители на магнитной ленте использовались повсеместно, в то время как магнитные диски считались слишком уж дорогой экзотикой. Но с начала 80-х годов цена на устройства памяти с магнитными дисками разительно снизилась, и в конце 90-х годов они практически вьпеснили накопители на магнитных лентах в подавляющем большинстве компьютерных систем. Таким образом, вопрос, который еще совсем недавно считался важнейшим в проблеме сортировки (а именно — разработка и анализ методов сортировки применительно к особенностям функционирования накопителей на магнитных лентах), теперь представляется не таким уж важным. Однако большинство подобных схем сортировки настолько изящны, а соответствующие алгоритмы так отражшот результаты самых глубоких исследований, выполненных в ранние годы компьютеризации, что делать их достоянием только истории науки представляется слишком большим расточительством.
Поэтому мы довольно подробно проанализируем схемы слияния и это, возможно, будет их последним появлением на сцене перед тем, как занавес за ними опустится окончательно. Мз всего, что известна нам сегодня, вполне можно сделать следующий вывод: зги методы сохванят свою аитуальность и в дальнейшем.
— ПАВЕЛ КЕМ ИС (1997) УПРАЖНЕНИЯ 1. (15) В тексте раздела внешняя сортировка рассматривается после внутренней. Почему нельзя вообще покончить с фазой внутренней сортировки, просто выполняя слияние записей во все более и более длинные серии с самого начала? 2. (10) Каким будет содержимое лент (аналогичное (1) — (3)), если записи??~??х .
Нгоооооо сортируются с помощью трехлешочного сбалансированного метала при Р =- 2? Сравните этот случай со слиянием на четырех лентах; сколько проходов по всем данным будет сделано после первоначального распределения серий? 3. (х0) Покажите, что метод сбалансированного (Р, Т вЂ” Р)-путевого гливнии, примененный х о начальных серий, приводит к 2л проходам> если Р" (Т вЂ” Р)" ' < 5 < Р~(Т вЂ” Р)~, и к 21+1 проходам, если Р" (Т вЂ” Р) < Б < Рьы(Т вЂ” Р)~.
Дайте простые формулы длк вычисления (а) точного числа прсеюдов хах функции от 5 при Т = 2Р, (Ь) приближенного числа проходов при 5 -~ м для любых Р и Т. 4. (НМ?5] При каком значении Р, 1 < Р < Т, значение Р(Т вЂ” Р) максимально? 5,4.1. Многопутевое слияние и выбор с замещением В разделе 5.2.4 рассматривались методы внутренней сортировки, основанные на двухпутевом сливкин — процессе объединения двух упорядоченных последовательностей в одну. Нетрудно расширить этот анализ и на Р-путевое слияние, когда Р входных серий объединяются в одну выходную. Пусть имеетси Р возрастающих серий, т.
е. последовательностей записей, ключи которых расположены в порядке иеубывании. Очевидным способом их слияния будет следующий: просмотреть первые записи каждой серии и выбрать из них ту, которая имеет минимальный ключ; эта запись передается на выход и исключаетси из входных данных, затем процесс новторяется. В любой момент времени потребуетси просмотреть только Р ключей (один на каждую серию) и выбрать из них наименьший. Если наименьшими окажутся два или более ключей, выбрать можно любой из них. Пока Р не слишком велико, этот выбор удобно осуществлять, просто выполнил Р— 1 сравнений дли нахождения наименьшето из текущих ключей.
Но если Р равно, скажем, 8, то можно ускорить работу, используя дерево выбора, как описано в разделе 5.2.3; затем каждый раз потребуется примерно 18Р сравнений (после начального формировании дерева). Рассмотрим„например, четырехпутевое слияние с двухуровневым деревом выбора. Е (087 503 со 087 170 908 со 154 ) 154 426 653 сс 1612 оо (503 <и 1170 908 оо 087 154 / 154 426 653 оо 1612 оо 1(503 <и 087 154 170 426 (426 653 сс 1 612 оо ° ( Шаг У 087 154 170 426 503 612 653 908 со В этом примере в конце каждой серии помещен добавочный ключ "оо", чтобы слияние заканчивалось естественно. Так как внешнее слияние обычно имеет дело с очень длинными сериями, эта добавочная запись с ключом "оо" не увечичит существенно длину данных или объем работы при слиянии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
