Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 96
Текст из файла (страница 96)
Если будет образовано 82 или больше начальных серий, можно 'взять Р = 10, но, так как имеется место только для 18 буферов ввода и двух буферов вывода, могут возникнуть задержки в процессе слияния (см. алгоритм 5.4.6Г). В таком случае, вероятно, лучше выполнить два частичных прохода, обрабатывая небольшую. часть данных, и сократить таким образом число начальных серий до 81 нли меньше. При наших предположениях каждый проход слияния займет около 50 с, так что вся сортировка в этой идеальной ситуации будет завершена за 2 5 мин (плюс несколько секунд на инициализацию н другие вспомогательные операции). Это в шесть раз быстрее, чем при наилучшей нз сортировок с шестью лентами, рассмотренных в разделе 5.4.6.
Причинами такого ускорения являются увеличенная скорость передачи данных между внешней и оперативной памятью (она в 3.5 раза выше), более высокий порядок слияния (мы не можем осуществить 8-путевое слияние на лентах, не имея девяти или более лент) и то, что выводные данные остаются на диске (нет необходимости в заключительной перемотке и других анщюгичных операциях). Если исходные' данные и рассортированный результат должны находиться на НЫЛ И1ХТ, а барабаны использоваться только для слияния, то понадобится около 8.2 мин.
Если имеется не два барабана, а только один., то время ввода вывода увеличится вдвое, поскольку чтение и запись придется выполнять по отдельности. (На самом деле операции ввода-вывода займут в тири раза больше времени, поскольку запись будет осуществляться поверх исходных данных. В таких случаях целесообразно за каждой операцией записи выполнгть операцию контрольного чтения, чтобы не потерять необратимо какие-либо исходные данные, если только оборудование не обеспечивает автоматическую проверку записанной информации.) Однако часть этого дополнительного времени можно использовать эффективно, поскольку можно реализовать метод частичных проходов, при котороч одни записи обрабатываются чаще других.
Применение двух барабанов предполагает, что все данные обрабатываются четное или нечетное число раз, но в случае одного барабана можно использовать более общие схемы слияния. В разделе 5.4.4 рассказывалось, что схемы слияния можно изображать с помощью деревьев и что время передачи, соответствующее схеме слияния, пропорционально длине внешнего пути дерева, В качестве схем эффективного слияния на лентах можно использовать лишь определенные виды деревьев (Т-)йо илн сильные Т-Ио), потому что в процессе слияния некоторые серии оказываются "спрятанными" в середине ленты.
Но при использовании дисков пли барабанов пригодны любые деревья, если только степени их внутренних узлов не слишком велики (т. е. согласуются с действительным объемом внутренней памяти). Следовательно, время передачи можно минимизировать, если выбрать дерево с минимальной длиной внешнего пути, такое, как полное Р-арное дерево, где Р— наибольшее возможное значение.
По формуле 5.4.4-(9) длина внешнего пути такого дерева с 5 внешними узлами (листьями) равна 95 — )(Рд — 5Н(р — 1)!. Ч= ~1ОКр51. (1) Особенно просто строится алгоритм, который осуществляет слияние в соответствии со схемой полного Р-арного дерева. (См., например, рис. 91, на котором показан случай, когда Р = 3, 5 = 6.) Сначала добавляем, если необходимо, фиктивные серии, чтобы сделать 5 гв 1 (по модулю Р— 1), затем объединяем серии в соответствии с правилом "первым включается — первым исключается", сливая на каждом этапе Р самых "старых" серий в начале очереди в одну серию, помещаемую в конец. Рис. 91. Полное тернариое дерево с шестью листьями н аютветствующая схема слияния.
Полные Р-арные деревья дают оптимальную схему, если все серии имеют равную длину, но часто резулыат может быть еще лучше, если одни серии длиннее других. Можно без труда построить оптимальную схему для этой общей ситуации с помощью метода Хоффмана (упр. 2.3.4.5-10), который применительно к слиянию формулируется так: "сначала добавьте (1 — 5) щи (Р— 1) фиктивных серий длиной О, затем многократно выполните слияние Р кратчайших из имеющихся серий, пока не останется одна серия". Если все начальные серии имеют одинаковую длину, этот метод сводится к описанной выше дисциплине г'1г'О.
В нашем примйре с обработкой 100,000 записей можно выполнять 9-путевое слияние, так как в памяти поместятся 18 буферов ввода и два буфера вывода и в алгоритме 5.4.6Г будет достигнуто полное совмещение вычислений. Полное 9-арное дерево с 60 листьями соответствует схеме слияния с 1тэ прохода, если все началь- зо ные серии имеют одинаковую длину. Общее время сортировки с одним барабаном и с использованием контрольного чтения после каждой записи становится, таким образом, равным 7.4 мин. Увеличивая Р, можно немного уменьшить это время, но ситуация будет весьма запутанной, поскольку не исключается задержка чтения в связи с тем, что буфера могут оказаться слишком полными или слишком пустыми. Влияние времени поиска.
Из всего вышесказанного следует, что для барабанов относительно легко построить оптимальную схему слияния, поскольку время поиска и время ожидания можно свести на нет. Но если используются диски, поиск информации отнимает больше времени, чем ее чтение. Поэтому время поиска оказывает значительное влияние на стратегию сортировки. Уменьшив порядок слияния Р, можно использовать ббльшие по размеру буфера, так что поиск потребуется выполнять реже.
За счет этого часто компенсируется дополнительное время передачи, которое растет с уменьшением Р. Время поиска зависит от расстояния, которое проходит держатель головок, и можно попытаться организовать работу таким образом, чтобы это расстояние было минимальным.
Вероятно, разумно сначала сортировать записи внутри цилиндров. Однако довольно большое слияние требует большого количества переходов между цилиндрами (см., например, упр. 2). Кроме того, режим мультипрограммирования в современных операционных системах позволяет пользователю лишь в редких случаях по-настоящему контролировать положение держателя головок. Таким образом, предположение о том, что каждая команда для диска требует "случайного" поиска, почти всегда вполне оправдывается.
Наша цель в том и состоит, чтобы найти такое дерево (т. е. схему слияния), которое обеспечивает наилучший баланс между временем поиска и временем передачп. Для этого нужен некоторый способ, позволяющий оценить достоинства любого конкретного дерева по отношению к конкретной конфигурации оборудования. Рассмотрим, например, дерево на рис. 92. Необходимо оценить, сколько времени займет выполнение соответствующего слияния, чтобы можно было сравнить это дерево с другими.
Последующий анализ, который должен продемонстрировать некоторые общие идеи, будет выполнен в предположении, что (!) на чтение или запись и символов требуется 72.5+ 0.005п мс; (й) под рабочее пространство в оперативной памяти отводится объем, достаточный для хранения 100000 символов; (ш) для пересылки одного символа из буфера ввода в буфер вывода затрачивается в среднем 0.004 мс; (1т) совмещенке чтения, записи и вычислений отсутствует: (т) размер буфера, используемого для вывода, необязательно равен размеру буфера, используемого для чтения данных на следующем проходе. Анализ задачи сортировки при этих простых предположениях будет полезен для понимания более сложных ситуаций.
Если выполняется Р-путевое слияние, можно разделить внутреннюю рабочую память на Р+ 1 буферных областей: Р— для ввода и 1 — для вывод»; объем каждого буфера — В = 1000007(Р+ 1) символов. Предположим, что в предназначенных для слияния файлах содержится в сумме Ь символов; значит, будет выполнено приблизительно Х/В операций вывода и примерно столько же операций ввода. Следовательно, общее время слияния при таких предположениях будет равно (в миллисекундах) приблизительно 2(72.5 — + 0.005Х) + 0.0045 = (0.00145Р+ 0.01545)Х. Х ' В (2) Иными словами, для Р-путевого слияния В символов необходимо примерно (оР + Д)Х, машинных циклов, где а и Д -- некоторые константы, зависящие от времени поиска, времени ожидания, времени вычислений и объема памяти.
Эта формула приводит к интересному способу построения хороших схем слияния для дисков, Рассмотрим, например, рис. 92 и будем считать, что все начальные серии (изображенные квадратными "листьями') имеют длину Хе. Тогда каждое слияние в узлах 9 и 10 выполняется за (2а + Д)(2Хе) машинных циклов, слияние в узле 11 — за (Зо+ Д)(4Хе) машинных циклов и окончательное слияние в узле 12 — за Рис. 92. Дерево с длиной внешнего пути 16 и длиной степенного пути 52. Теорема Н. Если время, необходимое для выполнения Р-путевого слияния Е символов, составляет (оР + й)ь и если требуется слить о' серий равной длины, то наилучшая схема слияния соответствуег дереву Т, для которого огг(Т) + дЕ(Т) минимально среди всех деревьев с о' листьями.
$ (Эта теорема неявно содержалась в неопубликованной статье, которую Джордж А. Хаббард (Сеогбе 11. НиЬЬагд) представил на Национальной конференции АСМ в 1963 году.) Пусть о и й — фиксированные константы. Будем говорить, что дерево апгппмааьна, если оно имеет минимальное значение оЮ(7) + бЕ(Т) среди всех деревьев 7 с тем же числом листьев.
Нетрудно видеть, что все поддеревья оптимального дерева также оптимальны. Поэтому мы можем строить оптимальные деревья с и листьями, объединяя оптимальные деревья, у которых листьев меньше, чем и. Теорема К. Пусть яоследоваттльность чисел А (и) определена пря 1 < пт < и такими правилами: (3) (4) А (и) = ппп (А~(й) + А г(п — й)) при 2 < пч < и; г<гйо/~о Аг(п) = гпш (огпп+;бп+ А (и)) при и > 2. 2<т<о (5) Тогда Аг(п) есть минимальное значение оО(Т) +;9Е(Т) среди всех деревьев Т с и листьями.
(4о+ д)(85о) машинных циклов, Общее время слияния, следовательно, составляет (52о+ 166) бо машинных циклов, Коэффициент 16 нам хорошо известен: это просто длина внешнего пути дерева. Коэффициент 52 при о соответствует новому понятию, которое можно назвать длиной степенного пйтпи дерева Яеугее рагй (епуй). Эта длина равна взятой по всем листьям сумме степеней внутренних узлов, легкащих на пути от листа к корню. Например, на рис. 92 длина стенениого пути равна (2 + 4) + (2 + 4) + (3 + 4) + (2+ 3+ 4) + (2+ 3+ 4) + (3+ 4) + (4) + (4) = 52 Если Т вЂ” любое дерево, то пусть Ю(7) и Е(7) обозначают соответственно длину степенного пути и длину внешнего пути этого дерева. Анализ сводится к следующей теореме.
Доказатаельсгаво. Из соотношения (4) следует, что Аш(п) — минимальное значение А1(п1)+ ° +А1(пы) для всех положительных чисел пы...,и,„, таких, что а~+ + и = и. Требуемый результат шшучается теперь индукцией по и. ) Рекуррентиые соотношения (3)-(5) можно использовать также для построения самих оптимальных деревьев. Пусть йн,(п) — значение, для которого достигается минимум в определении Аш(п). Тогда можно построить оптимальное дерево с и листьями, объединяя гл = й1(п) поддеревьев в корне. Полдеревья являются оптимальными деревьями с йы(п), Й 1(п — я„,(п)), Й„, 2(п — Й (п) — Й 1(ив й~(и))),... листьями соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
