Алексей Молчанов.

Системное программное обеспечение. Лабораторный практикум

(страница 3 из 27)

скачать книгу бесплатно

   Как и для метода цепочек, для комбинированных методов время размещения и время поиска элемента в таблице идентификаторов зависит только от среднего числа коллизий, возникающих при вычислении хэш-функции. Накладные расходы памяти при использовании промежуточной хэш-таблицы минимальны.
   Очевидно, что если в качестве дополнительного метода использовать простой список, то получится алгоритм, полностью аналогичный методу цепочек. Если же использовать упорядоченный список или бинарное дерево, то метод цепочек и комбинированные методы будут иметь примерно равную эффективность при незначительном числе коллизий (единичные случаи), но с ростом количества коллизий эффективность комбинированных методов по сравнению с методом цепочек будет возрастать.
   Недостатком комбинированных методов является более сложная организация алгоритмов поиска и размещения идентификаторов, необходимость работы с динамически распределяемыми областями памяти, а также бóльшие затраты времени на размещение нового элемента в таблице идентификаторов по сравнению с методом цепочек.
   То, какой конкретно метод применяется в компиляторе для организации таблиц идентификаторов, зависит от реализации компилятора. Один и тот же компилятор может иметь даже несколько разных таблиц идентификаторов, организованных на основе различных методов. Как правило, применяются комбинированные методы.
   Создание эффективной хэш-функции – это отдельная задача разработчиков компиляторов, и полученные результаты, как правило, держатся в секрете. Хорошая хэш-функция распределяет поступающие на ее вход идентификаторы равномерно на все имеющиеся в распоряжении адреса, чтобы свести к минимуму количество коллизий. В настоящее время существует множество хэш-функций, но, как было показано выше, идеального хэширования достичь невозможно.
   Хэш-адресация – это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных [5, 6, 11].



   Во всех вариантах задания требуется разработать программу, которая может обеспечить сравнение двух способов организации таблицы идентификаторов с помощью хэш-адресации. Для сравнения предлагаются способы, основанные на использовании рехэширования или комбинированных методов. Программа должна считывать идентификаторы из входного файла, размещать их в таблицах с помощью заданных методов и выполнять поиск указанных идентификаторов по требованию пользователя. В процессе размещения и поиска идентификаторов в таблицах программа должна подсчитывать среднее число выполненных операций сравнения для сопоставления эффективности используемых методов.
   Для организации таблиц предлагается использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно.
Хэш-функция должна обеспечивать работу не менее чем с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается использовать в работе хэш-функции, взятые из примера выполнения работы.
   Лабораторная работа должна выполняться в следующем порядке:
   1. Получить вариант задания у преподавателя.
   2. Выбрать и описать хэш-функцию.
   3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.
   4. Подготовить и защитить отчет.
   5. Написать и отладить программу на ЭВМ.
   6. Сдать работающую программу преподавателю.


   Отчет по лабораторной работе должен содержать следующие разделы:
   • задание по лабораторной работе;
   • описание выбранной хэш-функции;
   • схемы организации таблиц идентификаторов (в соответствии с вариантом задания);
   • описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);
   • текст программы (оформляется после выполнения программы на ЭВМ);
   • результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, указанных в варианте задания;
   • анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе.


   • Что такое таблица символов и для чего она предназначена? Какая информация может храниться в таблице символов?
   • Какие цели преследуются при организации таблицы символов?
   • Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?
   • Какие существуют способы организации таблиц символов?
   • В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?
   • Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?
   • Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?
   • Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?
   • Что такое рехэширование? Какие методы рехэширования существуют?
   • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и рехэширования.
   • В чем заключается метод цепочек?
   • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.
   • Как могут быть скомбинированы различные методы организации хеш-таблиц?
   • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью комбинированных методов.



   В табл. 1.1 перечислены методы организации таблиц идентификаторов, используемые в заданиях.
 //-- Таблица 1.1. Методы организации таблиц идентификаторов --// 

   В табл. 1.2 даны варианты заданий на основе методов организации таблиц идентификаторов, перечисленных в табл. 1.1.
 //-- Таблица 1.2. Варианты заданий --// 


   В качестве примера выполнения лабораторной работы возьмем сопоставление двух методов: хэш-адресации с рехэшированием на основе псевдослучайных чисел и комбинации хэш-адресации с бинарным деревом. Если обратиться к приведенной выше табл. 1.1, то такой вариант задания будет соответствовать комбинации методов 2 и 7 (в табл. 1.2 среди вариантов заданий такая комбинация отсутствует).


   Для хэш-адресации с рехэшированием в качестве хэш-функции возьмем функцию, которая будет получать на входе строку, а в результате выдавать сумму кодов первого, среднего и последнего элементов строки. Причем если строка содержит менее трех символов, то один и тот же символ будет взят и в качестве первого, и в качестве среднего, и в качестве последнего.
   Будем считать, что прописные и строчные буквы в идентификаторах различны. [2 - Программные модули, реализующие таблицы символов, построены таким образом, что в зависимости от условий компиляции они могут либо различать, либо не различать прописные и строчные буквы. Условие компиляции реализовано через макрокоманды компилятора Delphi 5 в функции Upper в модуле TblElem (листинг П3.1, приложение 3). О принципах, на основе которых выполняются макрокоманды и условная компиляция, можно подробно узнать в [7, 13, 23, 25, 28, 32].] В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows. Тогда, если положить, что строка из области определения хэш-функции содержит только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «0», а максимальным значением – сумма трех кодов литеры «z».
   Таким образом, область значений выбранной хэш-функции в терминах языка Object Pascal может быть описана как:
   (Ord(0 )+Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z')+Ord('z'))

   Диапазон области значений составляет 223 элемента, что удовлетворяет требованиям задания (не менее 200 элементов). Длина входных идентификаторов в данном случае ничем не ограничена. Для удобства пользования опишем две константы, задающие границы области значений хэш-функции:
   HASH_MIN = Ord(0 )+Ord(0 )+Ord(0 );
   HASH_MAX = Ord('z')+Ord('z')+Ord('z').

   Сама хэш-функция без учета рехэширования будет вычислять следующее выражение:
   Ord(sName[1]) + Ord(sName[(Length(sName)+1) div 2]) + Ord(sName[Length(sName);
   здесь sName – это входная строка (аргумент хэш-функции).

   Для рехэширования возьмем простейший генератор последовательности псевдослучайных чисел, построенный на основе формулы F = i-H -------
| bookZ.ru collection
|-------
|  
 -------


mod Н -------
| bookZ.ru collection
|-------
|  
 -------


, где Н -------
| bookZ.ru collection
|-------
|  
 -------


и Н -------
| bookZ.ru collection
|-------
|  
 -------


– простые числа, выбранные таким образом, чтобы H -------
| bookZ.ru collection
|-------
|  
 -------


было в диапазоне от Н -------
| bookZ.ru collection
|-------
|  
 -------


/2 до Н -------
| bookZ.ru collection
|-------
|  
 -------


. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от HASH_MIN до HASH_MAX, Н -------
| bookZ.ru collection
|-------
|  
 -------


должно быть максимально близко к величине HASH_MAX – HASН_МIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 – простое число, то возьмем Н -------
| bookZ.ru collection
|-------
|  
 -------


= 223 (если бы размер диапазона не был простым числом, то в качестве Н -------
| bookZ.ru collection
|-------
|  
 -------


нужно было бы взять ближайшее к нему меньшее простое число). В качестве H -------
| bookZ.ru collection
|-------
|  
 -------


возьмем 127: H -------
| bookZ.ru collection
|-------
|  
 -------


= 127.
   Опишем соответствующие константы:
   REHASH1 = 127;
   REHASH2 = 223;

   Тогда хэш-функция с учетом рехэширования будет иметь следующий вид:
    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



   Входные параметры этой функции: sName – имя хэшируемого идентификатора, iNum – индекс рехэшированиея (если iNum = 0, то рехэширование отсутствует). Строка проверки величины результата (Result < HASH_MIN) добавлена, чтобы исключить ошибки в тех случаях, когда на вход функции подается строка, содержащая символы вне диапазона 0 ..'z' (поскольку контроль входных идентификаторов отсутствует, это имеет смысл).
   Для комбинации хэш-адресации и бинарного дерева можно использовать более простую хэш-функцию – сумму кодов первого и среднего символов входной строки. Диапазон значений такой хэш-функции в терминах языка Object Pascal будет выглядеть так:
   (Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z'))
   Этот диапазон содержит менее 200 элементов, однако функция будет удовлетворять требованиям задания, так как в комбинации с бинарным деревом она будет обеспечивать обработку неограниченного количества идентификаторов (максимальное количество идентификаторов будет ограничено только объемом доступной оперативной памяти компьютера).
   Без применения рехэширования эта хэш-функция будет выглядеть значительно проще, чем описанная выше хэш-функция с учетом рехэширования:
    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------





   В первую очередь необходимо описать структуру данных, которая будет использована для хранения информации об идентификаторах в таблицах идентификаторов. Для обеих таблиц (с рехэшированием на основе генератора псевдослучайных чисел и в комбинации с бинарным деревом) будем использовать одну и ту же структуру. В этом случае в таблицах будут храниться неиспользуемые данные, но программный код будет проще. В качестве учебного примера такой подход оправдан.
   Структура данных таблицы идентификаторов (назовем ее TVarInfo) должна содержать в обязательном порядке поле имени идентификатора (поле sName: string), а также поля дополнительной информации об идентификаторе по усмотрению разработчиков компилятора. В лабораторной работе не предусмотрено хранение какой-либо дополнительной информации об идентификаторах, поэтому в качестве иллюстрации информационного поля включим в структуру TVarInfo дополнительную информационную структуру TAddVarInfo (поле pInfo: TAddVarInfo).
   Поскольку в языке Object Pascal для полей и переменных, описанных как class, хранятся только ссылки на соответствующую структуру, такой подход не приведет к значительным расходам памяти, но позволит в будущем хранить любую информацию, связанную с идентификатором, в отдельной структуре данных (поскольку предполагается использовать создаваемые программные модули в последующих лабораторных работах). В данном случае другой подход невозможен, так как заранее не известно, какие данные необходимо будет хранить в таблицах идентификаторов. Но разработчик реального компилятора, как правило, знает, какую информацию требуется хранить, и может использовать другой подход – непосредственно включить все необходимые поля в структуру данных таблицы идентификаторов (в данном случае – в структуру TVarInfo) без использования промежуточных структур данных и ссылок.
   Первый подход, реализованный в данном примере, обеспечивает более экономное использование оперативной памяти, но является более сложным и требует работы с динамическими структурами, второй подход более прост в реализации, но менее экономно использует память. Какой из двух подходов выбрать, решает разработчик компилятора в каждом конкретном случае (второй подход будет проиллюстрирован позже в примере к лабораторной работе № 4).
   Для работы со структурой данных TVarInfo потребуются следующие функции:
   • функции создания структуры данных и освобождения занимаемой памяти – реализованы как constructor Create и destructor Destroy;
   • функции доступа к дополнительной информации – в данной реализации это procedure SetInfo и procedure ClearInfo.
   Эти функции будут общими для таблицы идентификаторов с рехэшированием и для комбинированной таблицы идентификаторов.
   Однако для комбинированной таблицы идентификаторов в структуру данных TVarInfo потребуется также включить дополнительные поля данных и функции, обеспечивающие организацию бинарного дерева:
   • ссылки на левую («меньшую») и правую («большую») ветвь дерева – реализованы как поля данных minEl, maxEl: TVarInfo;
   • функции добавления элемента в дерево – function AddElCnt и function AddElem;
   • функции поиска элемента в дереве – function FindElCnt и function FindElem;
   • функция очистки информационных полей во всем дереве – procedure ClearAllInfo;
   • функция вывода содержимого бинарного дерева в одну строку (для получения списка всех идентификаторов) – function GetElList.
   Функции поиска и размещения элемента в дереве реализованы в двух экземплярах, так как одна из них выполняет подсчет количества сравнений, а другая – нет.
   Поскольку на функции и процедуры не расходуется оперативная память, в результате получилось, что при использовании одной и той же структуры данных для разных таблиц идентификаторов в таблице с рехэшированием будет расходоваться неиспользуемая память только на хранение двух лишних ссылок (minEl и maxEl).
   Полностью вся структура данных TVarInfo и связанные с ней процедуры и функции описаны в программном модуле TblElem. Полный текст этого программного модуля приведен в листинге П3.1 в приложении 3.
   Надо обратить внимание на один важный момент в реализации функции поиска идентификатора в дереве (function TVarInfo.FindElCnt). Если выполнять сравнение двух строк (в данном случае – имени искомого идентификатора sN и имени идентификатора в текущем узле дерева sName) с помощью стандартных методов сравнения строк языка Object Pascal, то фрагмент программного кода выглядел бы примерно так:
    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



   В этом фрагменте сравнение строк выполняется дважды: сначала проверяется отношение «меньше» (sN < sName), а потом – «больше» (sN > sName). И хотя в программном коде явно это не указано, для каждого из этих операторов будет вызвана библиотечная функция сравнения строк (то есть операция сравнения может выполниться дважды!). Чтобы этого избежать, в реализации предложенной в примере выполняется явный вызов функции сравнения строк, а потом обрабатывается полученный результат:
    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



    -------
| bookZ.ru collection
|-------
|  
 -------



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


   Таблицы идентификаторов реализованы в виде статических массивов размером HASH_MIN..HASH_MAX, элементами которых являются структуры данных типа TVarInfo. В языке Object Pascal, как было сказано выше, для структур таких типов хранятся ссылки. Поэтому для обозначения пустых ячеек в таблицах идентификаторов будет использоваться пустая ссылка – nil.
   Поскольку в памяти хранятся ссылки, описанные массивы будут играть роль хэш-таблиц, ссылки из которых указывают непосредственно на информацию в таблицах идентификаторов.
   На рис. 1.3 показаны условные схемы, наглядно иллюстрирующие организацию таблиц идентификаторов. Схема 1 иллюстрирует таблицу идентификаторов с рехэшированием на основе генератора псевдослучайных чисел, схема 2 – таблицу идентификаторов на основе комбинации хэш-адресации с бинарным деревом. Ячейки с надписью «nil» соответствуют незаполненным ячейкам хэш-таблицы.
   Рис. 1.3. Схемы организации таблиц идентификаторов.

   Для каждой таблицы идентификаторов реализованы следующие функции:
   • функции начальной инициализации хэш-таблицы – InitTreeVar и InitHashVar;
   • функции освобождения памяти хэш-таблицы – ClearTreeVar и ClearHashVar;
   • функции удаления дополнительной информации в таблице – ClearTreeInfo и ClearHashInfo;
   • функции добавления элемента в таблицу идентификаторов – AddTreeVar и AddHashVar;
   • функции поиска элемента в таблице идентификаторов – GetTreeVar и GetHashVar;
   • функции, возвращающие количество выполненных операций сравнения при размещении или поиске элемента в таблице – GetTreeCount и GetHashCount.


скачать книгу бесплатно

страницы: 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

Поделиться ссылкой на выделенное