русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритмизация вычислительных процессов


Дата добавления: 2013-12-23; просмотров: 935; Нарушение авторских прав


Дополнительная литература

Заключение

Хэш-таблицы

 

Хэш-таблицы (hash tables) — одно из величайших изобретений информатики. Сочетание массивов и списков с небольшой добавкой математики позволило создать эффективную структуру для хранения и* получения динамических данных. Типичное применение хэш-таблиц -символьная таблица, которая ассоциирует некоторое значение (данные) с каждым членом динамического набора строк (ключей). Ваш любимый компилятор практически наверняка использует хэш-таблицу для управления информацией о переменных в вашей программе. Ваш web-браузер наверняка использует хэш-таблицу для хранения адресов страниц, которые вы недавно посещали, а при соединении вашего компьютера с Интернетом, вероятно, она применяется для оперативного хранения (cache — кэширования) недавно использованных доменных имен и их IP-адресов.

 

Идея состоит в том, чтобы пропустить ключ через хэш-функцию (hash function) для получения хэш-значения (hash value), которое было бы равномерно распределено по диапазону целых чисел приемлемого размера. Это хэш-значение используется как индекс в таблице, где хранится информация. Java предоставляет стандартный интерфейс к хэш-таб-лицам. В С и C++ обычно с каждым хэш-значением (или "bucket" -"корзиной") ассоциируется список элементов, которые обладают этим значением, как показано на следующем рисунке:

 

 

На практике хэш-функция предопределена, а массив соответствующего размера выделяется нередко даже во время компиляции. Каждый элемент массива — это список, который сцепляет вместе элементы, имеющие общее хэш-значение. Другими словами, хэш-таблица из п элементов — это массив списков, средняя длина которых равна п/'(размер_массива). Получение элемента является константной (О(1)) операцией, если мы взяли хорошую хэш-функцию и списки не становятся слишком большими.



 

Поскольку хэш-таблица — массив списков, то тип элементов для нее такой же, как и для списка:

 

typedef struct Nameval

Nameval; struct Nameval {

char *name;

int value;

Nameval *next; /* следующий в цепи */ };

Nameval *symtab[NHASH]; /*

таблица символов */

Способы работы со списками из раздела 2.7 можно использовать для управления отдельными хэш-цепочками. Как только у вас есть хорошая хэш-функция, все становится легко: получаете цепочку и дальше спокойно проходите вдоль списка, ища подходящий элемент. Приведем текст процедуры поиска/вставки в хэш-таблицу. Если элемент найден, то он возвращается. Если элемент не найден и задан флаг создания create, то lookup добавляет элемент в таблицу. Копия имени символа не создается — считается, что вызывающая сторона сама сделала себе надежную копию.

 

 

/* lookup: поиск имени в таблице;

возможна вставка */ Nameval* lookup

(char *name, int create, int value)

{

int h;

Nameval *sym;

h = hash(name);

for (sym =-symtab[h];

sym != NULL; sym = sym->next)

if (strcmp(name, sym->name) == 0)

return sym; if (create) {

sym = (Nameval *)

emalloc(sizeof(Nameval));

 

 

sym->name = name; /*

считаем, что память

уже выделена */ sym->value = value;

sym->next = symtab[h]; symtab[h] = sym;

}

return sym;

}

Поиск и возможная вставка комбинируются часто. Иначе приходится прилагать лишние усилия. Если писать

if (lookup("name") == NULL)

additem(newitem("name", value));

 

то хэш-функция вычисляется дважды.

 

Насколько большим должен быть массив? Основная идея заключается в том, что он должен быть достаточно большим, чтобы любая хэш-цепочка была бы длиной всего в несколько элементов и поиск занимал время О(1). Например, у компилятора размер массива должен быть порядка нескольких тысяч, так как в большом исходном файле — несколько тысяч строчек и вряд ли различных идентификаторов имеется больше, чем по одному на строчку кода.

 

Теперь нам нужно решить, что же наша хэш-функция, hash, будет вычислять. Она должна быть детерминированной, достаточно быстрой и распределять данные по массиву равномерно. Один из наиболее распространенных алгоритмов хэширования для строк получает хэш-значение, добавляя каждый байт строки к произведению предыдущего значения на некий фиксированный множитель (хэш). Умножение распределяет биты из нового байта по всему до сих пор не считанному значению, так что в конце цикла мы получим хорошую смесь входных байтов. Эмпирически установлено, что значения 31 и 37 являются хорошими множителями в хэш-функции для строк ASCII.

enum { MULTIPLIER = 31 };

/* hash: вычислить

хэш-функцию строки */

unsigned int hash(char *str)

{

unsigned int h;

unsigned char *p;

 

 

h = 0;

for (p = (unsigned char *)

str; *p != '\0'; p++)

h = MULTIPLIER * h +

*p; return h % NHASH; }

В вычислениях символы принимаются неотрицательными принудительно (тем, что используется тип unsigned char), так как ни в С, ни в C++ наличие знака у символов не регламентировано, а мы хотим, чтобы наша хэш-функция оставалась положительной.

 

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

 

Эксперименты показывают, что для большого числа разных строк трудно придумать хэш-функцию, которая работала бы гораздо лучше, чем эта, зато легко придумать такую, которая работает хуже. В ранних версиях Java была хэш-функция для строк, работавшая более эффективно, если строка была длинной. Хэш-функция работала быстрее, анализируя только 8 или 9 символов через равные интервалы в строках длиннее, чем 16 символов, начиная с первого символа. К сожалению, хотя хэш-функция работала быстрее, у нее были очень плохие статистические показатели, что сводило на нет выигрыш в производительности. Пропуская части строки, она нередко выкидывала именно различающиеся части строк. Имена файлов начинаются с длинных идентичных префиксов — имен каталогов — и могут отличаться только несколькими последними символами (например, .Java и .class). Адреса в Internet обычно начинаются с http://www. и заканчиваются на . html, поэтому все различия у них в середине. Хэш-функция частенько проходила только по неразличающейся части в имени, в результате чего образовывались более длинные хэш-цепочки, что замедляло поиск. Проблема была решена заменой хэш-функции на эквивалентную той, что мы привели выше (с мультипликатором 37), которая исследует каждый символ в строке.

 

Хэш-функция, которая неплохо подходит для одного набора данных (например, имен переменных), может плохо подходить для другого (адреса Internet), так что потенциальная хэш-функция должна быть протестирована на разных наборах типичных входных данных. Хорошо ли она перемешивает короткие строки? Длинные строки? Строки одинаковой длины с небольшими изменениями?

 

Хэшировать можно не только строки. Можно "смешать" три координаты частицы при физическом моделировании, тем самым уменьшив размер хранилища до линейной таблицы (0(количество точек)) вместо трехмерного массива (0(размер_по_х хразмер_nojj X размер_no_z)).

 

Один примечательный случай использования хэширования — программа Джерарда Холзманна (Gerard Holzmann) для анализа протоколов и параллельных систем Supertrace. Supertrace берет полную информацию о каждом возможном состоянии наблюдаемой системы и хэширует эту информацию для получения адреса единственного бита в памяти. Если этот бит установлен, то данное состояние наблюдалось и раньше; если нет, то не наблюдалось. В Supertrace используется хэш-таблица длиной во много мегабайт, однако в каждой ячейке хранится только один бит. Цепочки не строятся; если два разных состояния совпали по своей хэш-функции, то программа этого не заметит. Supertrace рассчитана на то, что вероятность коллизии мала (она не обязана быть нулем, поскольку Supertrace использует вероятностные, а не детерминированные вычисления). Поэтому хэш-функция здесь очень аккуратна; она использует циклический избыточный код (cyclic redundancy check — CRC) — функцию, которая тщательно перемешивает данные.

 

Хэш-таблицы незаменимы для символьных таблиц, поскольку они предоставляют (почти всегда) доступ к каждому элементу за константное время. У них есть свои ограничения. Если хэш-функция плоха или размер массива слишком мал, то списки могут стать достаточно длинными. Поскольку списки не отсортированы, это приведет к линейному доступу (0(и)). Элементы нельзя напрямую получить в отсортированном виде, однако их легко подсчитать, выделить память под массив, заполнить его указателями на элементы и отсортировать их. Что и говорить, константное время операций поиска, вставка и удаление — это такое свойство хэш-таблицы, которого не достичь никакими другими технологиями.

 

Упражнение 2-14

 

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

 

Упражнение 2-15

 

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

 

Упражнение 2-16

 

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

 

Упражнение 2-17

 

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

 

 

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

 

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

 

У каждой операции есть ожидаемое время выполнения, которое часто определяет, насколько выбранный тип данных или его реализация подходит для конкретного приложения. Массивы предоставляют доступ к элементам за константное время, но зато плохо изменяют свои размер; Списки хорошо приспособлены для вставки и удаления, но случайный доступ к элементам происходит лишь за линейное время. Деревья и хэш-таблицы предоставляют разумный компромисс: быстрый доступ к заданным элементам в сочетании с легкой расширяемостью, пока в их структуре соблюдается определенный баланс.

 

 

 

  1. Серия книг "Алгоритмы" Боба Седжвика (Bob Sedgewick. Algorithms. Addison-Wesley) содержит доступные сведения о большом числе полезных алгоритмов. В третьем издании "Алгоритмов на C++" (Algorithms in C++, 1998) идет неплохое обсуждение хэш-функций и размеров хэш-таблиц. "Искусство программирования" Дона Кнута (Don Knuth. The Art of Computer Programming. Addison-Wesley) — первейший источник для строгого анализа многих алгоритмов; в третьем томе (2nd ed., 19981) рассматриваются поиск и сортировка.

 

  1. Программа Supertrace описана в книге Джерарда Холзманна "Дизайн и проверка протоколов" (Gerard Holzmann. Design and Validation of Computer Protocols. Prentice Hall, 1991).

 

  1. Ион Бентли и Дуг Мак-Илрой описывают создание скоростной и устойчивой версии быстрой сортировки в статье "Конструирование функции сортировки" (Jon Bentley, Doug Mcllroy. Engineering a sort function. Software - Practice and Experience, 23, 1, p. 1249-1265, 1993).


<== предыдущая лекция | следующая лекция ==>
Деревья | Алгоритм и его свойства


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.009 сек.