Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 26
Текст из файла (страница 26)
Но в действительности даже небольшие вычислительные машины обладают некоторой оперативной памятью с произвольным доступом, которая почти всегда больше той, которая требуется для разработанных здесь программ. Непростптсльно было бы не попытаться использовать ее оптимальным образом. Решение закл|очается в комбинировании методов сортировки массивов и файлов.
В частности, адаптированную сортировку массивов можно использовать на фазе распределения начальных серий так, чтобы в результате эти серии имели длину 1, приблизительно равную размеру имеющейся оперативной памяти. Очевидно, что на последующих проходах никакие дополнительные сортировки массивов не дадут какого- либо улучшения, так как длина участвующих в них серий постоянно растет и, следовательно, всегда будет больнице имеющейся оперативной памяти. Поэтому мы можем сосредоточить внимание на оптимизации алгоритма, который формирует начальные серии, Конечно, мы сразу обращаемся к логарифмическим методам сортировки массивов. Наиболее подходящий из них— это сортировка с помощью дерева, нли пирамидальная сортировка (см.
разд. 2.2.5). Пирамиду можно рассматривать как туннель, через который должны пройтп все компоненты файла, некоторые — быстрее, некоторые — медленнее. Наименьший ключ легко извлекается с вершины пирамиды, а его замещение — очень эффективный процесс. Пропуск компоненты с входной ленты 10 через весь «пирамидальный туи- з. Сортировка 142 пель> Л на выходную ленту )[1] можно просто описать следующим образом: гоп1е() Ц, 611]); таас((]0, 6 ]1] ); е111(1, и) (2.51) «511Ь («просеивание») — это процесс, описанный в равд. 2.2.5. Новая вставляемая компонента Л(1] просеивается на соответствующее место. Отметим, что й11] — наименьший элемент в пирамиде. Пример дан на рис.
2.17. Состояние до передача злемента: 1 2? Состоанне после передачи очередного элемента: 1О Рнс. 2.17. Просенеанне ключа через пнраннду. В конечном счете программа значительно усложняется, поскольку: 1. Пирамида й вначале пуста и прежде всего должна быть заполнена. 2. К концу работы пирамида заполнена лишь частично, а в самом конце становится пустой. 3, Нужно сохранять информацию о начале новых серий, для тОго чтобы вовремя сменить иидекс выходной ленты 1. 2.З. Сортировка последов«тел»них файлов Прежде всего опишем формально переменные, явно участвующие в работе: чаг ]О: горе; 1: аггау[!арене] о(гаре; Ь: аггау[1 ..
пт] о$ !гет; 1,т: !л!вйег (2.52) т — размер пирамиды Ь. Для обозначения тп/2 мы исполь- зуем константу тпЬ; ! и г — индексы в Ь. Процесс пропуска элементов через пирамиду можно теперь разбить на пять отдельных этапов: 1. Прочесть тпЬ первых элементов с [О и записать их в верхнюю половину пирамиды, где не требуется никакого упорядочения ключей. 2. Прочесть тЬ остальных элементов и записать их в нижшою половину пирамиды, просеивая каждый элемент на соответствующее место (построить пирамиду). 3.
Установить ! в тп н выполнить для оставшихся на !О элементах следующий шаг: отправить Ь[1] на текущую выходную ленту. Если его ключ меньше нли равен ключу следующего элемента входной ленты, то этот следующий элемент принадлежит той же серии и его можно просеять на подходящее место.
В противном случае надо уменьшить размер пирамиды и поместить новый элемент во втору1о, «верхнюю» пирамиду, которая строится для следующей серии. Границу между двумя пирамидами обозначим ин. дексом!. Итак, «нижняя»», или текущая, пирамида состоит из элементов Ь[1] ... Ь[!], а «верхняя», нли следующая, пирамида — из Ь[!+1] ... Ь[пт]. Если ! *О, то нужно сменить выходную ленту и вновь установить ! в тп. 4. Теперь входные ленты исчерпаны. Вначале установить г в и, затем сбросить на выходную ленту нижнюю часть пирамиды, заканчивающую текущую серию, одновременно построить верхнюю часть и постепенно переместить ее в позиции Ь [!+ 1] ...
Ь [г]. 5. Последняя серия формируется из оставшихся элементов пирамиды. Теперь мы можем подробно описать эти пять этапов в виде законченной программы, вызывающей процедуру ве!вс!горе как только найден конец серии и нужно совершить некоторое действие, изменяющее индекс выходной ленты. В программе 2.17 вместо этого используется фиктивная процедура: она просто подсчитывает число сформированных серий. Все элементы записываются на ленту !1. 2.
Сортировка Если теперь мы попытаемся объединить эту программу, например, с программой многофазной сортировки, то столкнемся с серьезной трудностью, Она возникает по следующим причинам: программа сортировки содержит вначале довольно сложную процедуру для переключения лент и предполагает наличие процедуры горугип, которая записывает на выбранную ленту ровно одну серию. С другой стороны, программа пирамидальной сортировки представляет собой сложную процедуру, предполагающую наличие закрытой процедуры зе(вс)(аре, которая просто выбирает новую ленту. Проблемы не возникало бы, если бы в одной (илн обеих) программе нужная процедура вызывалась лишь в одном месте, однако она вызывается в нескольких местах в обеих программах.
В такой ситуации лучше всего использовать так называемую сопрогралтму, как обычно рекомендуется, когда сосуществуют несколько процессов. Самый типичный пример-- комбииация процесса, который порождает поток информации, и процесса, который ее использует. Связь порождение/использование можно выразить в виде двух сопрограмм. Одна из них может быть основной программой.
Сопрограмму можно рассматривать как процедуру, или подпрограмму, которая содержит одну или несколько точек прерывания. Если встречается такая точка прерывания, то управление возвращается в программу, вызвавшую эту сопрограмму. При повторном вызове сопрограммы ее выполнение возобновляется с этой точки прерывания. В нашем примере мы можем рассматривать многофазную сортировку как основную программу„вызывающую соругитц которая построена в виде сопрограммы. Она состоит из основного тела программы 2.!7, где каждый вызов ье(есгГаре геперь представляет собой точку прерыванин, Проверку на конец файла нужно всюду заменить проверкой, достигла лн сопрограмма своего конца.
Логично заменить ео(((О) на еос(соругип). Анализ и выводи. Какой эффективности можно ожидать от многофазной сортировки с начальным распределением серий с помощью пирамидальной сортировки? Вначале мы обсудим, каких улучшений следует ожидать от использования пирамиды. В последовательности со случайно распределенными ключамн средняя длина серий равна 2. Какова эта длина после того, как последовательность пропущена через пирамиду размером т? Казалось бы, нужно ответить т, но, к счастью, результат вероятностного анализа на самом деле намного лучше, а именно равен 2пт (см. (2.7), т, 3, с. 304). Поэтому ожидаемый коэффициент улучшения равен т. ргойгага (!(з(г(Ьн(еЦО, Е 1,ои(ри(); (начальное распределение серий с помощью пирамидальной сортировки ) сапа( т = 30; (лЬ .= 15; (размер пирамиды1 Гуре Ие>л =-- гесога Ьеу: !п(едег епй; саре == 61е оЕ((е(п; !паех =-- О,, и; чаг 1,г: (пг(ех; ЕО,У'1: (аре; свил(: (л(ееег; '! счетчик серий ! Ь: аггау11 ..
т! о!нет; (пирамида( Еноеейаге зе1ес((аре; Ъга(п соил(: =- соил( + 1; (езиктивная щюцедураг подсчитывает число распределенных серий) епй (зе(еснаре); Ьгосег(аге зК~((,г: пи(ех); 1аЪе1 13; таг 1,1: !л(ееег( х: йет; Ьей!п(: —: 1;1:= 2ь(; х:=- ЬИ; ггЫ1е3 ~ г йо Ьеа(п 11 1 < г йеп 1Е ЬЦ .Ьеу ) Ь(!+Ц .Ьеу йеп (':= 1+1; !Е х .Аеу ~ Ь(Я Хеу йеп аа(о 13; Ьи:= ЬИ г':= 3'; 1:== 2г( епй; 13: Ь(!1:= х епа ; Ьеа!и ((йормнрование начальных серий с помощью пирамидальной сортировки! соил(: =- 0; газе((10); генг((е((' 1); зе1еснаре; (эгпап 1: заполнение верхней части пирамиды Ь ! 1: — -- т; гереаг геаЩО, ЬЯ); 1:= 1 — 1 пп(11 1 =- тЬ; (этап 2: заполнение нижней части пирамиды Ь ) гереас геаа(10, Ь111); з(Е(((,т); 1: =- 1 — 1 ппрй 1:-:: 0; [эп(ап 3; пропуск серий через пирамиду! г.
Сор р 1.'= т; эгЫе — еоУ'(УО) до Ъей[в иг!ге(Е'1, ЬЩ); Ы Ь[Ц .Ьеу ( Е01,ассу тЬеп Ьей[в [новая запись принадлеэкит той эев серии) гсагЕ(Е'О, Ь[Ц); зф(1,1); епй е1ае Ьеи[п [ новая запись принадлежит следуюи)ей серии) Ь[Ц:=- Ь[!); х[)г(1,! — 1); геагЕ(ЕО, Ь[!)); 11 1 ( тй 1Ьеп зфг(!т)! 11 Е-1; 11 1 = — О тЬев Ьей[п [пиралгида заполнена! начать новую серию) 1:=- т; эе!есиаре; евд епй епй ; [этап 4: сброс нижней части пирамиды) г:= т; хереа1 ит!ге[! 1, ЬЩ)1 ЬЩ:= Ь[1); эф(1>1-1); Ь[1):= ЬИ; .:= .-1; К 1 ~ тй [Ьепэ[)'г(1г) 1:= 1-1 ааб! 1= О; [этап 5: сброс верхней части, пирамиды; 4ораи[эоваиие последней серии) эе1есиаре; эеЫ1е г > 0 до Ьей[п ит!ге((1 Ь[Ц); ЬЩ:= Ь[г); эЯ[,г); и:= г — 1 епй; и гие!и (соил!) епд .
Программа 2.17. Распределение начальных серий с помошыо пирамиды, ' Оценку свойств многофазной сортировки можно получигь из табл. 2.15, определив максимальное число начальных серий, которые можно отсортировать за данное количество частичных проходов (уровней) при заданном числе п лент. Например, при и = 6 лентах и пирамиде размером и =100 Файл, содержащий до !65680100 начальных серий, можно отсортировать за 20 частичных проходов, Это — отличные характеристики. Упражнения Рассматривая программу, представляющую собой комбинацию многофазной и пирамидальной сортировки, нельзя че поразиться ее слогкности. Ведь она выполняет ту же самую, легко определимую задачу переупорядочения множества элементов, что и любая из коротких программ, основанных на простых методах сортировки массивов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
