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

- 6 0 -

чем в предыдущем случае. Он выполняется в 2 этапа, первым

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

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

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

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

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

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

- 6 f -

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

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

рения.

В случае использования списка типа Б вышеописанная

процедура выполняется лишь с тем отличием, что вычисляют­

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

Ш. Отобразительное упорядочение, результатом которо-

го является разбросанная таблица. При неограниченных ре­

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

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

как совокупность укрупненных позиций- ( надпозиций) . каждая

из которых может вместить количество записей, равное макси­

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

зиция. Дрд ограничении ресурсов оперативной памяти для по- <•

лучения номера позиции может быть использована старшая

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

заш оей, может оказаться одинаковым. Такие записи также

именуются синонимами. В частности, синонимами оказываются

заш ей с полностью одинаковыми управляющими словами. Для

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

бует, чтобы число позиций было не меньше числа размещаемых

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

Разбросанные таблицы удобны для представления дйцрмя-

ческих правильных последовательностей.(Сравни с дихотомиче­ скими деревьями).

1У. Представление элементов вектора. Характер элемен­

тов вектора значений, *с одной стороны, определяется типом

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

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

а) Имеется взаимно однозначное соответствие между

- 6 3 -

имеют одинаковый размер,

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

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

Для 1-й записи исходного списка определяется её номер в

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 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 ~ бит. Число включений записей

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