|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[8] Рис. 0.8:Устройство разделенного списка Реализация Реализация работы с разделенными списками на Си находится в разделе 4.8. Операторы typedef T, а также compLT и compEQ следует изменить так, чтобы они соответствовали данным, хранимым в узлах списка. Кроме того, понадобится выбрать константу MAXLEVEL; ее значение выбирается в зависимости от ожидаемого объема данных. Функция initList вызывается в самом начале. Она отводит память под заголовок списка и инициализирует его поля. Признаком того, что список пуст, Функция insertNode создает новый узел и вставляет его в список. Конечно, insertNode сначала отыскивает место в списке, куда узел должен быть вставлен. В массиве update функция учитывает встретившиеся ссылки на узлы верхних уровней. Эта информация в дальнейшем используется для корректной установки ссылок нового узла. Для этого узла, с помощью генератора случайных чисел, определяется значение newLevel, после чего отводится память для узла. Ссылки вперед устанавливаются по информации, содержащей в массиве update. Функция deleteNode удаляет узлы из списка и освобождает занимаемую ими память. Она реализована аналогично функции findNode и так же ищет в списке удаляемый узел. 3.5 Сравнение методов Мы рассмотрели несколько методов организации словарей: хеш-таблицы, несбалансированные двоичные деревья, красно-черные деревья и разделенные списки. Имеются несколько факторов, которые влияют на выбор алгоритма в конкретной ситуации: •Сортировка результата. Если результат должен быть отсортирован, хеш-таблицы представляются не вполне подходящими, поскольку их элементы заносятся в таблицу в порядке, определяемом только их хеш-значениями. Все обстоит совсем по-другому при работе с двоичными деревьями. При проходе дерева в обратном порядке1 мы получаем отсортированный список. Вот как это делается: void WalkTree(Node *P) { if (p == NIL) return; WalkTree(P->Left); /* Здесь исследуем P->Data */ WalkTree(P->Right); WalkTree(Root); •Чтобы получить отсортированный список узлов разделенного списка, достаточно пройтись по ссылкам нулевого уровня. Вот так: Node *P = List.Hdr->Forward[0]; while (P != NIL) { /* Здесь исследуем P->Data */ P = P->Forward[0]; •Память. Минимизация памяти, которая уходит на "накладные расходы", особенно важна, когда нужно хранить много маленьких узлов. ♦Для хеш-таблиц требуется только один указатель на узел. Кроме того, требуется память под саму таблицу. ♦Для красно-черных деревьев в каждом узле нужно хранить ссылку на левого и правого потомка, а также ссылку на предка. Кроме того, где-то нужно хранить и цвет узла! Хотя на цвет достаточен только один бит, из-за выравнивания структур, требуемого для эффективности доступа, как правило, будет потрачено больше места. Таким образом, каждый узел красно-черного дерева требует памяти, которой хватило бы на 3-4 указателя. ♦Для разделенных списков в каждом узле имеется ссылка нулевого уровня. Вероятность иметь ссылку уровня 1 равна S. Вероятность иметь ссылку уровня 2 равна j. В общем, количество ссылок на узел равно Терминология Д.Кнута (т.1,п.2.3.1): postorder. В оригинале данной работы этот же порядок назван in-order. • Время. Алгоритм должен быть эффективным. Это особенно важно, когда ожидаются большие объемы данных. В таблице 3.2 сравниваются времена поиска для каждого алгоритма. Обратите внимание на то, что наихудшие случаи для хеш-таблиц и разделенных списков чрезвычайно маловероятны. Экспериментальные данные описаны n = 1 + - + -+ = 2. 2 4 • Простота. Если алгоритм короток и прост, при его реализации и/или использовании ошибки будут допущены с меньшей вероятностью. Кроме того, это облегчает проблемы сопровождения программ. Количества операторов, исполняемых в каждом алгоритме, также содержатся в таблице 3.2.
Таблица 0.2: Сравнение алгоритмов ведения словарей В таблице 3.3 приведены времена, требуемые для вставки, поиска и удаления 65536 (216) случайных элементов. В этих экспериментах размер хеш-таблицы равнялся 10009, для разделенных списков допускалось до 16 уровней ссылок. Конечно, в реальных ситуациях времена могут отличаться от приведенных здесь, однако, таблица дает достаточно информации для выбора подходящего алгоритма.
Таблица 0.3: Среднее время (мсек) для 65536 случайных элементов В таблице 3.4 приведены средние времена поиска для двух случаев: случайных данных, и упорядоченных, значения которых поступали в возрастающем порядке. Упорядоченные данные являются наихудшим случаем для несбалансированных деревьев, поскольку дерево вырождается в обычный односвязный список. Приведены времена для "одиночного" поиска. Если бы нам понадобилось найти все 65536 элементов, то красно-черныму дереву понадобилось бы 6 секунд, а несбалансированному - около 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||