Тема № 2 Организация таблиц идентификаторов_КР1.ppt

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ТК
Тема:

Организация таблиц идентификаторов

и генерация кода требуют знания характеристик переменных, констант, функций и

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

Состав возможных характеристик
и методы их определения зависят
от семантики входного языка.

это специальным образом организованные наборы данных, служащие для хранения информации

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

Состав информации, хранимой в ТИ для каждого элемента исходной программы, зависит от семантики входного языка и типа элемента.


Например, в ТИ может храниться следующая информация:

Таблица идентификаторов заполняется не сразу.
Компилятор может несколько раз выполнять обращение
к данным в ТИ на различных фазах компиляции.

на различных фазах компиляции он вынужден многократно обращаться к

ней

для поиска информации
и записи новых данных

Назначение и особенности построения таблиц идентификаторов

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

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

Основным критерием
при выборе метода организации ТИ
является время поиска нужного элемента.

количестве элементов n

(поскольку при поиске будет в среднем выполнено n/2 сравнений )

за счет

увеличения времени помещения нового элемента
(максимальное число сравнений 1 + log2 n)

Недостатки: требование упорядочивания ТИ

K1, A22, B1, M, P3, L

Форма бинарного дерева зависит
от порядка поступления идентификаторов.

- необходимость хранения двух дополнительных ссылок (на

левую и правую ветви) в каждом элементе дерева

- работа с динамическим выделением памяти при построении
дерева

в таблице.
простой хеш-функцией является
внутреннее представление первой литеры символа
Например,

если двоичное ASCII представление символа А есть 00100001,
то результатом хеширования идентификатора ATable будет код 00100001.

Хеш-функцией (происходит от английского «hash function» – «функция смешивания») F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел:
Z:F(r)=n, где r∈R, n∈Z.

Процесс отображения области определения хеш-функции на множество значений называется «хешированием».

При работе с ТИ хеш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел.
Областью определения хеш-функции является множество всех возможных имен идентификаторов.

качестве адреса ячейки из некоторого массива данных.
Размер массива данных

должен соответствовать области значений используемой хеш-функции.

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

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

ТИ

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

Недостатки: - неэффективное использование объема памяти под ТИ (размер
массива для ее хранения должен соответствовать области
значений хеш-функции, в то время как реально хранимых в таблице
идентификаторов может быть существенно меньше, и наоборот,
если выбрана неудачная хеш-функция – может не хватить места для
размещения всех идентификаторов);
- необходимость соответствующего разумного выбора хеш-
функции (при неудовлетворительном выборе хеш-функции может
возникнуть такая ситуация, когда двум и более идентификаторам
будет соответствовать одно и то же значение хеш-функции, что
влечет за собой попытку размещения в одной и той же ячейке ТИ
обоих идентификаторов, что явно невозможно.
Такая ситуация называется коллизией).

ограничения:
- в реальности область значений любой хеш-функции ограничена размером доступного

адресного пространства в данной архитектуре компьютера. При организации хеш-адресации значение, используемое в качестве адреса ТИ, не может выходить за пределы, заданные разрядностью адреса компьютера;

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

формуле:


где A – идентификатор,

h(A) – хеш-функция,

hi(A) – новая хеш-функция,

pi – некоторое вычисляемое целое число,

Nm – максимальное значение из области значений хеш-функции h
(берется остаток от деления на максимальное значение из области
хеш-функции для того, чтобы не выйти за пределы ТИ)

hi(A) = (h(A) + pi) mod Nm,

Nm,
Недостаток: при совпадении хеш-адресов элементы в таблице начинают группироваться вокруг

них, что увеличивает число необходимых сравнений при поиске и размещении.

Достоинства: эффективен при неполном заполнении таблицы

Пример: Идентификаторы поступают в следующем порядке:
ab, ac, an, ak, bc, az, ck.

Максимальное значение ХФ Nm=13 (следовательно, под ТИ будет выделен
объем памяти, равный 13).

Используемая ХФ – ASCII-код первой буквы идентификатора.

h(ab)=h(ac)=h(an)=h(ak)=h(az)=d7

h(bc)=d3

h(ck)=d9

с адресом d7

h(ab)= d7
(для размещения данного идентификатора необходимо сделать 1 операцию)

ab

Шаг 1

Идентификаторы поступают в следующем порядке:
ab, ac, an, ak, bc, az, ck.

Шаг 2: При размещения идентификатора ac возникает коллизия:
h(ac)= d7, поскольку ячейка занята,
согласно формуле рехеширования, вычисляется новая ХФ:
h1(ac)=(h(ac)+1)mod13=d8
(для размещения данного идентификатора необходимо сделать 2 операции)

ac

Шаг 2

Шаг 3: При размещения идентификатора an возникает коллизия:
h(an)= d7, поскольку ячейка занята,
согласно формуле рехеширования, вычисляется новая ХФ:
h1(an)=(h(an)+1)mod13=d8 – снова коллизия
h2(an)=(h(an)+2)mod13=d9
(для размещения данного идентификатора необходимо сделать 3 операции)

an

Шаг 3

Шаг 4: При размещения идентификатора ak возникает коллизия:
h(ak)= d7, поскольку ячейка занята,
согласно формуле рехеширования, вычисляется новая ХФ:
h1(ak)=(h(ak)+1)mod13=d8 – снова коллизия
h2(ak)=(h(ak)+2)mod13=d9 – снова коллизия
h3(ak)=(h(ak)+3)mod13=d10
(для размещения данного идентификатора необходимо сделать 4 операции)

ak

Шаг 4

Шаг 5: Идентификатор bс размещается в ячейку с адресом d3
h(bс)= d3
(для размещения данного идентификатора необходимо сделать 1 операцию)

bс

Шаг 5

Шаг 6: При размещения идентификатора az возникает коллизия:
h(az)= d7, поскольку ячейка занята,
согласно формуле рехеширования, вычисляется новая ХФ:
h1(az)=(h(az)+1)mod13=d8 – снова коллизия
h2(az)=(h(az)+2)mod13=d9 – снова коллизия
h3(az)=(h(az)+3)mod13=d10 – снова коллизия
h4(az)=(h(az)+4)mod13=d11
(для размещения данного идентификатора необходимо сделать 5 операций)

az

Шаг 6

Шаг 7: При размещения идентификатора ck возникает коллизия, так как ячейка d9 уже занята:
h(ck)= d9,
следовательно, согласно формуле рехеширования, вычисляется новая ХФ:
h1(ck)=(h(ck)+1)mod13=d10 – снова коллизия
h2(ck)=(h(ck)+2)mod13=d11 – снова коллизия
h3(ck)=(h(ck)+3)mod13=d12
(для размещения данного идентификатора необходимо сделать 4 операции)

ck

Шаг 7

(h(A) + pi) mod Nm,

последовательность псевдослучайных

целых чисел p1, p2, …, pk.

Метод рехеширование с помощью произведения

hi(A) = (h(A) * i) mod Nm,

рассмотренными методами, но эффективность напрямую зависит:

-

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

- качества используемой хеш-функции (чем реже коллизии, тем выше эффективность).


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

Рехеширование

для каждого возможного значения хеш-функции, а сделать ее динамической так,

чтобы ее объем рос по мере заполнения (первоначально ТИ не содержит ни одной ячейки, а все ячейки ХТ имеют пустое значение).

(делается только для ХТ);

- каждому идентификатору соответствует строго одна ячейка в ТИ, поскольку в ней нет пустых неиспользуемых ячеек (пустые ячейки есть только в ХТ, и объем неиспользуемой памяти не зависит от объема информации, хранимой для каждого идентификатора, то есть для каждого значения хеш-функции расходуется только память, необходимая для хранения одного указателя на основную ТИ).

Метод цепочек

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

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

В результате в ТИ возникают своеобразные цепочки связанных элементов (отсюда и название – «метод цепочек»).

ab, ac, an, ak, bc, az, ck.
Максимальное значение ХФ Nm=13
(следовательно, под ХТ будет
выделен объем памяти, равный 13).

Используемая ХФ – ASCII-код
первой буквы идентификатора.

h(ab)=h(ac)=h(an)=h(ak)=h(az)=d7

h(bc)=d3

h(ck)=d9

a1

a5

a7

Среднее время на размещение одного элемента и на поиск элемента

зависит только от среднего числа коллизий, возникающих при вычислении хеш-функции.

Накладные расходы памяти, связанные с необходимостью иметь одно дополнительное поле указателя в ТИ на каждый ее элемент, можно признать вполне оправданными.

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

методы, как и в методе цепочек в ТИ используется специальное

дополнительное поле ссылки, которое имеет несколько иное значение.

для выборки информации из ТИ используется хеш-функция и поле ссылки остается пустым

через поле ссылки организуется поиск идентификаторов, для которых значения хеш-функции совпадают, по одному из рассмотренных выше методов

Недостатком же метода является необходимость работы с динамически распределяемыми областями памяти.

Коллизия

Нет коллизий

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

Эффективность данного метода
зависит от качества применяемой
хеш-функции и от метода организации
дополнительных хранилищ данных.

m=d6, n=d1, z=d8