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

probes As Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod 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 = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

End Function

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

Заполнив поле Table Size (Размер таблицы) и нажав на кнопку Create table

(Создать таблицу), можно создавать хеш-таблицы различных размеров. Затем

можно ввести значение элемента и нажать на кнопку Add (Добавить) или Find

(Найти), чтобы вставить или найти элемент в таблице.

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

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

могут иметь в области Random Items (Случайные элементы), и затем нажмите на

кнопку Create Items (Создать элементы).

После завершения программой какой-либо операции она выводит статус операции

(успешное или безуспешное завершение) и длину тестовой последовательности.

Она также выводит среднюю длину успешной и безуспешной тестовой

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

последовательности, выполняя поиск всех значений от 1 до максимального

значения в таблице.

В табл. 11.1 приведена средняя длина успешных и безуспешных тестовых

последовательностей, полученных в программе Linear для таблицы со 100

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

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

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

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

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

неплохой, даже если таблица практически заполнена. Если же программа часто

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

очень низкой, если таблица переполнена.

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

расходуя при этом слишком много памяти, если заполнено от 50 до 75

процентов таблицы. Если таблица заполнена больше, чем на 75 процентов, то

производительность падает. Если таблица заполнена меньше, чем на 50

процентов, то она занимает больше памяти, чем это необходимо. Это делает

открытую адресацию хорошим примером пространственно-временного компромисса.

Увеличивая хеш-таблицу, можно уменьшить время, необходимое для вставки или

поиска элементов.

=======297

@Таблица 11.1. Длина успешной и безуспешной тестовых последовательностей

Первичная кластеризация

Линейная проверка имеет одно неприятное свойство, которое называется

первичной кластеризацией (primary clustering). После добавления большого

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

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

кластер, чтобы найти пустую ячейку.

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

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

случайное число и вставить его в таблицу, то вероятность того, что элемент

займет любую заданную позицию P в таблице, равна 1/N.

При вставке второго случайно выбранного элемента, он может отобразиться на

ту же позицию с вероятностью 1/N. Из-за конфликта в этом случае он

помещается в позицию P + 1. Также существует вероятность 1/N, что элемент и

должен располагаться в позиции P + 1, и вероятность 1/N, что он должен

находиться в позиции P - 1. Во всех этих трех случаях новый элемент

располагается рядом с предыдущим. Таким образом, в целом существует

вероятность 3/N того, что 2 элемента окажутся расположенными вблизи друг от

друга, образуя небольшой кластер.

По мере роста кластера вероятность того, что следующие элементы будут

располагаться вблизи кластера, возрастает. Если в кластере находится два

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

кластеру, равна 4/N, если в кластере четыре элемента, то эта вероятность

равна 6/N, и так далее.

Что еще хуже, если кластер начинает расти, то его рост продолжается до тех

пор, пока он не столкнется с соседним кластером. Два кластера сливаются,

образуя кластер еще большего размера, который растет еще быстрее, сливается

с другими кластерами и образует еще большие кластеры.

======298

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

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

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

элемента. Также существует 50-процентная вероятность того, что он найдет

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

длина тестовой последовательности равна 0,5 * 1 + 0,5 * 2 = 1,5.

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

гигантский кластер. При этом все еще есть 50-процентная вероятность того,

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

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

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

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

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

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

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

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

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

эффекта кластеризации. Запустите программу и создайте хеш-таблицу со 100

ячейками, а затем добавьте 50 случайных элементов со значениями до 999. Вы

обнаружите, что образовалось несколько кластеров. В одном из тестов 38 из

50 элементов стали частью кластеров. Если добавить еще 25 элементов к

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

70 из 75 элементов были сгруппированы в кластеры.

Упорядоченная линейная проверка

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

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

искомое. Так как при этом возможное положение искомого элемента уже позади,

значит искомый элемент отсутствует в списке.

Можно использовать похожую идею при поиске в хеш-таблице. Предположим, что

можно организовать элементы в хеш-таблице таким образом, что значения в

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

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

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

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

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

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

probes As Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

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

If new_value = UNUSED Or probes > NumEntries Then

LocateItem = HASH_NOT_FOUND

pos = -1

Exit Function

End If

' Элемент найден или его нет в таблице.

If new_value >= Value Then Exit Do

pos = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

If Value = new_value Then

LocateItem = HASH_FOUND

Else

LocateItem = HASH_NOT_FOUND

End If

End Function

Для того, чтобы этот метод работал, необходимо организовать элементы в хеш-

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

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

вставки элементов, который гарантирует такое расположение элементов.

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

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

в эту позицию и процедура завершена. Если встречается элемент, значение

которого больше значения нового элемента, то они меняются местами и

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

При этом может встретиться элемент с еще большим значением. Тогда элементы

снова меняются местами, и выполняется поиск нового местоположения для этого

элемента. Этот процесс продолжается до тех пор, пока, в конце концов, не

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

местами.

========299-300

Public Function InsertItem(ByVal Value As Long, pos As Integer,_ probes

As Integer) As Integer

Dim new_value As Long

Dim status As Integer

' Проверить, заполнена ли таблица.

If m_NumUnused < 1 Then

' Поиск элемента.

status = LocateItem(Value, pos, probes)

If status = HASH_FOUND Then

InsertItem = HASH_FOUND

Else

InsertItem = HASH_TABLE_FULL

pos = -1

End If

Exit Function

End If

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

' Если значение найдено, поиск завершен.

If new_value = Value Then

InsertItem = HASH_FOUND

Exit Function

End If

' Если ячейка свободна, элемент должен находиться в ней.

If new_value = UNUSED Then

m_HashTable(pos) = Value

HashForm.TableControl(pos).Caption = Format$(Value)

InsertItem = HASH_INSERTED

m_NumUnused = m_NumUnused - 1

Exit Function

End If

' Если значение в ячейке таблицы больше значения

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

If new_value > Value Then

m_HashTable(pos) = Value

Value = new_value

End If

pos = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

End Function

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

проверкой. Она идентична программе Linear, но использует упорядоченную хеш-

таблицу.

В табл. 11.2 приведена средняя длина успешной и безуспешной тестовых

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

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

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

намного быстрее. Разница в особенности заметна, если хеш-таблица заполнена

более, чем на 70 процентов.

=========301

@Таблица 11.2. Длина поиска при использовании линейной и упорядоченной

линейной проверки

В обоих методах для вставки нового элемента требуется примерно одинаковое

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

с позиции (K Mod NumEntries) и перемещается по таблице до тех пор, пока не

найдет свободную ячейку. Во время упорядоченного хеширования может

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

последовательности. Если элементы представляют собой записи большого

размера, то на это может потребоваться больше времени, особенно если записи

находятся на диске или каком-либо другом медленном запоминающем устройстве.

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

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

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

которых нет в таблице, или элементы таблицы имеют большой размер и

перемещать их достаточно сложно, то можно получить лучшую

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

Квадратичная проверка

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

использовать хеш-функцию следующего вида:

Hash(K, P) = (K + P2) Mod N где P = 0, 1, 2, ...

Предположим, что при вставке элемента в хеш-таблицу он отображается в

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

позицию возле начала кластера, то возникнет еще несколько конфликтов

прежде, чем найдется свободная ячейка для элемента. По мере роста параметра

P в тестовой функции, значение этой функции быстро меняется. Это означает,

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

далеко от кластера.

=======302

На рис. 11.8 показана хеш-таблица, содержащая большой кластер элементов. На

нем также показаны тестовые последовательности, которые возникают при

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

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

прилегает к кластеру, поэтому после вставки этих элементов размер кластера

не увеличивается.

Следующий код демонстрирует поиск элемента с использованием квадратичной

проверки (quadratic probing):

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

Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod 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 = (Value + probes * probes) Mod NumEntries

probes = probes + 1

Loop

End Function

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

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

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

В табл. 11.3 приведена средняя длина тестовых последовательностей,

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

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

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

@Рис. 11.8. Квадратичная проверка

======303

@Таблица 11.3. Длина поиска при использовании линейной и квадратичной

проверки

Квадратичная проверка также имеет некоторые недостатки. Из-за способа

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

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

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

Например, рассмотрим небольшую хеш-таблицу, состоящую всего из шести ячеек.

Тестовая последовательность для числа 3 будет следующей:

3

3 + 12 = 4 = 4 (Mod 6)

3 + 22 = 7 = 1 (Mod 6)

3 + 32 = 12 = 0 (Mod 6)

3 + 42 = 19 = 1 (Mod 6)

3 + 52 = 28 = 4 (Mod 6)

3 + 62 = 39 = 3 (Mod 6)

3 + 72 = 52 = 4 (Mod 6)

3 + 82 = 67 = 1 (Mod 6)

3 + 92 = 84 = 0 (Mod 6)

3 + 102 = 103 = 1 (Mod 6)

и так далее.

Эта тестовая последовательность обращается к позициям 1 и 4 дважды перед

тем, как обратиться к позиции 3, и никогда не попадает в позиции 2 и 5.

Чтобы пронаблюдать этот эффект, создайте в программе Quad хеш-таблицу с

шестью ячейками, а затем вставьте элементы 1, 3, 4, 6 и 9. Программа

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

неиспользованными. Тестовая последовательность для элемента 9 не обращается

к элементам 2 и 5, поэтому программа не может вставить в таблицу новый

элемент.

=======304

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

обращаться, по меньшей мере, к N/2 ячеек таблицы, если размер таблицы N —

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

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

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

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

таблицы, а не беспокоиться о том, сможет ли тестовая последовательность

найти свободную ячейку.

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

проверки, заключается в том, что хотя она устраняет первичную

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

называется вторичной кластеризацией (secondary clustering). Если два

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

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

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

по хеш-таблице. Если появляется новый элемент с тем же самым начальным

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

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

На рис. 11.9 показана хеш-таблица, которая может содержать 10 ячеек. В

таблице находятся элементы 2, 12, 22 и 32, которые все изначально

отображаются в позицию 2. Если попытаться вставить в таблицу элемент 42, то

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

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

Псевдослучайная проверка

Степень кластеризации растет, если в кластер добавляются элементы, которые

отображаются на уже занятые кластером ячейки. Вторичная кластеризация

Страницы: 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