Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 91
Текст из файла (страница 91)
В связи с последовательной природой ленты и в соответствии с правилом "первым включается - . первым исключается", которому подчиняется прямое чтение, нельзя взять за основу схемы распределения любое помеченное дерево. В дереве примера 1 данные записываются на ленту А на шагах 2 и 3; данные, записанные в течение шага 2, необходимо использовать раньше данных, записанных в течение шага 3. В общем случае, если осуществляется запись на ленту в течение шагов 1 и у, где г с у, первыми следует использовать данные, записанные в течение шага б Кали дерево содержит две ветви вида то должно выполняться условие й с б Кроме того, нельзя ничего записывать на ленту А мезсду шагами к и 1, поскольку между чтением и записью необходима перемотка.
Те читатели, которые внимательно прорабзтали упражнения нз раздела 5.4,4, сразу поймут, что допустимые деревья для поразрядной сортировки с прямым чтением на Т лентах — это в точности сильные Т-Яо-деревья, описывающие сортировку методам слияния на Т лентах с прямым чтением! 1См. упр. 5.4.4-20,) Вдннственное различие заключается в том, что все внешние узлы рассматриваемых здесь Т1 Т2 Т3 Т4 Начальное распределение 1 1 1 1 Шаг дерева о 13 12 — 123' Шаг дерева 4 12 1' 2' 123' Шаг дерева 3 1' — 2'3! 1'3' Шаг дерева 2 — 4' 3' 3' Шаг дерева 1 10! Если сравнить ее с поразрядной сортировкой, то очевидно, что оба метода имеют, в сущности, одну и ту же структуру, ио обратны во времени и имеют обратное расположение содержимого на лентах: 123' !две серии длиной 1 каждая, за которыми следует одна серия длиной 3) соответствует (3, 8, 9Ц4) 10) !два подфайла, содержащие по 1 ключу, перед которыми расположен один подфайл, содержащий 3 ключа), Двигаясь в другую сторону, люжио, в принципе.
построить поразрядную сортировку, двойственную многофазному слиянию, каскадному слиянию и т. д. Например, многофазному слиянию 21 серии на трех лентах, изображенному в начале раздела 0.4.2, соответствует «ледук!щая интересная поразрядная сортировка. Фаза Т! Т2 ТЗ 1од,... до) 1 !0,2,4,5,7,9,10,12,13,15,17,!8,20» 11,3,6,8,11,14,16,19) 11,3,6,8,11,14,16,19) 12,4,7,9,12,!5,17,20) 2 !0,5,10,13,18) 10,5,10,13,!8)(!.6,11,14,19) (2,7,12,15,20) (3,8,16Ц4,9,17) 13,8,!6Ц4,9,17)(5,10,16) 16,11,19Ц7,12,20) 10,1ЗЦ1,14Ц2,15) 10дзН1,14Н2,и) (3,16)...!7,20) 5 18ЦОЦ1ОН11Ц12) б 18)(9)(10)111)112)(13)...120) (ОЦ1)...
!7) деревьев помечены одной и той же лентой. Мы могли бы снять это ограничение, предположив, что существует окончательная фаза "сборки", на которой все записи переносятся на выводную ленту, или могли бы добавить его к правилам для Т- й!йз-деревьев, потребовав„чтобы начальный распределительный проход сортировки методом слияния был явно выражен в соответствующем дереве слияния. Иными словами, каждой схеме слияния соответствует схема распределения и каждой схеме распределения соответствует схема слияния. По некотором размышлении это становится понятным. Рассмотрим сортировку методом слияния, делающую все наоборот, т. е. разделяющую окончательный выводной файл на подфайлы, которые, в свою очередь, разделяются на другие подфайлы, и т. д.
Наконец, разделим файл на о' серий. Подобная схема может применяться к лентам тогда н только тогда, ко!2!а допустима соответствующая схема распределения для поразрядной сортировки Я ключей. Эта двойственность слияния н распределения почти точна; оиа не выполняется только в одном отношении: данные с вводной ленты должнь! сохраняться в разное время. Пример с восемью ключами, рассмотренный в начале этого раздела, очевидно, является двойственным сбалансированному слиянию на четырех лентах.
Пример с десятью ключами и частичными проходами соответствует следующей схеме слияния десяти серий !ес7!и скрыть фазы копирования — шаги 6-11 в дереве). Правило распределения, согласно которому ключи располагаются на лентах на каж- дом шаге, кажется магическим, но на самом деле оно имеет простую связь с системой счисления, использующей числа Фибоначчи! (См. упр. 2.) Обратное чтение. Двойственность поразрядной сортировки и слияния применима также к алгоритмам, читающим ленту в обратном направлении.
Мы определили ТНо-деревья в разделе 5.4.4, и нетрудно видеть, что они подходят для поразрядной сортировки в той же мере, что и для сортировки методом слияния. Поразрядная сортировка с обратным чтением была фактически рассмотрена Джоном Мочли (,1опп МапсЫу) еще в 1946 году в одной из первых опубликованных работ по сортировке вообще (см. раздел 5.5).
Мочли на самом деле предложил следующую схему сортировки. Фаза Т1 Т4 Т2 (0,1,2,...,9) (3, 6) (3, 6) (1, 8) (3,6Ц1,8) ТЗ (0,1,8,9) (0, '1,'8,'9) (0) 1 (4,5) 2 (4,5Ц2, 7) 3 (4,5Ц2,7Ц0,9) 4 (4,5Ц2, 7) (2,3,6,7) (9) (9ЦЗЦ7Ц6Ц5) (0Ц1)(2ЦЗЦ4) (0Ц1Ц2ЦЗЦ4Ц5)... (9) Эта схема не является самой эффективной среди всех возможных, но она интересна тем, что показывает: методы с частичными проходами рассматривались применительно к поразрядной сортировке еще в 1946 году, хотя в литературе по слиянию они появилнсь лишь около 1960 года. Эффективная конструкция схем распределения с обратным чтением была предложена в работе А. Вауеэ, САСМ 11 (1968), 491-493.
Пусть дано Р+ 1 лент и Я ключей; ра щелите ключи на Р подфайлов, каждый из которых содержит (о/Р1' или (Я/Р"; ключей, и примените эту процедуру рекурсивно к каждому подфайлу, Если о ( 2Р, то один подфайл должен состоять из единственного наименьшего ключа; его и следует записать на выводную ленту. (Общая конструкция с прямым порядком Р. М. Карпа, описанная в конце раздела 5.4.4, включает этот метод как частный случай.) Обратное чтение несколько усложняет слияние, поскольку оно обращает порядок серий. Соответствуюгций эффект возникает и при поразрядной сортировке. Рсзультат оказывается устойчивым илн неустойчивым в зависимости от того, какой уровень достигнут в дереве.
После поразрядной сортировки с обратным чтением, когда одни внешние узлы находятся на четных уровнях, а другие — на нечетных, для одних ключей относительный порядок различных записей с одинаковыми ключамн будет соеиадашь с первоначальным порядком, но для других он будет противоположеп исходному (см. упр. 6). Осциллирующал сортировка методом слияния также имеет свою пару в этой двойственности. При осциллирукпией поразрлднш1 соулпировке мы продолжаем разделять ключи, пока не достигнем подфайлов, содержащих только адин ключ или достаточно малых, чтобы поздаваться внутренней сортировке.
Такие подфайлы сортируются и записываются иа выводную ленту, затем процесс разделения возоб- новляется. Например, если имеются три рабочие ленты и одна выводная и если ключи являются двоичными числами, мы можем сначала поместить ключи вида Ох на ленту Т1, а ключи 1х -- на ленту Т2. Если на ленте Т1 больше записей, чем может поместиться в памяти, то вновь просматриваем ее и помещаем 00х на Т2 н 01х на ТЗ. Теперь, если подфайл 00х достаточно короткий, выполняем его внутреннюю сортировку, выводим результат, а затем начинаем обработку подфайла 01х. Подобный метод был назван Э. Х, Френдом каскадной псевдопоразрядной сортировкой [,7АСМ 3 [1956), 157-159); более подробно его разработали Х. Нзглер [Н.
На81ег) [,7АСМ 6 [19а9), 459 — 468), который дал ему красочное название— "метод двуглавого змия"., и Ч. Х. Годетт [С. Н. Сапбееее) [1ВМ Таей. 01ве)свите ВиЛ. 12 [Аргй, 1970), 1849-1853]. Имеет ли поразрядная сортировка преимуп1естио перед слиянием. Одним важным следствием принципа двойственности является то, что поразрядная еортпировка обычно хуже сортировки методом слияния. Это связано с тем, что метод выбора с замещением по сравнению с сортировкой 'методом слияния имеет определенное преимущество: нет очевидного пути такого построения поразрядной сортировки, чтобы можно было использовать процедуры внутренней сортировки, требующие более одной загрузки в память за один раз.
На самом деле осцнллирующая поразрядная сортировка часто будет порождать подфайлы, несколько меньшие, чем объем памяти, так что ее схема распределения соответствует дереву со значительно большим числом внешних узлов, чем было бы при использовании слияния н выбора с замещением. Соответственно возрастает длина внешнего пути дерева [т. е. время сортировки). [См. упр. 5.3.1-33.) Для внешней поразрядной сортировки существует, однако, одно важное применение. Предположим, например, что имеется файл, содержащий фамилии всех сотрудников большого предприятия в алфавитном порядке.
Предприятие состоит из десяти отделений, и требуется рассортировать файл по отделениям, сохранял алфавитный порядок сотрудников каждого отделения. Если файл длинный, значит, сложилась именно та ситуация, в которой следует применять стабильную поразрядную сортировку, так как число записей, принадлежащих каждому из отделений, будет, вероятно, больше числа записей, которые были бы в начальных сериях, полученных методом выбора с замещением.
Вообще говоря, если диапазон ключей так мал, что набор записей с одинаковыми ключами более чем вдвое превышает объем оперативной памяти, то разумно использовать поразрядную сортировку. Мы видели в разделе 5,2.5, что на некоторых высокоскоростных компьютерах внутареннлл поразрядная сортировка предпочтительнее слияния, поскольку "внутренний цикл" поразрядной сортировки обходится без сложных переходов. Если внешняя память очень бьютрая, то для таких машин может оказаться проблемой выполнение слияния данных с такой скоростью, чтобы поспеть за оборудованием ввода-вывода.
Позтому в подобной ситуации поразрядная сортировка, возможно, лучше слияния, особенно если известно, что ключи распределены равномерно. УПРАЖНЕНИЯ 1. [х0) В начале раздела 5,4 была определено общее ебаланеироышное слияние на Т лентах е параметром Р, 1 ~ Р ( Т. Покажите, чта оио соответствует поразрядной сортировке, использующей систему счисления ео смешанным основанием. 2. [М33] В тексте раздела схематически представлена многофазная поразрядная сортировка 21 ключа.
Обобщите ее для Б, ключей и объясните, какие ключи и на какой ленте оказываются в конце каждой фазы. [Указание. Рассмотрите систему счисления, использующую числа Фибоначчи; см. упр. 1,2.8-34.) 3. [МУ5] Распро*траннг.е результаты упр. 2 на ьшогофазную поразрядную сортировку с четырьмя или более лентами (см. упр. 5.4.2-10.) 4. [М33] Докажите, что схема распределении Эщенхерсте служит наилучшим способом сортировки десяти ключей иа четырех лентах без обратного чтения в том смысле, что соответствующее дерево имеет минимальную Шгииу внешнего пути среди всех "сильных 4-Яо-деревьев". (Такии образом, это, по существу, — наилучший метод, если не учитывать вреия перемотки.) б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
