|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[73] Анализ хеширования с цепочками В этом разделе мы оценим время работы операций для хеширования с цепочками. Пусть Г - хеш-таблица с т позициями, в которую занесено га элементов. Коэффициентом заполнения (load factor) таблицы называется число а = п/т (это число может быть и меньше, и больше единицы). Мы будем оценивать стоимость операций в терминах а. В худшем случае хеширование с цепочками ведет себя отвратительно: если хеш-значения всех га ключей совпадают, то таблица сводится к одному списку длины га, и на поиск будет тратиться то же время в (га), что и на поиск в списке, плюс ещё время на вычисление хеш-функции. Конечно, в такой ситуации хеширование бессмысленно. Средняя стоимость поиска зависит от того, насколько равномерно хеш-функция распределяет хеш-значения по позициям таблицы. Вопросу о том, как добиваться этой равномерности, посвящен раздел 12.3; пока же будем условно предполагать, что каждый данный элемент может попасть в любую из тп позиций таблицы с равной вероятностью и независимо от того, куда попал другой элемент. Мы будем называть это предположение гипотезой «равномерного хеширования» (simple uniform hashing). Будем считать, что для данного ключа к вычисление хеш-значения h(k), шаг по списку и сравнение ключей требует фиксированного времени, так что время поиска элемента с ключом к линейно зависит от количества элементов в списке T[h(k)], которые мы просматриваем в процессе поиска. Будем различать два случая: в первом случае поиск оканчивается неудачей (элемента с ключом к в списке нет), во втором поиск успешен - элемент с требуемым ключом обнаруживается. Теорема 12.1. Пусть Т - хеш-таблица с цепочками, имеющая коэффициент заполнения а. Предположим, что хеширование равномерно. Тогда при поиске элемента, отсутствующего в таблице, будет просмотрено в среднем а элементов таблицы, а среднее время такого поиска (включая время на вычисление хеш-функции) будет равно 0(1 + а). Доказательство. Поскольку в предположении равномерного хеширования все позиции таблицы для данного ключа равновероятны, среднее время поиска отсутствующего элемента совпадает со средним временем полного просмотра одного из т списков, то есть пропорционально средней длине наших т списков. Эта средняя длина есть п/т = а, откуда получаем первое утверждение теоремы; второе утверждение получится, если добавить время 0(1) на вычисление хеш-значения.□ Теорема 12.2. При равномерном хешировании среднее время успешного поиска в хеш-таблице с цепочками есть 0(1 + а), где а - коэффициент заполнения. Доказательство. Хотя формулировка этой теоремы похожа на предыдущую, смысл утверждения несколько иной. В предыдущей теореме мы рассматривали произвольную таблицу с коэффициентом заполнения а и оценивали среднее число действий, необходимых для поиска случайного элемента, равновероятно попадающего во все ячейки таблицы. В этой теореме так делать нельзя: если мы возьмём произвольную таблицу и, считая все её элементы равновероятными, будем искать среднее время поиска случайно выбранного из них, то оценки вида 0(1+ а) не получится (контрпример: таблица, в которой все элементы попали в один список) Формулировка подразумевает двойное усреднение: сначала мы рассматриваем случайно выбранную последовательность элементов, добавляемых в таблицу, причём на каждом шаге все значения ключа равновероятны и шаги независимы, а затем в полученной таблице выбираем элемент для поиска, считая все её элементы равновероятными. Посмотрим на ситуацию в тот момент, когда таблица уже построена, но случайный элемент для поиска ещё не выбран. Чему равно среднее время поиска, усреднённое по всем п элементам таблицы? Надо сложить позиции всех элементов в своих списках и поделить сумму на п (общее число элементов). Если представить себе, что при заполнении таблицы элементы дописывались в конец соответствующих списков (см. упр. 12.2-3), то упомянутая сумма по порядку величины равна общему число операций, выполненных при заполнении таблицы (поскольку при добавлении в конец и при поиске выполняется одно и то же количество действий). Теперь вспомним об усреднении по различным возможностям в процессе построения таблицы. При добавлении в неё г-го элемента математическое ожидание числа действий равно 0(1 + [г - 1)/т) (см. доказательство предыдущей теоремы), и потому математическое ожидание общего числа действий при заполнении таблицы, делённое на п, есть e(±£(i + ))=e(i + J-Bi-i>) = у п \ т ) Iу птI \ пт 2 ) = e(1 + i-)=e<1 + 0- □ Если количество позиций в хеш-таблице считать пропорциональным числу элементов в таблице, то из доказанных теорем вытекает, что среднее время на поиск (в оптимистических предположениях о распределении вероятностей) есть 0(1). В самом деле, если п = О (га), то а = п/т = 0(1) и 0(1 + а) = 0(1). Поскольку стоимость добавления в хеш-таблицу с цепочками есть 0(1) (даже при добавлении в конец, см. упр. 12.2-3), а стоимость удаления элемента есть 0(1) (мы считаем, что списки двусторонне связаны), среднее время выполнения любой словарной операции (в предположении равномерного хеширования) есть 0(1). Упражнения 12.2-1 Пусть h - случайная хеш-функция, сопоставляющая с каждым из п различных ключей {к\, к2, , кп} одну из га позиций в таблице. Каково математическое ожидание числа коллизий (точнее, числа пардля которых что h(ki) = h(kj))? 12.2-2 Как будет выглядеть хеш-таблица с цепочками после того, как в неё последовательно поместили элементы с ключами 5,28,19,15,20,33,12,17,10 (в указанном порядке)? Число позиций в таблице равно 9, хеш-функция имеет вид h(k) = к mod 9. 12.2-3 Покажите, что математическое ожидание времени добавления нового элемента (в предположении равномерного хеширования) есть 0(1 + а), если мы добавляем новый элемент в конец соответствующей цепочки. 12.2-4 Профессор предполагает, что хеширование с цепочками будет гораздо эффективнее, если списки элементов с данным хеш-значением будут упорядоченными. Как этот подход повлияет на стоимость успешного поиска, поиска отсутствующего элемента, добавления, удаления? 12.2-5 Разработайте реализацию хеш-таблицы с цепочками, в которой записи хранятся внутри самой хеш-таблицы (неиспользуемые позиции связываются в список свободных мест). Считайте, что в каждой позиции могут храниться либо флаг и два указателя, либо флаг, указатель и элемент. Все словарные операции, а также операции по выделению и освобождению места, должны выполняться за время 0(1). Обязательно ли делать список свободных мест двусторонне связанным? 12.2-6 Пусть общее число возможных ключей (размер множества U) превосходит гага, где га - количество хеш-значений. Покажите, |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||