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

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

в) Управляющее слово является лишь частью записи, при­

чём нет взаимно однозначного соответствия между значением управляющего слова записи и номером записи в правильной по­

следовательности. Значения управляющих слов не повторяются.

Список записей - типа А.

Элементом вектора является, как и в предыдущем случае,

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

ка записей для распределения мест в правильной последовате­

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

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

предварительное распределение мест и дополнительная память,

хранящая информацию о результатах этого распределения.

г) Значения управляющих слов, возможно, повторяются,

и нет взаимно однозначного соответствия между значением уп-

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

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

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

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

- 6 5 -

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

Такой способ деления во многих случаях уменьшает число фра­

гментов.

Получение правильной последовательности записей смо­ жет затем быть выполнено подобно построению лексикографи­ чески упорядоченной последовательности (см . §2 г л .1 ). Ме­ тодом отображения осуществляется упорядочение исходной по­ следовательности записей по значению самого старшего фраг­ мента управляющего слова. При этом внутри последовательно­ сти возникают взаимно упорядоченные подпоследовательности записей, характеризуемые одинаковым значением данного фра­ гмента. Значение следующего по старшинству фрагмента ана­ логичным образом используется для независимого разделения каждой из них на взаимно упорядоченные подпоследовательно­ сти меньшего размера и т .д . Разделение очередной подпосле­ довательности не назначается в случае выполнения хотя бы

6 6 -

одного из 2 условий: а)подпоследовательность содержит един­ ственную запись; б)все фрагменты управляющего слова записей подпоследовательности проанализированы.

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

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

Упорядоченность по его значению, возникающая после I этапа,

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

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

о

-6 7 -

последовательности записей. Дальнейшие этапы, имение мес­

то, если фрагментов более,чем два, протекают стереотипно с

рассмотренным. Процесс такого упорядочения отображением за­

т е е й иллюстрируется графом, изображённым на рис.5.

Алгоритмы упорядочения рассмотренного рода будем име­

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

ния последовательности.

Подпоследовательности , внутренне упорядоченные по совокупности {к -2) младших фрагментов

управляющего слова

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

У1. Разрядное упорядочение. Разрядные алгоритмы явля­

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

ляются в особую группу ввиду особенностей их реализации,

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

- 6 8 -

дочения: соответственно двум возможным значениям двоичного разряда в результате выполнения этапа возникают только две ассоциации записей. Тем самым для каждой просматриваемой записи возможны 2 исхода: попадание в I-ю или во 2-ю ассо­ циацию. Это сближает разрядные алгоритмы с сопоставитель­ ными алгоритмами и позволяет осуществить распределение по­ зиций между записями в процессе единственного на каждый анализируемый разряд просмотра путём перенумерации запи­ сей обменом. Используемый при этом оператор разделения от­ личается от оператора, описанного в §3 гл.П, лишь принци­ пом отнесения записей к одному из результатных магазинов:

согласно значению анализируемого двоичного разряда.

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

§ 5 . Сравнение отобразительного и сопоставительного методов упорядочения

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

туры памяти, в случае,же написания алгоритмов упорядочения

о

_ 69-

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

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

ляя) •

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

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

Сначала сравним сопоставительный метод и одноэтапную

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

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

П . Это свидетельствует о более высокой информационной

ценности отображения записи по сравнению с сопоставлением.

'Если правильная последовательность простая, то одним отоб­

ражением снимается энтропия, равная по величине

h>g-2ti,./ n ~ n k>§2n/ n ~ бит. Число включений записей

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

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

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

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

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

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

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

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

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