Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 15
Текст из файла (страница 15)
Основные требования к ней очевидны: она должна легковычисляться и распределять равномерно. Один из возможных подходовзаключается в следующем.1. По символам строки s определяем положительное целое H.Преобразование одиночных символов в целые обычно можно сделатьсредствами языка реализации. В Паскале для этого служит функция ord, вСи при выполнении арифметических операций символьные значения93трактуются как целые.2. Преобразуем H, вычисленное выше, в номер списка, т.е.
целоемежду 0 и m-1, где m - размер таблицы расстановки, например, взятиемостатка при делении H на m.Функции расстановки, учитывающие все символы строки,распределяют лучше, чем функции, учитывающие только несколькосимволов, например в конце или середине строки. Но такие функциитребуют больше вычислений.Простейший способ вычисления H - сложение кодов символов.Перед сложением с очередным символом можно умножить староезначение H на константу q. Т.е.
полагаем H0=0, Hi=q*Hi-1+ci для 1<=i<=k,k - длина строки. При q=1 получаем простое сложение символов. Вместосложения можно выполнять сложение ci и q*Hj-1 по модулю 2.Переполнение при выполнении арифметических операций можноигнорировать.Функция Hashpjw, приведенная ниже [3], вычисляется, начиная сH=0. Для каждого символа c сдвигаем биты H на 4 позиции влево идобавляем очередной символ. Если какой-нибудь из четырех старших битH равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем помодулю 2 с H и устанавливаем в 0 каждый из четырех старших бит,равных 1.#define PRIME 211#define EOS '\0'int Hashpjw(char *s){ char *p;unsigned H=0, g;for (p=s; *p != EOS; p=p+1){H=(H<<4)+(*p);if (g = H & 0xf0000000){H=H^(g>>24);H=H^g;}}return H%PRIME;}Рис. 6.56.5. Таблицы на деревьяхРассмотрим еще один способ организации таблиц с использованием94двоичных деревьев.
Будем считать, что на множестве идентификаторовзадан некоторый линейный порядок (например, лексикографический), т.е.задано некоторое отношение '<', транзитивное, антисимметричное иантирефлексивное. Каждой вершине двоичного дерева, представляющеготаблицу символов, сопоставлен идентификатор. Вершина может иметьнуль, одного (правого или левого) или двух (правого и левого) потомков.Если вершина имеет левого потомка, то идентификатор, сопоставленныйлевому потомку, меньше идентификатора, сопоставленного самойвершине; если имеет правого потомка, то ее идентификатор больше.Элемент таблицы изображен на рис. 6.6.TPIdentLeftRightРис. 6.6struct TreElement{struct TreElement * Left, * Right;String IdenP;};Поиск в такой таблице может быть описан следующей процедурой:TreElement * SearchTree(String Id,TreElement * TP){int comp;if (TP==NULL) return NULL;comp= IdComp(Id,TP->IdenP);if (comp<0) return(SearchTree(Id,TP->Left));if (comp>0) return(SearchTree(Id,TP->Right));return TP;}Занесение в таблицу осуществляется функцией:TreElement * InsertTree(String Id,TreElement * TP);TreElement * fill(TreElement * P, String Id){ if (P==NULL){P=new TreElement();P->IdenP=Include(Id);P->Left=NULL;P->Right=NULL;return(P);95}else return(InsertTree(Id,P));}TreElement * InsertTree(String Id,TreElement * TP){int comp= IdComp(Id,TP->IdenP);if (comp<0) return(fill(TP->Left,Id));if (comp>0) return(fill(TP->Right,Id));return(TP);}Как показано в работе [7], среднее время поиска и занесения в таблицуразмера n, организованную в виде двоичного дерева, при равнойвероятности появления каждого объекта равно 2ln(2)log2(n)+C, чтопревышает на 40% среднее время поиска в упорядоченном массивеметодом двоичного поиска.
Это превышение обусловлено тем, что деревонеизбежно оказывается несбалансированным: имеются более длинные иболее короткие ветви.Чтобы ускорить среднее время поиска в двоичном дереве, можно впроцессе построения дерева следить за тем, чтобы оно все времяоставалосьсбалансированным.Аименно,назовемдеревосбалансированным, если ни для какой вершины высота правого поддереване отличается от высоты левого более чем на 1.
Ясно, что для того, чтобыдостичь сбалансированности, в процессе построения дерево иногдаприходится слегка перестраивать [8]. Определим для каждой вершиныдерева характеристику, равную разности высот правого и левого еепотомков. Для сбалансированного дерева характеристика вершины можетбыть равной -1, 0 и 1, для листьев она равна 0).
Пусть мы определилиместо новой вершины в дереве. Ее характеристика равна 0. Рассмотримотрезок пути от новой вершины к корню, такой, что характеристики всехвершин на нем равны 0 (до перестраивания). Пусть A - верхний(ближайший к корню) конец этого отрезка. A - либо корень, либо имеетхарактеристику 0. Если A - корень, то дерево перестраивать не надо,достаточно лишь изменить характеристики вершин на нем на 1 или -1, взависимости от того, влево или вправо пристроена новая вершина.Если верхний конец A отрезка с характеристикой 0 не корень, товозможны следующие варианты.
Если A имеет характеристику 1 (-1) иновая вершина добавляется в правое (левое) поддерево, то характеристикавершины A становится равной 0 и дерево перестраивать не надо.Пусть теперь характеристика A до перестраивания равна -1 и новаявершина добавлена к левому поддереву A (аналогично - для случая 1 идобавления к правому поддереву). Возможны следующие варианты.96A(-2,n+3)B(-1,n+2)C(n)A(0,n+1)D(n+1)B(0,n+2)D(n+1)E(n)E(n)Новая вершина(а)C(n)(б)Рис.
6.7A(-2,n+3))B(1,n+2)D(n)C(n)E(0,n+2)C(n)B(0,n+1)E(-1,n+1)F(n)Новая вершинаа)G(n-1) D(n)Рис. 6.897A(1,n+1)F(n)G(n-1)б)A(-2,n+3))B(1,n+2)D(n)A(0,n+1)C(n)E(0,n+2)C(n)B(-1,n+1)E(-1,n+1)F(n-1)G(n)D(n)Новая вершинаа)Рис. 6.9F(n-1)G(n)б)Рассмотрим вершину B - левого потомка A. Если характеристика Bпосле добавления новой вершины в D стала равна -1, то дерево имеетструктуру, изображенную на рис. 6.7(а). Перестроив дерево так, как этоизображено на рис.
6.7(б), мы добьемся сбалансированности (в скобкахуказаны характеристики вершин, где это существенно, и соотношениявысот после добавления).A(-2,2)B(1,1)E(1,0)B(0,0)A(0,0)E(0,0)Новая вершинаРис. 6.10Если характеристика вершины B после добавления новой вершины в Eстала равна 1, то надо отдельно рассмотреть случаи, когда характеристикавершины E, следующей за B на выделенном пути, стала равна -1, 1 и 0 (впоследнем случае вершина E - новая).
Вид дерева до и после перестройкидля этих случаев показан соответственно на рис. 6.8, 6.9 и 6.10.986.6. Реализация блочной структурыС точки зрения структуры программы блоки (и/или процедуры) образуютдерево. Каждой вершине дерева этого представления, соответствующейблоку, можно сопоставить свою таблицу объектов (и, возможно, однуобщую таблицу идентификаторов). Работу с таблицами блоков можноорганизовать в магазинном режиме: при входе в блок создавать таблицуобъектов, при выходе - уничтожать.
При этом сами таблицы должны бытьсвязаны в упорядоченный список, чтобы можно было просматривать их впорядке вложенности (рис. 6.11). Если таблицы организованы с помощьюфункций расстановки, это означает, что для каждой таблицы должна бытьсоздана своя таблица расстановки.T1T2TnРис.
6.116.7. Сравнение различных методов реализации таблицРассмотрим преимущества и недостатки тех или иных методовреализации таблиц с точки зрения техники использования памяти. Еслитаблица размещается в массиве, то, с одной стороны, отпадаетнеобходимость использования динамической памяти, а с другой появляется ряд осложнений.
Использование динамической памяти, какправило, довольно дорогая операция, поскольку механизмы поддержанияработы с динамической памятью довольно сложны. Необходимоподдерживать списки свободной и занятой памяти, выбирать наиболееподходящий кусок памяти при запросе, включать освободившийся кусок всписок свободной памяти и, возможно, склеивать куски свободной памятив списке. С другой стороны, использование массива требует отведениязаранее довольно большой памяти, а это означает, что значительнаяпамять вообще не будет использоваться. Кроме того, часто приходитсязаполнять не все элементы массива (например, в таблице идентификаторовили в тех случаях, когда в массиве фактически хранятся записипеременной длины, например если в таблице символов записи дляразличных объектов имеют различный состав полей).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
