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