книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

мом внутреннего упорядочения последовательности (число ото­

рируют качественно различный характер оценок числа действий для данного алгоритма и оптимальных сопоставительных.

Доказано, что в случае, когда значения приведённого

управляющего слова представляют случайные коды с равномер­ ным законом распределения (такой закон распределения явля­ ется приближённой моделью для множества реальных ситуап упорядочения), средняя длина его старшей части, позволяющей

отличить одну запись от всех остальных, равна 1!о(£г П + /,533

разрядам [ а] . Поэтому приближёян_я оценка среднего числа

отображений одной записи в указанном случае для отобразите-

льных алгоритмов взаимного упорядочения подпоследовательно­

-71-

Число ' сопоставлений

или отображений в

расчёте на одну запись

15

Рис.6 . Зависимость от параметров упорядочения числа сопоставлений при оптимальном сопоставительном упо­ рядочении и числа отображений при упорядочении о т о - бразительным алгоритмом внутреннего упорядочения последовательности.

Тсопоставительный метод для п = 8192Г

__4е ____________________ _______________

Р и с .7 . Оценки числа отображений при оптимальном упорядочении набора из 8192 записей и числа сопо­ ставлений при оптималгаом сопоставительном упоря­ дочения того же набора

- 7 3 -

риалом для образования новых ассоциаций, а в конечном ито­ ге - правильной последовательности всех записей.

Алгоритмы, в которых подпоследовательности записей

получают явное выражение с помощью средств ассоциативного

программирования (например, списков типа Б и В ), будем

именовать ассоциативными. Для них характерны следующие особенности:

а) Положение в памяти записей исходного набора оста­ ётся неизменным, поскольку получаемая правильная последо­

вательность записей задана не расположением записей, а

иными средствами. Иногда факт существования двух последо­ вательностей записей - правЛшной последовательности и списка типа А, представляющего исходный набор записей,-

оказывается существенным для пользователя.

б) Затраты на формирование последовательности записей

в процессе упорядочения, а, следовательно, и общие затраты

времени на упорядочение не зависят от размеров записей, в

отличив от случая, когда их последовательность представле­ на списком типа А.

в) Ассоциативные алгоритмы позволяют более гибко испо­

социативного программирования позволяет при заданных ресур­ сах памяти, если это требуется, образовывать большее число правильных последовательностей, построенных для различных управляющих слов, по сравнению с использованием неассоциа­

- 7 4 -

тивных алгоритмов.

Промежуточные последовательности записей при упорядо­

чении ассоциативными алгоритмами представлены ассоциатив­

реса связи цепных списков могут быть выделены в отдельный участок памяти. При этом принадлежность какого-либо адреса связи определённой записи определяется подразумеваемым со­ ответствием (например, по номеру позиции записи и номеру позиции, занимаемой адресом связи в выделенном участке) или прямым указанием адреса записи в элементе ассоциативной структуры, помимо уже имеющегося в нём адреса связи.

В некоторых случаях использования ассоциативных алго­ ритмов может потребоваться переход от ассоциативного спосо­ ба задания правильной последовательности к её заданию спис­ ком типа А. Если, например, она предназначается для информа ционного поиска, то неудобным является её представление од­ носвязным цепным списком, исключающее прямой доступ к отде­ льным её записям; кроме того, в несовершенных ЭВМ не может осуществляться передача данных между уровнями памяти в по­ следовательности, заданной цепным списком или. оглавлением;

наконец, пользователь может попросту не владеть навыками ассоциативного программирования, необходимыми для последую­ щего использования в его задаче такой последовательности.

Изменение способа её выражения может быть выполнено с помощью операторов, рассмотренных в § 6 гл .1 .

-7 6 -

§7. Классификация алгоритмов упорядочения данных Классификация представляет собой научную систематизацию

алгоритмов и имеет как теоретическое, так и практическое зна­

ности и различий алгоритмов упорядочения, я начинать его сле­ дует с различий наиболее абстрактного плана: в первую очередь алгоритмы следует различать по методу упорядочения, сопоста­ вительному или отобразительному. Тем самым выделяются 2 вет­ ви алгоритмов, для каждой из которых характерны специфические

дейотвия, лежащие в основе упорядочения. Эта специфика опре­ деляет качественно различный характер зависимости числа ос­ новных действий в алгоритмах от параметров упорядочения.

Наиболее весомыми различиями логической схемы алгоритмов

в каждой ветви являются различия по характеру исходных и воз­ никающих в процессе упорядочения (промежуточных) структур

- 7 7 -

алгоритмов, промежуточные структуры данных в которых нераз­ виты (алгоритмы упорядочения вставкой, обменом смежных запи­ сей и т . д . )• Рациональное усложнение используемых структур данных, приводящее к появлению иерархии в структуре, окупа­ ется увеличением быстродействия алгоритмов, сложность'которых

емых дейотвий обладают лишь алгоритмы включения записей в ди­ хотомическое дерево, иерархическое распределение элементов данных при работе которых обусловлено салим характером дре­

весной упорядоченности.

Как было показано выше, трансформация развитых промежу­

точных структур данных в процессе упорядочения монет быть изображена т .н . деревом трансформаций. Двоякая возможная ори­ ентация ребер дерева трансформации отражает .два диаметрально противоположных принципа преобразования промежуточных струк­

тур в алгоритмах, основывающихся на использовании либо внут­

ренней, либо взаимной упорядоченности подпоследовательностей.

В качестве дополнительных аспектов, которые уточняют ло­

гическую схему алгоритма, можно рассматривать:

- йээ;Ефцциент ветвления дерева трансформации, отражающий

степень нарастания числа взаимно упорядоченных подпоследова­ тельностей или сокращения числа внутренне упорядоченных;

иля сколь близкие т размеру сегменты получаются при разде­ лении;

- временной график слияния или разделения сегментов; в

одних алгоритмах частной задачей каждого момента их работа

- 7 8 -

являетоя максимально возможное упорядочение в одной из час­ тей последовательности записей ( " вертикальные" алгоритмы;

название обусловлено "ростом" отдельных поддеревьев или да­ же отдельных "веток"-путей в дереве трансформации, динами­ чески отображающем процесс упорядочения), в других алгорит­ мах степень упорядоченности поддерживается примерно одина­ ковой во всех частях общей последовательности записей ( "го­ ризонтальные" алгоритмы; в отображающем их дереве трансфор­ мации происходит равномерный рост всех путей, начинающихся от листьев или от корня).

После рассмотрения "направленности" дерева трансформа­ ции, его коэффициента ветвления и формы, временного графи­ ка "построения"дерева логическая схема алгоритма на "макро­ уровне" получает завершённость, чем и объясняется начальное положение указанных критериев в векторе критериев, использу­ емых при классификации алгоритмов упорядочения.

"Качество" алгоритма определяется не только общей схе­ мой его организации, но и характеристиками основных опера­ торов, используемых в её рамках. Например, насчитывается несколько операторов объединения внутренне упорядоченных сегментов, имеющих разную производительность, сложность и предъявляющих различные требова ия к объёму дополнительной памяти, используемой при упорядочении. Так, оператор объе­ динения, используемый в р -операторном алгоритме, рекурсив­ ным образом использует возможность замены акта объединения исходных сегментов 3 актами объединения их половин для све­ дения в конечном итоге объединения к манипуляциям с отдель­ ными записями. Такое объединение само может быть представле­ но троичным деревом, число ярусов в котором определяется

- 7 9 -

размером объединяемых сегментов. Следовательно, сложность объединения в расчёте на одну запись возрастает с ростом раз­ мера сегментов, в то время как в рассмотренном нами в § 3

главы П операторе она оотаётся практически постоянной. Та­ ким образом, экономия используемой памяти обусловила сниже­ ние производительности.

Переходя к следующему уровню детализации алгоритмов,

отметим, что.по существу одни и те же алгоритмы могут раз­ личаться лишь способом выражения последовательности записей в целом и отдельных её сегментов, следствием чего является различная техническая реализация перенумераций записей и переадресаций - для сопоставительных алгоритмов - и различ­ ное представление вектора значений, различная реализация переадресаций и включений записей в промежуточную структуру

- для отобразительных алгоритмов. ■

Построенное на основе рассмотренных Критериев классифи­ кационное дерево (рис*. 9) служит целям систематизации прин­

ципиально простых, фундаментальных алгоритмов упорядочения.

В реальных алгоритмах упорядочения может выигрышно сочетать­ ся использование сопоставительного и отобразительного метода,

взаимного и внутреннего упорядочения последовательностей,

"горизонтального" и "вертикального" графиков их получения и ад.

Ещё одним практическим аспектом, определяющим сложность

алгоритмов упорядочения и ограничивающим свободу выбора используемых структур данных, операторов и списков, является уровень памяти, используемой для размещения данных в процес­ се упорядочения» .Как известно, для устройств внешней памяти в той или иной степени характерным является использование последовательного доступа к данным. Поэтому время выборки