Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 188

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 182 183 184 185 186 187 < 188 > 189 190 191 192 193 194 .. 316 >> Следующая

Примером представления, подходящего для ассоциативных массивов, является ключевое представление, когда по индексу вычисляется ключ, а уже по ключу размещается значение (см. рис. 9.8). Здесь двойная стрелка означает
528
9.
Первое измерение:
Рис. 9.6. Ссылочное представление
один из вариантов представления записи
(<ключ, если для него есть компоненту Kj),
которая в кл чевом представлении заменяет исходнй компонент разре енного массива.
Таким образом, доступ к компоненте становится двухступенчатым:
1. выбор нужной компонента в новом наборе (логически это снова массив, но у е плотнй) и
2. извлечение Ki из записи (второе поле).
Старый индекс для такого представления называется ключом, а порядковые номера компонентов нового набора — индексами записей нового набора.
При ключевом доступе возникает задача контроля целостности: в новом наборе не долны появляться записи с одинаковми кл чами, и ну но контролировать, не нарушается ли упорядоченность ключей. Ключевое представление можно рассматривать как следующий по отношению к исходному массиву уровень абстракции (более ниний, реализационный), который, в сво очередь, допускает различне реализации двухступенчатого доступа.
казанная запись мо ет представляться стандартным способом, со свободной упаковкой (реже) или с использованием ссылок (очень часто). С учетом упорядоченности ключей (обычное свойство для ассоциативных массивов —
9.3.
529
A:
dl
dl'
Граничная цепочка dl
d2
A[d1,d2]
A[d1',d2]
Остаток этого столбца
d2'
Нет значения
A[dl,d2']
A[dl',d2']
статок этого столбца
статок этого ряда
статок этого ряда
Рис. 9.7. Решетчатое представление массива
см. ве) целесообразно предло ить организаци индексов, приспособленную для дихотомического поиска. Здесь возможны варианты:
1. ндекс представля тся как последовательность регистров со ссл-ками на Ключи, которая соответствует упорядоченности ключей — прямолинейная реализация.
2. По значениям ключей вместо массива Индексы строится B-дерево, обеспечивающее хорошую стратегию оперирования.
Значение ключа вершины, к которой ведет левая дуга, всегда больше значения ключа родительской вершины, которое, в свою очередь, боль-е значения кл ча правой верин . ерево долно бть сбалансированным (длин всех путей от корня к листьям различа тся не более чем на 1). Только в таком случае достигается эффективность доступа.
3. спользуется расс ановка (хеирование), суть которой сводится к следующему. Определяется расстановочное поле (хеш-таблица) — массив фиксированного размера m, который будет заполняться ссылками на группы компонентов исходного разреженного массива (записей нового представления). Эти группы далее называются гроздями. На множестве всех возможных значений ключей определяется функция рас-
530
9.
становки11 (хеш-функция) со значениями в множестве номеров гроздей
11 Термин 'хеширование' неудачен как в русском, так и в английском языке (переводится примерно как "что-либо мелко порубленное, нарезанное". Сам метод изобретен в СССР независимо от зарубежных аналогов и назван вполне логично расстановкой. Сопутствующие понятия также получили вполне адекватные наименования. Однако после ужасного (в смысле терминов) перевода замечательной книги Д. Гриса [26] расстановка стала замещаться хешированием, и сегодня русский термин некоторым кажется старомодным.
Впервые этот метод (примитивный вариант) предложен Петерсоном [87]. А. П. Ершов использовал собственный вариант метода в 1967 году в очень развитом для своего времени трансляторе [32]. Хорошее изложение этого метода см. в [46].
Ключіь
Ключ1 K1

K1LR
Kjik)41r K1R
nil
K1RR

Рис. 9.9. B-дерево
9.3. СТРУКТУРНЫЕ ТИПЫ
531
Расстановочное поле 1.
m
Ссылка на гроздь 1
Ссылка на гроздь 2
Ссылка на гроздь 3 nil

Ключш І Kin
КлЮЧцг І Ki12
...
КЛЮЧЦд1 Kilgl
слка на гроздь
Нет значений с соответствующими ключами
Ключ121 Ki21
Ключ122 Ki22
Ключ!2д2 I
Ki2g2
КлючіШ1 і Kim1
КлючіШ2 J Kim2
...
Ключітдт j Kimgm
Рис. 9.10. Расстановка (хеширование)
от 0 до m — 1 так, чтобы выполнялись условия перемешивания:
(a) для каждого значения ключа существует значение функции расстановки,
(b) множества всех возможных значений ключей разбивается на классы эквивалентных значений, у которых равны значения функции расстановки, тем самм кадый класс задает сво гроздь,
(c) модности гроздей должны оказаться примерно одинаковыми для статистически ожидаемого множества возможных значений ключей — равномерность расстановки.
стройство грозди мо ет бть лбым (массив, список). х взаимное размеение — так е непринципиально (например, мо но иметь перемешанные в памяти грозди).
Наряду с B-деревьями, хеширование сейчас наиболее применимый общий метод работы с ключевыми массивами. Поэтому возникают различные варианты и выро денне случаи расстановки
(а) Многоуровневая расстановка. По существу, это двухступенчатый доступ, т. е. работа с массивом массивов. Эффективность хеширования при этом резко падает. Используется, когда надо привлекать внен память.
Предыдущая << 1 .. 182 183 184 185 186 187 < 188 > 189 190 191 192 193 194 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100