книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие
.pdf-too -
Процедуры обработки переполнения могут быть различными.
Одни из них сохраняют упорядоченность таблицы по используе
мому управляющему слову даже при появлениях записей-"синони мов" и, следовательно, допускают применение в таблицах и ди хотомического поиска; при использовании других упорядочен ность нарушается или её характер становится весьма сложным.
В упорядоченных таблицах (назовём их " разбросанными") после
обнаружения занятости позиции используется логика .дихотоми ческого поиска по близости с целью размещения новой записи между ближайшими "снизу" и "сверху" записями. При этом воз можны 2 ситуации: а) ближайшие заш ей разделены незанятыми
(незанятой) позициями, тогда новая запись размещается на
ближайшую из них к месту отображения; б) ближайшие записи занимают смежные позиции, тогда для размещения между ними
новой записи приходится выполнять реорганизацию более или менее значительной части таблицы. Установлено, что размер этой части зависит лишь от значения коэффициента степени заполнения таблицы и при случайном характере отображений сравнительно невелик (в среднем), даже при значительной ве личине коэффициента [ 2 j . Существуют граничные значения это го коэффициента, превышение которых ведёт к проигрышу по времени поиска в таблицах, по сравнению с другими высоко производительными поисковыми алгоритмами.
Кроме указанного, при поиске местас,включения новой за писи может также использоваться принцип, подобный принципу поиска корня функции по методу хорд [ в ] , я даже такие эк зотические средства как матричный каталог [ э ] .
Возможны такие реальные наборы записей, которые харак теризуются ощутимой неравномерностью распределения зиаче-
ний их управляющих слов по числовой оси, к |
тощ же может су |
ществовать высокая корреляция Сво времени) |
появления записей |
с близкими значениями. Одним.из вариантов, |
обеспечивающих о е - |
хранение высокой производительности поиска в таблицах и в та ких случаях, является использование перемешанных таблиц, для которых характерным является различный характер правила упо рядочения при первоначальном отображении поискового образа и при возможном последующем процессе отыскания хранящейся
записи, или позиции для размещения новой записи. Поиск по
интервалу и по блязооти в таких таблицах становится мало эф фективным, Обозначим число позиций таблицы через М. Если
число Р - взаимно простое о М, то, начав о произвольной по
зиции таблицы и изменяя номер позиции с шагом Р (ила - Р }
суммирование или вычитание при его изменении производится по модулю М), можно за М последовательных актов получить
по одному разу номера всех позиций. Этот процесс и поло жен в основу последовательного поиска 1 -й незанятой позиции для размещения записи, в то время как первоначальное отобра жение выполняется обычным образом. Тем самым ослабляется■от
рицательный эффект вышеуказанных неравномерности и корреляции.
При отыскании записей, логика которого очевидна, приме няется сочетание отобразительного и сопоставительного мето дов поиска.
4 , Пример поиска по незакреплённым условиям в неупорядо ченном списке типа А при жёстких ограничениях величины ис пользуемой памяти. Как уже упоминалось при поиске с неза креплёнными условиями весьма важно'сократить число последо вательно используемых поисковых образов, (логика подобного поиска подробно рассмотрена в £ ю ] } . Это число определяет
-102-
кратность проверки записей при переборе. Целесообразно также осуществлять ограничение области перебора путём группировки
записей в процессе поиска.
Идея соответствующего алгоритма поиска для случая поиска по конъюнктивной совокупности 4 одинаково важных условий:
УШ, УП2, УПЗ, УП4 ‘поясняется рис. 10, на котором корень де рева изображает исходное множество записей, узлы частного подмножества корня представляют подмножества записей, в ко торых либо выполнено, либо не выполнено условие поиска УП1
(обозначим их соответственно как УБ1 и УП1), а на следующих
ярусах соответственным образом использованы прочие условия.
При группировке записей возможно получение пустых групп за писей, которые на рис. 1 0 показаны неэачернёншши кружка
ми. Группировка без дополнительных затрат памяти может быть выполнена, например, оператором разделения, рассмотренным в
§ |
3 главы П, воли в качестве критерия для помещения записи |
в |
тот и л е иной результатный магазин используется факт выпо |
лнения или не выполнения в записи проверяемого условия по иска. Очерёдность разделений подмножеств записей показана числом ниже узла, обозначающего разделяемое подмножество.
Рис. 10. Дерево, отображающее процесс поиска по не закреплённым условиям в неупорядоченном списке при жёстких ограничениях величины используемой памяти.
- 103-
Число выше узла имеет соответственный смысл дан группировка
Логика алгоритма такова: последовательно проверяется вы полнение условий поиска в подмножестве записей, для которых выполнились вое ранее проверенные условия (действия 1 ,2,3,4)<
Получение при акте разделения записей по очередное условию пустого подмножества записей, для которых оно должно выпол няться (действие * ) , вызывает необходимость разделения ранее оставленных подмножеств (действия 5 ,7 ,9 ), перемежающегося о группировкой в единые подмножества (показана скобками ____>)
записей с одинаковым количеством выполненных условий из чис ла проверенных (цепочка действий 6 ,8 ,1 0 ). В нашем примере максимальное число условий, выполняющихся в одной записи,
оказалось равным 3. Если бы оно было меньше, появились бы дополнительные последовательности действий, подобные цепоч ке действий'5 - 10.
§ 5, Использование при поиске средств адресного
|
программирования |
|
I . |
Использование оглавлений. В конце |
§ 3 данной главы |
рассматривались случаи возможного их использования. Для де |
||
тального |
изучения вопроса читатель отсылается к |
[ в ] . Логя- |
© |
|
|
ка поиска по совпадению, близости, интервалу при использо вания оглавлений базируется на логике аналогичных случаев
поиска в |
списке типа |
А. |
2 . |
Поиск в двоичных деревьях, узлами которых являются |
|
записи. |
Среди прочих двоичные деревья допускают наиболее |
|
простую реализацию процессов построения, преобразования |
||
дерева и поиска в нём. |
В общих чертах процедура такого по |
|
иска рассматривалась в |
§ 3 главы П. |
|
Одной из слонннх задач использования двоичных деревьев является задача физического исключения устаревших записей,
отображаемых внутренними узлами дерева. Такая запись служит
опорным элементом взаимной упорядоченности, |
существующей ме- ' |
аду всеми записями её правой ветви и всеми |
записями левой, |
и поэтому при исключении может быть заменена лишь ближай |
|
шей к ней по значению управляющего слова записью. Если по |
|
следняя является листом дерева, исключение первой требует всего I акта замены, В противном случае замещающая её за пись должна быть замещена ближайшей по значению и т . д . ,
вплоть до выявления замещающей записи, являющейся листом.
Естественным средством поиска в двоичных деревьях яв ляется дихотомический поиск, при атом последовательно рас сматриваемые опорные записи отображаются цепочкой дерева,
называемой путём поиска. Поэтому при поиоке нет надобности в задании граней множества неопределенности; а его сокраще ние выполняется не заменой верхней или нижней грани, а пе реходом в правую или левую ветвь опорной записи при про хождения через представляющий её уаел.
Логика пояска по совпадению в двоичном дереве подобна логике 2 варианта поиска по совпадению, рассмотренного в предыдущем параграфе: При следовании по пути поиска нахо дится 1 -я запись, удовлетворяющая условию поиска. Если по совпадению необходимо выявить все такие записи, то на 2 -й
фазе работы алгоритма тем же способом выявляются и осталь ные записи, находящиеся в поддереве, корневой точкой кото рого является найденная запись.
1 -я фаза поиска по интервалу также состоит в нахождении на пути поиска I -й записи, удовлетворяющей условию; отличие
- f 0 5 -
логшси 2 ~й фазы поиска от случая поиска по |
соьпаденяю состо |
ит в том, что при нахождении в левой ветви |
от I-й найденной |
записи очередной записи, удовлетворяющей условию поиска, все
записи в правой ветви последней оказываются результатом по иска, "симметричный" принцип справедлив и для поиска в пра вой ветви от I-й найденной записи.
Логика поиска по близости требует запоминания адресов
последних элементов, у одного из которых при следовании по
пути поиска использовался левый, а у другого - правый адрес,
так как значения именно этих элементов являются ближайшими
"снизу" и "сверху" к поисковому образу из всех рассмотренных элементов (возможны случаи, когда один из таких элементов .
отсутствует: поисковый образ больше максимального или мень ше минимального значения, представленного в дереве). Выбор в качестве результата одного из них определяется характером заданного в условии поиска минимального отклонения.
Важнейшей проблемой использования двоичных деревьев яв ляется поддержание приемлемой с точки зрения производитель
ности поиска и включения запиоей формы дерева; оно осущест |
||
вляется перестройками дерева при отклонении его формы от |
||
допустимой. |
Для детального изучения перестраиваемых деревь- |
|
ев читатель |
отсылается к £ з ]. |
|
3. |
Словари. Словари являются характерным примером прак |
|
тического использования недвоичннх деревьев. Пример словаря |
||
изображён на рис. I I . |
В данном дереве узел содержит код бук |
|
вы, двоичный признак, |
одно из состояний которого соответст |
|
вует. внутренним буквам олова, а другое - конечным (либо в алфавит вводится специальный символ окончания слова, исполь зование которого потребует также добавления адреса связи ),
- Ю6-
адреоа связи, максимальное количество которых определяется числом символов алфавита. Столь значительный расход памяти под служебную информацию, как правило, неоправдан.
Тот же словарь, изображённый на р и с.1 2 ,содержит меньшее число адресов связи, так как частные подмножества представ лены в виде списков типа А - "гнёзд". При относительно не-
Рис. 12. Дерево-словарь.Пример 2. s означает конец слова. 0
-ю > ~
большом размере гнёзд даже перебор является приемлемым спо собом для поиска в гнёздах очередной буквы слова.
При включении нового слова выполняется поиск максимальной
по длине старшей его части, уже имеющейся в дереве, остальные
буквы его добавляются в виде новых узлов с указанием признака оконечной буквы слова, даже если все буквы нового слова уже
представлены частью имевшейся цепочки |
(например, если при на |
личии в словаре слова " догма" заносится слово " д о г "). При |
|
исключении слова происходит стирание индивидуального его |
|
окончания (если последняя буква слова |
являлась листом дере |
в а ). Признак окончания слова стирается |
в любом случае (напри |
мер, при устранении слова "дог" - это |
единственное действие). |
Код буквы не является обязательной составной частью уз |
|
ла: если размер гнёзд взять равным максимально возможному, |
|
становится возможным отыскание строк дерева не по сопостави тельному, а по отобразительноыу принципу, приведя в соответ ствие порядковый номер буквы в алфавите и номер её позиции в гнезде. Такое представление дерева изображено на рис. 13, где гнёзда представлены горизонтальными строками, узлы дерева -
их секциями, |
содержащими в качестве ссылок адреса |
или номера |
||||||||
5 Нёзд. |
|
|
|
|
|
|
|
|
|
|
• |
» |
I |
» |
I |
t i t |
i |
t I |
|
|
• |
9 |
ж |
|
|
|
|
ж |
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
7 |
* |
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
5 |
* |
|
|
|
& |
|
|
|
|
|
4 |
|
* |
|
|
|
S |
|
* |
7 |
S |
3 |
* |
|
|
|
|
9 |
|
3 |
|
|
г |
|
|
2, |
|
|
|
|
|||
1 |
А 6 |
|
/г л м н о п р |
|
с г * |
я |
||||
•АП |
|
А |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
Рис. |
13. |
Пример словаря |
с |
позиционным представлением букв. |
||||||
4 0 8 -
П Р И Л О Ж В Н И Е
Ниже приводятся процедуры с целью иллюстрации содер
жимого отдельных параграфов пособия. Оптимизация процедур
с тонки зрения их практического использования специально
не осуществлялась.
I . Операторы изменения выражения абстрактных структур данных (см . § 6 гл . I)
а) Оператор "Оглавление - |
список типа А" |
|
||||
p-iocedv'ie IZM tt п .) записей: ( Z |
) их оглавление: ( А ) ; |
|||||
осгау z : inteoez ctzzai/А\ |
|
in i ере г |
п\ |
8 |
||
Begin |
гео£ г ; |
inteyez |
|
Boolean azzoj/fiл]- |
||
cowmen4- |
следующий оператор приводит в |
исходное |
состоя |
|||
ние вектор В ; / о ? |
l :=I step |
I |
untiB п do |
tzoe ; |
||
commentf~ параметром цикла следующего оператора является
индекс оглавления; |
L := l |
step I untiB п do |
i£ 8[t]then Begin |
z x=Z[ij\ |
comment выполнена засылка |
Z[i]в буфер для освобождения начальной "вакантной"позиции;
к\~ i \ /о* J : = А[к] whiBe J ф/ Begin Z[Kh~Z[jJ;
R[i]-= tatse ; k\=J end одного замещения записей из цикла
замещений, присвоение ^/Узначения |
-foBse |
фиксирует факт |
окончательного размещения записи |
н ау ’-й |
позиции\Z C k J--t |
e n d цикла замещений'после установки записи из буфера йа
позицию; |
end IZM1 |
|
б)0ператор " Цепной список •* оглавление" |
||
p la ce d U Z € IZM 2{П ) элементов цепного |
списка:(АО его |
|
фиксатор начала:{-fn) оглавление:(ДО); |
L n te a e z щ . fn ; |
|
in t e g e r |
a z z a g А/, А2 ; c o m m e n t сбответствие между |
|
записями и элементами массива А2 (оглавление) осуществля
ется по содержимому элементов (ссылкам), в то время как соответствие между записями и элементами массива AI осуще ствляется по их индексам (элемент с наименьшим индексом соответствует записи с наименьшим индексом и т . д . ) ;
B eg in |
in te g e r |
i |
; < / : = / '? ; - f°? / : = 1 ste p i i/a tjB n ch |
B e g in |
com m en t следующий оператор размещает адреса свя-с |
||
за цепкого списка |
в виде оглавления; А 2.[1]\~А 1П ]Щ, J - |
||
com m ent |
продвижение |
по цепочке; end end_ JZM2 |
|
-Ю 9 -
в) Оператор "Цепной список - описок типа А"
procedu re |
I Z M 3 ( гг) |
записей:( Z ) |
цепной описок:(А1) его |
||||||||||||
фиксатор: ( / я / ) ; |
|
in te g e r |
n .'- fn h |
|
a r z a g |
Z |
; |
' |
|||||||
Integer |
a r ia у |
Ah |
|
A2 ; |
|
integer J n2. i,/\ & • |
|||||||||
Begin |
integer |
azzag |
|
||||||||||||
J , |
: = / / ? / ; |
J o z |
/ Ы I s te p |
1 u n t ie |
|
(/?-1 ) |
Vo_ S ep in |
||||||||
A 2 [A i[jll i - J ; |
1'.= А 1ф e n d |
построения^ встречного |
цепного |
||||||||||||
списка А2 |
с фиксатором fh Z 3 J-n2x=g |
; |
J |
' - f a t » |
|
|
|||||||||
/от / r : = i |
step |
1 unii t |
п do |
Begin |
|
геаВ г ; |
|||||||||
г -.-ZiK7; Z[kb=Z[j]; Z [J]i- |
г ; comment предыдущие 3 |
||||||||||||||
оператора реализуют обмен для установки J |
- й записи i-a/f-ю |
||||||||||||||
позицию формируемого списка |
типа_А; |
|
М: |
i |
:= |
A i[ g l\ |
|||||||||
A |
i [ j ] := A t [ к ] |
;A 1[A 2 [ к ] ] |
; |
c o m m e n t |
предыдущие |
||||||||||
2 |
оператора отражают переключения в |
исходном, |
а следующие |
||||||||||||
2 |
оператора - во |
встречном |
списке, |
отражающие изменение |
|||||||||||
позиции записи, |
|
перешедшей с к -й на ^ /-ю |
позицию; |
|
|||||||||||
А 2$]:=А 2[1<}, A 2[A 1[K U -=J |
; J |
: = i |
; |
c o m m e n t |
продви |
||||||||||
жение по цепочке, см.также |
оператор с меткой М; |
e n d од |
|||||||||||||
ного |
замещения |
записей |
e n d |
i z М 3 - |
|
|
|
|
|
||||||
|
|
г ) Оператор "Дихотомический описок - |
односвязный цеп |
||||||||||||
ной |
список" |
|
|
|
|
|
|
|
|
|
|
|
|
||
рweedиге IZMi{ П ) левых адресов или адресов связи одно-г связного: ( / J Z ) правые адреса:(АР); comment АР[о]~ фиксатор корня, а затем фиксатор начала одноовязного цепного списка;
integer |
п ; integer a rra y |
AL, |
АР; |
||
Begirt |
Boolean |
arza g |
В [l\rij\ |
comment элемен |
|
ты массива АО представляют адреса |
"обратной связи" в ди |
||||
хотомическом списке; |
integer |
i |
, J >к ; com m ent i - |
||
текущий фиксатор последнего из элементов, включённых в од
носвязный список к некоторому моменту; integer |
arrop |
||||
АО[lift]; comment |
массив В необходим для различения |
||||
элементов уже включённых в односвязный список от ещё не |
|||||
включённых, следующий оператор приводит его к исходному |
|||||
состоянию; |
к°г i :=I |
step I a n tiВ п do B[i}.= -faUse ; |
|||
J:=Q; comment это |
означает, что отправной точкой служит |
||||
корень; MI; I %=/ ; |
comment далее осуществляется переход |
||||
по |
правому адресу |
(вначале - от фжеатора к корню) |
и если |
||
он |
не пуст, |
то затем ври переходе по цепочке 'по индексу^) |
|||