Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

3) h2(i)=(a*i+c) mod N - "псевдослучайная последовательность".

Здесь c и N должны быть взаимно просты, b=а-1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [6].

void Search(String id, boolean * Yes, int * Point)
{int H0=h(id),H=H0;
while (1)
{if (!IdComp(H,id))
{*Yes=true;
*Point=H;
return;
}
else if (Empty(H))
{*Yes=false;
*Point=H;
return;
}
else H=h2(H);
if (H==H0)
{*Yes=false;
*Point=NULL;
return;
} } }

Поиск в таблице можно описать функцией, приведенной выше. Функция IdComp(H,id) сравнивает элемент таблицы по входу H с идентификатором и вырабатывает 0, если они равны. Функция Empty(H) вырабатывает 1, если вход H пуст. Функция Search присваивает параметру по ссылке result значения (true,P), если нашли требуемый идентификатор, и P - указатель на него, (false,NIL), если искомого идентификатора нет и в таблице нет свободного места, и (false,P), если искомого идентификатора нет, но в таблице есть свободный вход P.

Занесение идентификатора в таблицу можно осуществить следующей функцией:

int Insert(String id)
{boolean Yes;
int Point;
Search(id,&Yes, &Point);
if (!Yes && (Point!=NULL))
InsertId(Point,id);
return(Point);
}

Здесь функция InsertId(Point,id) заносит идентификатор id по входу таблицы Point.

Второй способ организации таблицы идентификаторов - хранение идентификаторов в сплошном массиве символов. В этом случае идентификатору соответствует номер его первого символа в этом массиве, как это изображено на рис. 6.2. Идентификатор в массиве заканчивается каким-либо специальным символом (EOS). Второй возможный вариант - в качестве первого символа идентификатора в массив заносится его длина. Для организации поиска в таком массиве таблица идентификаторов отделяется от таблицы расстановки (рис. 6.3).

s o r t EOS a EOS r e a d EOS i EOS

Рис. 6.2

0
...

9 Idenp x

...
Указатели на идентификаторы

20 Idenp x

...
Указатель на идентификатор

32
x


... Указатели на идентификаторы
210

Рис. 6.3

6.3. Таблицы символов и таблицы расстановки

Рассмотрим организацию таблицы символов с помощью таблицы расстановки. Таблица расстановки - это массив указателей на списки указателей на идентификаторы. В каждый такой список входят указатели на идентификаторы, имеющие одно значение функции расстановки (рис. 6.3).

Вначале таблица расстановки пуста (все элементы имеют значение NIL). При поиске идентификатора id вычисляется функция расстановки H(id) и просматривается линейный список T[H]. Поиск в таблице может быть описан следующей процедурой:

struct Element
{String IdenP;
struct Element * Next;
};
Element * Search(String Id)
{Element * P;
P=T[h(Id)];

while (1)
{if (P==NULL) return(NULL);
else if (!IdComp(P->IdenP,Id)) return(P);
else P=P->Next;
}
}

IdenTab - таблица идентификаторов. Занесение объекта в таблицу может осуществляться следующей процедурой:

Element * Insert(Id:string)
{Element * P,H;
P=Search(Id);
if (P!=NULL) return(P);
else {H=H(Id); P=new Element();
P->Next=T[H]; T[H]=P;
P->Idenp=Include(Id);
}
return(P);
}

H






P

Рис. 6.4.

Процедура Include заносит идентификатор в таблицу идентификаторов. Алгоритм иллюстрируется рис. 6.4.

6.4. Функции расстановки.

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

1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.

2. Преобразуем H, вычисленное выше, в номер списка, т.е. целое между 0 и m-1, где m - размер таблицы расстановки, например, взятием остатка при делении H на m.

Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например в конце или середине строки. Но такие функции требуют больше вычислений.

Простейший способ вычисления H - сложение кодов символов. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H₀=0, H_i=q*H_i-1+c_i для 1<=i<=k, k - длина строки. При q=1 получаем простое сложение символов. Вместо сложения можно выполнять сложение c_i и q*H_j-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.5

6.5. Таблицы на деревьях

Рассмотрим еще один способ организации таблиц с использованием двоичных деревьев. Будем считать, что на множестве идентификаторов задан некоторый линейный порядок (например, лексикографический), т.е. задано некоторое отношение '<', транзитивное, антисимметричное и антирефлексивное. Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставлен идентификатор. Вершина может иметь нуль, одного (правого или левого) или двух (правого и левого) потомков. Если вершина имеет левого потомка, то идентификатор, сопоставленный левому потомку, меньше идентификатора, сопоставленного самой вершине; если имеет правого потомка, то ее идентификатор больше. Элемент таблицы изображен на рис. 6.6.

TP Ident



Left Right

Рис. 6.6

struct 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);
}
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 и дерево перестраивать не надо.

Характеристики

Список файлов лекций