Вычисление - адрес
Cтраница 3
В программе 6.11 приведена подпрограмма вычисления адреса модуля КАМАК Она представляет собой эквивалентную запись программы 6.2 в виде подпрограммы. [31]
 |
Поиск путем вычисления адреса.| Поиск путем вычисления адреса с непрямой адресацией. [32] |
Блок-схема алгоритма двухступенчатого поиска с вычислением адреса на первой ступени и перебором на второй ступени изображена на рис. 1.6. В качестве признака подмножества, выделяемого на первом этапе поиска, используется значение группы старших разрядов признака, заданное в условии поиска. [33]
На шагах 4 и 5 осуществляется вычисление адресов источника и места назначения для следующего элемента строки. Наконец, шаги 1, 6 и 7 служат для определения числа обработанных элементов. [34]
От чего зависит хорошая эффективность методов вычисления адреса. Возможно, секрет лежит в выборе разумной хеш-функции, которая по возможности предотвращает коллизии. Однако в реальных случаях хеш-функция выбирается до того, как содержимое таблицы становится известным, а это означает, что способа избежать коллизий не существует. Даже если хеш-функция отображает имена на пространство адресов равномерно, доля А, / 2 имен в таблице будет образовывать коллизию с ранее введенными именами ( см. упр. Поскольку X обычно близко к 1, почти половина имен приводит к коллизиям; следовательно, даже самая лучшая хеш-функция не может предотвратить большого числа коллизий. К счастью, число коллизий имеет слабое влияние на эффективность методов вычисления адреса; коллизия удлиняет последовательность проб только на одну ячейку. [35]
Трудоемкость операции пересылки зависит от сложности вычисления адресов позиций по заданным значениям индексов i и /, а также от трудоемкости самого перемещения объекта с одной позиции на другую, зависящей от организации информации в позиции и от ее объема. [36]
Мы уже отмечали, что сортировка вычислением адреса дает хорошие результаты с избыточной таблицей. Однако размещение элементов по порядку замедляет процесс. Существенное улучшение может быть достигнуто путем размещения элементов случайным ( или псевдослучайным) путем. Случайный порядковый номер К для данного элемента генерируется из значения ключа методами, подобными используемым при вычислении адреса. Если К-я позиция пуста, туда помещается новый элемент; если нет, то должна быть найдена другая ячейка для размещения. [37]
 |
Хеш-таблица для небольшого пространства имен. [38] |
Наконец, таблицы, основанные на вычислении адреса, расширить динамически непросто: это Может приводить к потере памяти, если таблица слишком велика, или к малой производительности, если таблица слишком мала. Тем не менее методы вычисления адреса в некоторых случаях являются ценными; многие таблицы, например, не обязательно записывать в естественном порядке; худшим случаем часто можно пренебречь, если он возникает достаточно редко, и размеры многих таблиц можно точно оценить a priori. В последующих разделах более подробно обсуждаются самые популярные методы. [39]
Для реализации доступа к записи по методу вычисления адреса по значению первичного поискового ключа ( CALC-ключа) на каждой странице области организуются два специальных CALC-указателя. Эти указатели рассматриваются как запись - владелец экземпляра системного CALC-набора. При этом каждой странице соответствует свой экземпляр CALC-набора. При помещении записи в БД, на основании значения первичного ключа записи формируется по методу хеширования номер страницы области, затем запись размещается на этой странице и включается в CALC-набор, владелец которого находится также на этой странице. Если на странице не хватает места, то запись размещается на другой странице, однако включается в тот экземпляр CALC-набора, который находится на странице, определенной хешированием по значению ключа. При поиске записи по значению CALC-ключа СУБД с помощью хеширования определяет экземпляр CALC-набора, а затем в нем последовательным просмотром членов выполняет поиск требуемой записи. [40]
Первые два примера этого раздела4 иллюстрировали методы вычисления адреса ограниченной применимости: когда пространство имен меньше доступной памяти или когда содержимое таблицы известно до выбора хеш-функции. Третий пример самый важный; он иллюстрирует метод, полезный, когда пространство имен великой хеш-функция и схема разрешения коллизий должны быть выбраны до того, как станет известным содержимое таблицы. Более подробно эти задачи обсуждаются в следующих разделах. [41]
Поиск, таким образом, сводится к вычислению адреса управляющего слова на первой ступени и перебору в пределах области, упоминаемой в управляющем слове, на второй ступени. [42]
Одно из типичных применений сумматора адресов - это вычисление адреса команды, которая должна выполняться вслед за данной. Существуют операции ( называемые операциями управления ], которые определяют этот адрес сами, в качестве результата своей работы. Для остальных операций адрес следующей команды получается в результате добавления единицы к адресу, хранящемуся на регистре адреса команды. Это сложение выполняется на сумматоре адресов. [43]
Одно из типичных применений сумматора адресов - это вычисление адреса команды, которая должна выполняться вслед за данной. Существуют операции ( называемые операциями управления), которые определяют этот адрес сами, в качестве результата своей работы. Для остальных операций адрес следующей команды получается в результате добавления единицы к адресу, хранящемуся на регистре адреса команды. Это сложение выполняется на сумматоре адресов и его результат снова посылается на регистр адреса команды. [44]
Для повышения - эффективности используется двухступенчатый поиск с вычислением адресов на первой ступени и перебором на второй ступени. [45]
Страницы: 1 2 3 4