Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

- 7 7 -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 7 8 -

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

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

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

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

- 7 9 -

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

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

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

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

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

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

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

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

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

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

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

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

- 8 0 -

или записи во внешнюю память в расчёте на элемент данных

значительно сокращается, если пересылается совокупность по­

следовательно расположенных в памяти элементов (" блок" ) .

Данное обстоятельство в силу необходимости совместного рас­

смотрения упорядочиваемых данных и сегментации объёма внеш­

ней памяти требует соответствующей сегментации исходной и

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

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

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

ности, Этому требованию удовлетворяют алгоритмы взаимного

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

тавительные, так: и стобразительные. С целью повышения про-

А Л Г О Р И Т М Ы У П О Р Я Д О Ч Е Н И Я

[по сопоставительному методу] |п'о отобразнтельному методу)

Рис.9. Классификационное дерево алгоритмов упорядочения .

- 81-

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

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

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

Схематичное представление о распространённых алгоритмах упорядочения во внешней памяти читатель может получить из [7],

ГЛАВА Ш. ИНФОРМАЦИОННЫЙ ПОИСК

§I . Понятие информационного поиске, и его связь

опонятиями упорядочения и сортировки

Назначением структур данных, упорядоченных по содерка-

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

(например, по имени, по качественному признаку) с целью ис­

пользования другой части их содержания. В качестве опозна­

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

Например, объектом опознания могут служить отдельные запи­ си и ассоциации записей, отдельные фразы текстового мате­ риала, его параграфы и главы.

Процесс опознания элементов данных по содержанию на

любом уровне, их иерархии будем называть информационным по­

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

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

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

- 8 3 -

числе использований элементов этого уровня» приводящем к превышению суммарного выигрыша времени при доступе к дан­ ным над его проигрышем при организации в ЭВМ этого уровня.

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

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

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

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

элементов ассоциации, т .е . привносит большую определённость в расположение элементов, чем это требуется для сортировки.

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

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

ве нескольких характеристик, присущих описываемым объек­ там.

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

.ляющему слову, такая ассоциация записей представлена не­ которым его подсписком. Если подсписок не имеет представ-