|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[120] равен I)1. Будем считать, что наша операционная система, как и большинство современных, снабжена подсистемой управления памятью, позволяющей при необходимости выделять новые блоки памяти и освобождать занятые. Имея это в виду, при попытке добавить запись к заполненной таблице мы будем предварительно расширять (expand) таблицу следующим образом: выделим память под таблицу увеличенного размера, скопируем имеющиеся записи из старой таблицы в новую, после чего добавим запись уже к новой таблице. Как показывает опыт, разумно увеличивать таблицу вдвое в момент переполнения. Если мы только добавляем записи к таблице, то при такой стратегии коэффициент заполнения не может стать меньше 1/2 (если он не был таким в самом начале), т.е. пустые ячейки не будут занимать более половины таблицы. Вот как выглядит алгоритм Table-Insert, основанный на этих принципах (table[T] -указатель на блок памяти, в котором размещена таблица Г, пит[Т] - количество записей в таблице, size[T] - размер таблицы, т.е. количество ячеек; первоначально size[T] = num[T] = 0): Table-Insert (Г, ж) 1if size[T] = 0 2then выделить блок table[T] с одной ячейкой 3size[T] <- 1 4if num[T] = size[T] 5then выделить блок памяти new-table с 2 • size[T] ячейками 6скопировать все записи из table[T] в new-table 7освободить память, занятую table[T] 8table[T] <- new-table 9size[T] <- 2 • size[T] 10записать ж в table[T] 11num[T] <- num[T] + 1 Проанализируем время работы этого алгоритма. Собственно запись в таблицу происходит в нём только в строках 6 и 10. Стоимость операции «записать элемент в таблицу» примем за единицу. Будем считать, что время работы всей процедуры Table-Insert пропорционально количеству операций «записать в таблицу»; тем самым мы подразумеваем, что затраты на выделение памяти под таблицу с одной ячейкой (строка 2) - величина ограниченная, и что затраты на выделение и освобождение памяти в строках 5 и 7 - величина не большего порядка, чем затраты на переписыва- 1В некоторых приложениях (например, в хеш-таблицах с открытой адресацией) разумно считать таблицу заполненной уже в тот момент, когда коэффициент заполнения превышает некоторую константу, меньшую единицы (см. упр. 18-4.2). ние из одной таблицы в другую (строка 6). Пусть теперь мы применили га операций Table-Insert к таблице, не содержащей первоначально ни одной ячейки. Какова стоимость г-й операции, после которой в таблице будет г элементов? Обозначим эту стоимость через сг-. Если в таблице есть место (или если г = 1), то сг- = 1 (мы записываем новый элемент в таблицу один раз в строке 10. Если же места в таблице нет и добавление записи к таблице сопровождается расширением таблицы, то сг- = г: одна единица стоимости идет на запись нового элемента в расширенную таблицу (строка 10), и ещё г - 1 единица пойдет на копирование старой таблицы в новую (строка 6). Стало быть, сг- га при всех г, и грубая оценка стоимости га операций Table-Insert есть О (га2). Можно, однако, эту оценку улучшить, если проследить, сколь часто происходит расширение таблицы. В самом деле, расширение происходит только в том случае, когда г - 1 является степенью двойки, так что Стало быть, стоимость га операций Table-Insert не превосходит Зга, и учётную стоимость каждой такой операции можно считать равной 3. Понять, откуда берется коэффициент 3, можно с помощью метода предоплаты. Именно, при выполнении каждой операции Table-Insert (Г, ж) будем вносить по 3 доллара, при этом один доллар немедленно израсходуем на оплату операции «записать х в table[T]» в строке 10, ещё один доллар прикрепим к элементу ж, а оставшийся отдадим одному из элементов, уже записанных в таблицу (из тех, что ещё не получили своего доллара) Этими долларами будет оплачиваться перенос записей из старой таблицы в расширенную. При этом всякий раз, когда таблицу необходимо расширять, каждый из её элементов будет иметь по доллару. В самом деле, пусть при предыдущем расширении таблица имела размер т и была расширена до 2т. С тех пор мы добавили т элементов, при этом и добавленные элементы, и каждый из т старых элементов получили по доллару. Таким образом, следующее расширение таблицы уже оплачено. Можно проанализировать алгоритм Table-Insert и с помощью метода потенциалов. Чтобы это сделать, надо придумать такую потенциальную функцию, которая равна нулю сразу после расширения таблицы и нарастает по мере расширения таблицы (становясь равной размеру таблицы в тот момент, когда свободных ячеек не остаётся). Этим условиям удовлетворяет, например, функция п Ф(Г) = 2 • пит[Т] size[T]. Начальное значение потенциала равно нулю, и поскольку в любой момент не менее половины таблицы заполнено, значение Ф(Г) всегда неотрицательно. Стало быть, сумма учётных стоимостей операций Table-Insert (определённых по методу потенциалов как фактическая стоимость плюс изменение потенциала) оценивает сверху суммарную фактическую стоимость. Найдем учётные стоимости. Для этого обозначим через size;, пицц и Фг размер, количество записей и потенциал таблицы после г-й операции Table-Insert. Если эта операция не сопровождалась расширением таблицы, то size; = sizei-i, пипц = питг 1 + 1 и сг- = 1, откуда с,- = с,- + Фг - Ф,- 1 = 3. Если же г-я операции Table-Insert сопровождалась расширением таблицы, то sizei/2 = sizei-i = nurrii-i и сг- = пига,-, откуда опять-таки с,- = с,- + Ф,- - Ф,- 1 = = пига, + (2 пипц - size/) - (2пипц \ - sizei \) = = пицц + (2 пипц - (2 пипц - 2)) - (2(пищ - 1) - (пиггц - 1)) = = пицц + 2 - (nurrii - 1) = 3. На рис. 18.3 изображена зависимость величин nurrii, sizei и Фг- от г. Обратите внимание, как накапливается потенциал к моменту расширения таблицы. 18.4.2. Расширение и сокращение таблицы Теперь займемся операцией Table-Delete (удалить из таблицы). Помимо удаления ненужной записи из таблицы, желательно сократить (contract) таблицу, как только коэффициент заполнения станет слишком низок. Общая стратегия тут та же, что и при расширении таблицы: как только число записей падает ниже некоторого предела, мы выделяем память под новую таблицу меньшего размера, копируем в меньшую таблицы все записи из большей, после чего возвращаем операционной системе память, занимавшуюся старой таблицей. Мы построим алгоритм Table-Delete со следующими свойствами: •коэффициент заполнения ограничен снизу положительной константой, •учётная стоимость операций Table-Insert и Table-Delete есть 0(1). При этом мы по-прежнему будем считать, что стоимость алгоритма определяется количеством операций «записать в таблицу» (строки 6 и 10 алгоритма Table-Insert) и противоположных ей |
Среды: 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 | ||