Алгоритм - перемешивание
Cтраница 1
Алгоритм перемешивания позволяет находить пару АВ обычно за одну операцию считывания страницы. Затем кольца очень быстро просматриваются в оперативной памяти, что обеспечивает эффективное моделирование ассоциативной памяти. Аналогия теряется при появлении цепей переполнения, не показанных на рисунке. [1]
Алгоритмы перемешивания осуществляют преобразование ключа записи в номер соответствующего первичного участка. Однако алгоритм, преобразующий номер участка в его машинный адрес, должен учитывать наличие участков переполнения в основной области. [2]
Наиболее приемлемый алгоритм перемешивания выбирают следующим образом: берут достаточно представительный набор ключей файла, применяют к нему все возможные алгоритмы перемешивания и определяют число записей, направленных в каждый участок основной области, и число записей, направленных в область переполнения. [3]
Удачно выбранный алгоритм перемешивания приводит лишь к несколько лучшим результатам, чем случайное преобразование ключей записей файла. Поэтому при оценке плотности заполнения основной области и числа записей в области переполнения не следует слишком доверять результатам, приведенным в табл. 21.1 и на рис. 21.4. При выборе размера участка необходимо учитывать характеристики конкретного типа внешнего запоминающего устройства. [4]
Запись, направленная алгоритмом перемешивания в полностью заполненный участок основной области, помещается в свободный участок области переполнения. Адрес этого участка запоминается в исходном участке основной области. Если алгоритм перемешивания направляет еще одну запись в тот же участок основной области, то она помещается в какой-нибудь другой участок области переполнения. [5]
 |
Коды Грея. [6] |
Случайное кодирование основано на том, что алгоритм перемешивания дает случайные кодовые слова. Ясно, что два имени, отличающиеся одной буквой, дают разные слова. Ясно, что этот алгоритм весьма эффективен, но, возможно, его можно еще улучшать. Здесь этот вопрос не рассматривается. [7]
В - размер участка в байтах; N - - номер участка, полученный на выходе алгоритма перемешивания. [8]
 |
Преобразование ключа в адрес методом сдвига разрядов.| Преобразование ключа в адрес методом складывания. [9] |
Выбросив из ключа разряды, имеющие распределение, сильно отличающееся от равномерного, и преобразуя только оставшиеся разряды, мы сможем достичь более равномерного распределения адресов на выходе алгоритма перемешивания. [10]
При реальных вычислениях для обеспечения устойчивости алгоритма к округлениям осуществляют перемешивание чисел TJ. Алгоритм перемешивания в случае k - 2 заключается в следующем. [11]
 |
Зависимость числа записей, размещаемых в области переполнения, от вместимости участков и плотности заполнения основной области. [12] |
Системный аналитик может выбрать между плотностью заполнения, большой вместимостью заполнения, большой вместимостью участков и малым количеством записей в области переполнения. Предполагается, что алгоритм перемешивания, подобно колесу рулетки, осуществляет выбор номера участка случайным образом. [13]
В справочнике содержатся сведения о том, какие участки еще не заполнены; эти сведения позволяют избежать последовательного просмотра участков при внесении записей. При включении новых записей алгоритм перемешивания определяет номер первичного участка, куда данная запись должна быть помещена. [14]
Ключ записи преобразуется в квазислучайное число п, находящееся в диапазоне от 1 до N, где N - число участков, используемых для размещения записей. Для этой операции могут быть применены многие алгоритмы перемешивания. Необходимо выбрать тот, который наилучшим образом соответствует множеству ключей, используемому в данной задаче. [15]
Страницы: 1 2