|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[72] шем случае: 12.1-2 Битовый вектор (bit vector) - это массив битов (нулей и единиц). Битовый вектор длины т занимает значительно меньше места, чем массив из т указателей. Как, пользуясь битовым вектором, реализовать динамическое множество, состоящее из различных элементов и не содержащее дополнительных данных? Словарные операции должны выполняться за время 0(1). 12.1-3 Как реализовать таблицу с прямой адресацией, в которой ключи различных элементов могут совпадать, а сами элементы могут содержать дополнительные данные? Операции добавления, удаления и поиска должны выполняться за время 0(1) (не забудьте, что аргументом процедуры удаления Delete является указатель на удаляемый элемент, а не ключ). 12.1-4* Предположим, что нам надо реализовать динамическое множество, поддерживающее словарные операции, на базе очень большого массива. Первоначально в массиве может быть записано что-то, не имеющее отношение к нашей задаче, но массив такой большой, что предварительно очищать его непрактично. Как в таких условиях реализовать таблицу с прямой адресацией? Каждая запись должна занимать место размером 0(1), операции добавления, удаления и поиска должны выполняться за время 0(1), время на инициализацию структуры данных также должно быть равно 0(1). (Указание: чтобы иметь возможность узнать, имеет ли данный элемент массива отношение к нашей структуре данных, заведите стек, размер которого равен количеству записей в таблице). 12.2. Хеш-таблицы Прямая адресация обладает очевидным недостатком: если множество U всевозможных ключей велико, то хранить в памяти массив Г размером \U\ непрактично, а то и невозможно. Кроме того, если число реально присутствующих в таблице записей мало по сравнению с £/, то много памяти тратится зря. Если количество записей в таблице существенно меньше, чем количество всевозможных ключей, то хеш-таблица занимает гораздо меньше места, чем таблица с прямой адресацией. Именно, хеш-таблица требует памяти объёмом 0(/i), где К - множество записей, при этом время поиска в хеш-таблице по-прежнему есть 0(1) (единственное «но» в том, что на сей раз это - оценка в среднем, а не в худшем случае, да и то только при определённых предположениях). В то время как при прямой адресации элементу с ключом к отво- Переводы надписей на самой картинке: universe of keys - всевозможные ключи, actual keys - используемые ключи Рис. 12.2 Использование хеш-функции для отображения ключей в позиции хеш-таблицы. Хеш-значения ключей &2 и къ совпадают - имеет место коллизия. дится позиция номер к, при хешировании этот элемент записывается в позицию номер h(k) в хеш-таблице (hash table) Г[0 . .т - 1], где h: U {0,1,...,то- 1} - некоторая функция, называемая хеш-функцией (hash function). Число h(к) называют хеш-значением (hash value) ключа к. Идея хеширования показана на рис. 12.2: пользуясь массивом длины то, а не \U\, мы экономим память. Проблема, однако, в том, что хеш-значения двух разных ключей могут совпасть. В таких случаях говорят, что случилась коллизия, или столкновение (collision). К счастью, эта проблема разрешима: хеш-функциями можно пользоваться и при наличии столкновений. Хотелось бы выбрать хеш-функцию так, чтобы коллизии были невозможны. Но при \U\ > то неизбежно существуют разные ключи, имеющие одно и то же хеш-значение. Так что можно лишь надеяться, что для фактически присутствующих в множестве ключей коллизий будет немного, и быть готовыми обрабатывать те коллизии, которые всё-таки произойдут. Выбирая хеш-функцию, мы обычно не знаем заранее, какие именно ключи будут храниться. Но на всякий случай разумно сделать сделать хеш-функцию в каком-то смысле «случайной», хорошо перемешивающей ключи по ячейкам (английский глагол "to hash" означает «мелко порубить, помешивая»). Разумеется, «случайная» хеш-функция должна всё же быть детерминированной в том смысле, что при ее повторных вызовах с одним и тем же аргументом она должна возвращать одно и то же хеш-значение. В этом разделе мы рассмотрим простейший способ обработки (как говорят, «разрешения») коллизий с помощью цепочек. Другой способ - открытая адресация - рассматривается в разделе 12.4. Переводы надписей на самой картинке: universe of keys - всевозможные ключи, actual keys - используемые ключи Рис. 12.3 Разрешение коллизий с помощью цепочек. В позиции T[j] хранится указатель на список элементов с хеш-значением j. Например, h(ki) = h(k$) и h(k5)=h(k2) = h(k7). Разрешение коллизий с помощью цепочек Технология сцепления элементов (chaining) состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список (рис. 12.3). В позиции номер j хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно j; если таких элементов в множестве нет, в позиции j записан nil. Операции добавления, поиска и удаления реализуются легко: Chained-Hash-Insert(T, ж) добавить ж в голову списка T[h(key[x])] Chained-Hash-Search(T, к) найти элемент с ключом к в списке T[h(k)] Chained-Hash-Delete(T, ж) удалить ж из списка T[h(key[x])] Операция добавления работает в худшем случае за время 0(1). Максимальное время работы операции поиска пропорционально длине списка (ниже мы рассмотрим этот вопрос подробнее). Наконец, удаление элемента можно провести за время 0(1) - при условии, что списки двусторонне связаны (если списки связаны односторонне, то для удаления элемента ж надо предварительно найти его предшественника, для чего необходим поиск по списку; в таком случае стоимость удаления и поиска примерно одинаковы). |
Среды: 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 | ||