VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

возникает, когда для элементов, которые первоначально должны занимать одну

и ту же ячейку, выполняется одна и та же тестовая последовательность, и

образуется вторичный кластер, распределенный по хеш-таблице. Можно

устранить оба эти эффекта, если сделать так, чтобы для разных элементов

выполнялись различные тестовые последовательности, даже если элементы

первоначально и должны были занимать одну и ту же ячейку.

Один из способов сделать это заключается в использовании в тестовой

последовательности генератора псевдослучайных чисел. Для вычисления

тестовой последовательности для элемента, его значение используется для

инициализации генератора случайных чисел. Затем для построения тестовой

последовательности используются последовательные случайные числа,

получаемые на выходе генератора. Это называется псевдослучайной проверкой

(pseudo-random probing).

Когда позднее требуется найти элемент в хеш-таблице, генератор случайных

чисел снова инициализируется значением элемента, при этом на выходе

генератора мы получим ту же самую последовательность чисел, которая

использовалась для вставки элемента в таблицу. Используя эти числа, можно

воссоздать исходную тестовую последовательность и найти элемент.

@Рис. 11.9. Вторичная кластеризация

==========305

Если используется качественный генератор случайных чисел, то разные

значения элементов будут давать различные случайные числа и соответственно

разные тестовые последовательности. Даже если два значения изначально

отображаются на одну и ту же ячейку, то следующие позиции в тестовой

последовательности будут уже различными. В этом случае в хеш-таблице не

будет возникать первичная или вторичная кластеризация.

Можно проинициализировать генератор случайных чисел Visual Basic, используя

начальное число, при помощи двух строчек кода:

Rnd -1

Randomize seed_value

Оператор Rnd дает одну и ту же последовательность чисел после инициализации

одним и тем же начальным числом. Следующий кода показывает, как можно

выполнять поиск элемента с использованием псевдослучайной проверки:

Public Function LocateItem(Value As Long, pos As Integer, _

probes As Integer) As Integer

Dim new_value As Long

' Проинициализировать генератор случайных чисел.

Rnd -1

Randomize Value

probes = 1

pos = Int(Rnd * m_NumEntries)

Do

new_value = m_HashTable(pos)

' Элемент найден.

If new_value = Value Then

LocateItem = HASH_FOUND

Exit Function

End If

' Элемента нет в таблице.

If new_value = UNUSED Or probes > NumEntries Then

LocateItem = HASH_NOT_FOUND

pos = -1

Exit Function

End If

pos = Int(Rnd * m_NumEntries)

probes = probes + 1

Loop

End Function

=======306

Программа Rand демонстрирует открытую адресацию с псевдослучайной

проверкой. Она аналогична программам Linear и Quad, но использует

псевдослучайную, а не линейную или квадратичную проверку.

В табл. 11.4 приведена примерная средняя длина тестовой последовательности,

полученной в программах Quad или Rand для хеш-таблицы со 100 ячейками и

элементами, значения которых находятся в диапазоне от 1 до 999. Обычно

псевдослучайная проверка дает наилучшие результаты, хотя разница между

псевдослучайной и квадратичной проверками не так велика, как между линейной

и квадратичной.

Псевдослучайная проверка также имеет свои недостатки. Так как тестовая

последовательность выбирается псевдослучайно, нельзя точно предсказать,

насколько быстро алгоритм обойдет все элементы в таблице. Если таблица

меньше, чем число возможных псевдослучайных значений, то существует

вероятность того, что тестовая последовательность обратится к одному

значению несколько раз до того, как она выберет другие значения в таблице.

Возможно также, что тестовая последовательность будет пропускать какую-либо

ячейку в таблице и не сможет вставить новый элемент, даже если таблица не

заполнена до конца.

Так же, как и в случае квадратичной проверки, эти эффекты могут вызвать

затруднения, только если таблица почти заполнена. В этом случае увеличение

таблицы дает гораздо больший прирост производительности, чем поиск

неиспользуемых ячеек таблицы.

@Рис. 11.4. Длина поиска при использовании квадратичной и псевдослучайной

проверки

=======307

Удаление элементов

Удаление элементов из хеш-таблицы, в которой используется открытая

адресация, выполняется не так просто, как удаление их из таблицы,

использующей связные списки или блоки. Просто удалить элемент из таблицы

нельзя, так как он может находиться в тестовой последовательности другого

элемента.

Предположим, что элемент A находится в тестовой последовательности элемента

B. Если удалить из таблицы элемент A, найти элемент B будет невозможно. Во

время поиска элемента B встретится пустая ячейка, которая осталась после

удаления элемента A, поэтому будет сделан неправильный вывод о том, что

элемент B отсутствует в таблице.

Вместо удаления элемента из хеш-таблицы можно просто пометить его как

удаленный. Можно использовать эту ячейку позднее, если она встретится во

время выполнения вставки нового элемента в таблицу. Если помеченный элемент

встречается во время поиска другого элемента, он просто игнорируется и

тестовая последовательность продолжится.

После того, как большое число элементов будет помечено как удаленные, в хеш-

таблице может оказаться множество неиспользуемых ячеек, и при поиске

элементов достаточно много времени будет уходить на пропуск удаленных

элементов. В конце концов, может потребоваться рехеширование таблицы для

освобождения неиспользуемой памяти.

Рехеширование

Чтобы освободить удаленные элементы из хеш-таблицы, можно выполнить ее

рехеширование (rehashing) на месте. Чтобы этот алгоритм мог работать, нужно

иметь какой-то способ для определения, было ли выполнено рехеширование

элемента. Простейший способ сделать это — определить элементы в виде

структур данных, содержащих поле Rehashed.

Type ItemType

Value As Long

Rehashed As Boolean

End Type

Вначале присвоим полю Rehashed значение false. Затем выполним проход по

таблице в поиске ячеек, которые не помечены как удаленные, и для которых

еще не было выполнено рехеширование.

Если такой элемент встретится, то выполняется его удаление из таблицы и

повторное хеширование, при этом выполняется обычная тестовая

последовательность для элемента. Если встречается свободная или помеченная

как удаленная ячейка, элемент размещается в ней, помечается как

рехешированный, и продолжается проверка остальных элементов, для которых

еще не было выполнено рехеширование.

Если при выполнении рехеширования найдется элемент, который уже был помечен

как рехешированный, то тестовая последовательность продолжается. Если затем

встретится элемент, для которого еще не было выполнено рехеширование, то

элементы меняются местами, текущая ячейка помечается как рехешированная и

процесс начинается снова.

======308

Изменение размера хеш-таблиц

Если хеш-таблица становится почти заполненной, производительность

значительно падает. В этом случае может понадобиться увеличение размера

таблицы, чтобы в ней было больше места для элементов. И наоборот, если в

таблице слишком мало ячеек, может потребоваться уменьшить ее, чтобы

освободить занимаемую память. Используя методы, похожие на те, которые

использовались при рехешировании таблицы на месте, можно увеличивать и

уменьшать размер хеш-таблицы.

Чтобы увеличить хеш-таблицу, вначале размер массива, в котором она

находится, увеличивается при помощи оператора Dim Preserve. Затем

выполняется рехеширование таблицы, при этом элементы могут занимать ячейки

в созданной свободной области в конце таблицы. После завершения

рехеширования таблица будет готова к использованию.

Чтобы уменьшить размер таблицы, вначале определим, сколько элементов должно

содержаться в массиве таблицы после уменьшения. Затем выполняем

рехеширование таблицы, причем элементы помещаются только в уменьшенную

часть таблицы. После завершения рехеширования всех элементов, размер

массива уменьшается при помощи оператора ReDim Preserve.

Следующий код демонстрирует рехеширование таблицы с использованием линейной

проверки. Код для рехеширования таблицы с использованием квадратичной или

псевдослучайной проверки выглядит почти так же:

Public Sub Rehash()

Dim i As Integer

Dim pos As Integer

Dim probes As Integer

Dim Value As Long

Dim new_value As Long

' Пометить все элементы как нерехешированные.

For i = 0 To NumEntries - 1

m_HashTable(i).Rehashed = False

Next i

' Поиск нерехешированных элементов.

For i = 0 To NumEntries - 1

If Not m_HashTable(i).Rehashed Then

Value = m_HashTable(i).Value

m_HashTable(i).Value = UNUSED

If Value <> DELETED And Value <> UNUSED Then

' Выполнить тестовую последовательность

' для этого элемента, пока не найдется свободная,

' удаленная или нерехешированная ячейка.

probes = 0

Do

pos = (Value + probes) Mod NumEntries

new_value = m_HashTable(pos).Value

' Если ячейка свободна или помечена как

' удаленная, поместить элемент в нее.

If new_value = UNUSED Or _

new_value = DELETED _

Then

m_HashTable(pos).Value = Value

m_HashTable(pos).Rehashed = True

Exit Do

End If

' Если ячейка не помечена как рехешированная,

' поменять их местами и продолжить.

If Not m_HashTable(pos).Rehashed Then

m_HashTable(pos).Value = Value

m_HashTable(pos).Rehashed = True

Value = new_value

probes = 0

Else

probes = probes + 1

End If

Loop

End If

End If

Next i

End Sub

Программа Rehash использует открытую адресацию с линейной проверкой. Она

аналогична программе Linear, но позволяет также помечать объекты как

удаленные и выполнять рехеширование таблицы.

Резюме

Различные типы хеш-таблиц, описанные в этой главе, имеют свои преимущества

и недостатки.

Для хеш-таблиц, которые используют связные списки или блоки можно легко

изменять размер таблицы и удалять из нее элементы. Использование блоков

также позволяет легко работать с таблицами на диске, позволяя считать за

одно обращение к диску сразу множество элементов данных. Тем не менее, оба

эти метода являются более медленными, чем открытая адресация.

Линейная проверка проста и позволяет достаточно быстро вставлять и удалять

элементы из таблицы. Применение упорядоченной линейной проверки позволяет

быстрее, чем в случае неупорядоченной линейной проверки, установить, что

элемент отсутствует в таблице. С другой стороны, вставку элементов в

таблицу при этом выполнить сложнее.

Квадратичная проверка позволяет избежать кластеризации, которая характерна

для линейной проверки, и поэтому обеспечивает более высокую

производительность. Псевдослучайная проверка обеспечивает еще более высокую

производительность, так как при этом удается избавиться как от первичной,

так и от вторичной кластеризации.

В табл. 11.5 приведены преимущества и недостатки различных методов

хеширования.

======310

@Таблица 11.5. Преимущества и недостатки различных методов хеширования

Выбор наилучшего метода хеширования для данного приложения зависит от

данных задачи и способов их использования. При применении разных схем

достигаются различные компромиссы между занимаемой памятью, скоростью и

простотой изменений. Табл. 11.5 может помочь вам выбрать наилучший алгоритм

для вашего приложения.

=======311

Глава 12. Сетевые алгоритмы

В 6 и 7 главах обсуждались алгоритмы работы с деревьями. Данная глава

посвящена более общей теме сетей. Сети играют важную роль во многих

приложениях. Их можно использовать для моделирования таких объектов, как

сеть улиц, телефонная или электрическая сеть, водопровод, канализация,

водосток, сеть авиаперевозок или железных дорог. Менее очевидна возможность

использования сетей для решения таких задач, как разбиение на районы,

составление расписания методом критического пути, планирование коллективной

работы или распределения работы.

Определения

Как и в определении деревьев, сетью (network) или графом (graph) называется

набор узлов (nodes), соединенных ребрами (edges) или связями (links). Для

графа, в отличие от дерева, не определено понятие родительского или

дочернего узла.

С ребрами сети может быть связано соответствующее направление, тогда в этом

случае сеть называется ориентированной сетью (directed network). Для каждой

связи можно также определить ее цену (cost). Для сети дорог, например, цена

может быть равна времени, которое займет проезд по отрезку дороги,

представленному ребром сети. В телефонной сети цена может быть равна

коэффициенту электрических потерь в кабеле, представленном связью. На рис.

12.1 показана небольшая ориентированная сеть, в которой числа рядом с

ребрами соответствуют цене ребра.

Путем (path) между узлами A и B называется последовательность ребер,

которая связывает два этих узла между собой. Если между любыми двумя узлами

сети есть не больше одного ребра, то путь можно однозначно описать,

перечислив входящие в него узлы. Так как такое описание проще представить

наглядно, то пути по возможности описываются таким образом. На рис. 12.1

путь, проходящий через узлы B, E, F, G,E и D, соединяет узлы B и D.

Циклом (cycle) называется путь который связывает узел с ним самим. Путь E,

F, G, E на рис. 12.1 является циклом. Путь называется простым (simple),

если он не содержит циклов. Путь B, E, F, G, E, D не является простым, так

как он содержит цикл E, F, G, E.

Если существует какой-либо путь между двумя узлами, то должен существовать

и простой путь между ними. Этот путь можно найти, если удалить все циклы из

исходного пути. Например, если заменить цикл E, F, G, E в пути B, E, F, G,

E, D на узел E, то получится простой путь B, E, D, связывающий узлы B и D.

=======313

@Рис. 12.1. Ориентированная сеть с ценой ребер

Сеть называется связной (connected), если между любыми двумя узлами

существует хотя бы один путь. В ориентированной сети не всегда очевидно,

является ли сеть связной. На рис. 12.2 сеть слева является связной. Сеть

справа не является связной, так как не существует пути из узла E в узел C.

Представления сети

В 6 главе было описано несколько представлений деревьев. Большинство из них

применимо также и для работы с сетями. Например, представления полными

узлами, списком потомков (списком соседей для сетей) или нумерацией связей

также могут использоваться для хранения сетей. За описанием этих

представлений обратитесь к 6 главе.

@Рис. 12.2. Связная (слева) и несвязная (справа) сети

======314

Для различных приложений могут лучше подходить разные представления сети.

Представление полными узлами обеспечивает хорошие результаты, если каждый

узел в сети связан с небольшим числом ребер. Представление списком соседних

узлов обеспечивает большую гибкость, чем представление полными узлами, а

представление нумерацией связей, хотя его сложнее модифицировать,

обеспечивает более высокую производительность.

Кроме этого, некоторые варианты представления ребер могут упростить работу

с определенными типами сетей. Эти представления используют один класс для

узлов и другой — для представления связей. Применение класса для связей

облегчает работу со свойствами связей, такими, как цена связи.

Например, ориентированная сеть с ценой связей может использовать следующее

определения для класса узла:

Public Id As Integer ' Номер узла.

Public Links As Collection ' Связи, ведущие к соседним узлам.

Можно использовать следующее определение класса связей:

Public ToNode As NetworkNode ' Узел на другом конце связи.

Public Cost As Integer ' Цена связи.

Используя эти определения, программа может найти связь с наименьшей ценой,

используя следующий код:

Dim link As NetworkLink

Dim best_link As NetworkLink

Dim best_cost As Integer

best_cost = 32767

For Each link In node.Links

If link.cost < best_cost Then

Set best_link = link

best_cost = link.cost

End If

Next link

Классы node и link часто расширяются для удобства работы с конкретными

алгоритмами. Например, к классу node часто добавляется флаг Marked. Если

программа обращается к узлу, то она устанавливает значение поля Marked

равным true, чтобы знать, что узел уже был проверен.

Программа, управляющая неориентированной сетью, может использовать немного

другое представление. Класс node остается тем же, что и раньше, но класс

link включает ссылку на оба узла на концах связи.

Public Node1 As NetwokNode ' Один из узлов на конце связи.

Public Node2 As NetwokNode ' Другой узел.

Public Cost As Integer ' Цена связи.

Для неориентированной сети, предыдущее представление использовало бы два

объекта для представления каждой связи — по одному для каждого из

направлений связи. В новой версии каждая связь представлена одним объектом.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31