Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 [ 68 ] 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

if (wl..key = x) Л (}vl Ф sentinel) then,

wl.count :== wllxount + 1 else (4.25)

begin иеи'(и'З); [включение w2 между wl uw2} with w3t do

begin fcey :== x; count I; next :=-wl end ; w2[.next := w3

end [search]

Теперь пора спросить, какого выигрыша можно ждать от поиска в упорядоченном списке. Учитывая, что дополнительное усложнение невелико, не следует ожидать каких-то по-Фрясагощих результатов.

Допустим, что все слова встречаются в тексте с одинаковой частотой. В этом случае, как только все слова окажутся в списке, выигрыш, достигнутый при помощи лексикографического упорядочения, фактически будет ничтожен; здесь позиция слова не имеет значения, поскольку важна лишь сумма всех шагов и все слова ищутся с одинаковой частотой. Однако выигрыш достигается при включении нового слова. Вместо всего списка просматривается в среднем только около поло; вины списка. Следовательно, включения в упорядоченный список стоит использовать лишь в случае, когда нужно пО строить словарь с большим числом различных слов, п сравнению с частотой появления. Поэтому приведенные выШ^ процедуры служат в основном в качестве упражнений в пр граммировании, а не для практического применения.

Помещать данные в связанный список рекомендуете в том случае, если число элементов мало (скажем, <100)> заранее неизвестно и, более того, нет никакой информаЦК

Чтобы ускорить поиск, условие продолжения в операхп цикла можно вновь упростить, используя барьер. Это Tpe6v присутствия фиктивного элемента как в начале, так и в kohi Следовательно, список должен инициироваться следую1Щ5 операторами:

newiroot); nevisentinel); root].next := sentinel; и процедура поиска заметно упрощается, что видно из (4.25)-

тосейте search(xi integer; yat root: ref);

var w\,\v2,w3: ref; begin wl := root; wl := w2\.next; sentinel\.key :~ x;

while wl\.key < x йо

begin w2 :~ wl; wl wl.next



йястоте обращения к ним. Типичный пример - таблица имен трансляторах с языков программирования. Как только тречается описание, новое имя добавляется к списку, а при тхоДб из области действия описания имя удаляется из спи-ка Простые связанные списки стоит использовать, если речь дет о сравнительно коротких программах. Даже и в этом учае можно значительно повысить эффективность доступа д^годаря очень простому приему, который мы здесь еще раз рассмотрим в первую очередь в связи с тем, что он служит Хорошим примером для демонстрации гибкости структуры вязанного списка.

root

sentinel


Рис. 4.11. Список до переупорядочения.

Для текста программ характерно частое скопление одного и того же идентификатора, т. е. за одним вхождением часто следует одно или более повторных вхождений того же слова. Это наводит на мысль реорганизовать список после каждого обращения, переставляя найденное слово в начало списка, так как тем самым минимизируется длина прохода по списку при следующем поиске того же слова. Этот метод называется гюиском по списку с переупорядочением, или - несколько пре-чттозяосамоорганизующимся поиском по списку. Описывая соответствующий алгоритм в виде процедуры, которую Можно подставить в программу 4.1, мы учтем предыдущий опыт и с самого начала введем барьер. Действительно, его Наличие в этом случае не только ускоряет поиск, но и упрощает программу. С самого начала список не пуст, а уже содержит барьер. Начальные операторы следующие:

new(sentinel); root := sentinel;

Заметим, что основное различие между новым алгоритмом простым поиском по списку (4.21) - переупорядочение при Нахождении элемента. Найденный элемент отделяется, или Удаляется со своего старого места и вставляется в начало, о удаление слова требует использования двух ссылок при Иске, чтобы можно было установить местонахождение эле-



мента ш2, предшествующего найденному элементу wlj в свою очередь требует особого обращения с первым эпёц том (т. е. с пустым списком). Чтобы читатель мог наглядц представить себе процесс изменения связей, мы отсылаем его к рис. 4.11. На нем изображены две ссылки в момент когда ш1 опознан в качестве искомого элемента. КонфигА,! рация списка после соответствующего переупорядочения п& казана на рис. 4.12, а новая процедура поиска целиком описана ниже:

procedure да(2/-сЛ(х: integer; уяг root: ref);

var wl,w2: ref; begin 41 := root; sentinel\.key := x; if wl = sentinel then begin (первый элемент] new{root); with roofl 0

begin/<-ej :- x; count :- 1; next;- sentinel end end else

if w\\Jcey = X then wl.couni := wl.count + 1 else begin [search]

repeat w2 :- wl; wl :- w2\.next

tmtil w.key = л:; (4 26)-

if wl ~ sentinel then begin [включение]

w2 := root; newQoot); with root] do

begin/сс; := x; count := 1; next := w2 end end else

begin [найден, теперь переупорядочивание списка] wll-couni := wlxount + 1; w2\.ncxt wljiext; wl.next :- root; root := wl

тй [search]

Выигрыш при таком методе поиска сильно зависит от степени скопления входных данных. При заданном коэффициенте скопления улучшение более ощутимо в случае больших спИ; сков. Для того чтобы получить представление о примерной величине выигрыша, который можно ожидать, были провО дены эмпирические измерения. Приведенная выше пpoгpaM составления частотного словаря применялась к коротки*




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 [ 68 ] 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133