Смекни!
smekni.com

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

После завершения операции поиска или вставки, программа выводит статус операции в нижней части формы — была ли операция успешной и число проверенных во время ее выполнения элементов.

В строке статуса также выводится средняя длина успешной (если элемент есть в таблице) и безуспешной (если элемента в таблице нет) тестовых последовательностей. Программа вычисляет эти значения, выполняя поиск для всех чисел между единицей и наибольшим числом в хеш‑таблице, и затем подсчитывая среднее значение длины тестовой последовательности.

На рис. 11.2 показано окно программы Chain после успешного поиска элемента 414.[RV17]

Блоки

Другой способ разрешения конфликтов заключается в том, чтобы выделить ряд блоков, каждый из которых может содержать несколько элементов. Для вставки элемента в таблицу, он отображается на один из блоков и затем помещается в этот блок. Если блок уже заполнен, то используется обработка переполнения.

@Рис. 11.2. Программа Chain

[RV18]

======285

Возможно, самый простой метод обработки переполнения состоит в том, чтобы поместить все лишние элементы в специальные блоки в конце массива «нормальных» блоков. Это позволяет при необходимости легко увеличивать размер хеш‑таблицы. Если требуется больше дополнительных блоков, то размер массива блоков просто увеличивается, и в конце массива создаются новые дополнительные блоки.

Например, чтобы добавить новый элемент K в хеш‑таблицу, которая содержит пять блоков, вначале мы пытаемся поместить его в блок с номером K Mod 5. Если этот блок заполнен, элемент помещается в дополнительный блок.

Чтобы найти элемент в таблице, вычислим K Mod 5, чтобы найти его положение, и затем выполним поиск в этом блоке. Если элемента в этом блоке нет, и блок не заполнен, значит элемента в хеш‑таблице нет. Если элемента в блоке нет и блок заполнен, необходимо проверить дополнительные блоки.

На рис. 11.3 показаны пять блоков с номерами от 0 до 4 и один дополнительный блок. Каждый блок может содержать по 5 элементов. В этом примере в хеш‑таблицу были вставлены следующие элементы: 50, 13, 10 ,72, 25, 46, 68, 30, 99, 85, 93, 65, 70. При вставке элементов 65 и 70 блоки уже были заполнены, поэтому эти элементы были помещены в первый дополнительный блок.

Чтобы реализовать метод блочного хеширования в Visual Basic, можно использовать для хранения блоков двумерный массив. Если требуется NumBuckets блоков, каждый из которых может содержать BucketSize ячеек, выделим память под блоки при помощи оператора ReDim TheBuckets(0 To BucketSize -1, 0 To NumBuckets - 1). Второе измерение соответствует номеру блока. Оператор Visual Basic ReDim позволяет изменить только размер массива, поэтому номер блока должен быть вторым измерением массива.

Чтобы найти элемент K, вычислим номер блока K Mod NumBuckets. Затем проведем поиск в блоке до тех пор, пока не найдется искомый элемент, или пустая ячейка блока, или блок не закончится. Если элемент найден, поиск завершен. Если встретится пустая ячейка, значит элемента в хеш‑таблице нет, и процесс также завершен. Если проверен весь блок, и не найден искомый элемент или пустая ячейка, требуется проверить дополнительные блоки.

@Рис. 11.3. Хеширование с использованием блоков

======286

Public Function LocateItem(Value As Long, _

bucket_probes As Integer, item_probes As Integer) As Integer

Dim bucket As Integer

Dim pos As Integer

bucket_probes = 1

item_probes = 0

' Определить, к какому блоку он относится.

bucket = (Value Mod NumBuckets)

' Поиск элемента или пустой ячейки.

For pos = 0 To BucketSize - 1

item_probes = item_probes + 1

If Buckets(pos, bucket).Value = UNUSED Then

LocateItem = HASH_NOT_FOUND ' Элемент отсутствует.

Exit Function

End If

If Buckets(pos, bucket).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

' Проверить дополнительные блоки.

For bucket = NumBuckets To MaxOverflow

bucket_probes = bucket_probes + 1

For pos = 0 To BucketSize - 1

item_probes = item_probes + 1

If Buckets(pos, bucket).Value = UNUSED Then

LocateItem = HASH_NOT_FOUND ' Not here.

Exit Function

End If

If Buckets(pos, bucket).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

Next bucket

' Если элемент до сих пор не найден, то его нет в таблице.

LocateItem = HASH_NOT_FOUND

End Function

======287

Программа Bucket демонстрирует этот метод. Эта программа очень похожа на программу Chain, но она использует блоки, а не связные списки. Когда эта программа выводит длину тестовой последовательности, она показывает число проверенных блоков и число проверенных элементов в блоках. На рис. 11.4 показано окно программы после успешного поиска элемента 661 в первом дополнительном блоке. В этом примере программа проверила 9 элементов в двух блоках.

Хранение хеш‑таблиц на диске

Многие запоминающие устройства, такие как стримеры, дисководы и жесткие диски, могут считывать большие куски данных за одно обращение к устройству. Обычно эти блоки имеют размер 512 или 1024 байта. Чтение всего блока данных занимает столько же времени, сколько и чтение одного байта.

Если имеется большая хеш‑таблица, записанная на диске, то этот факт можно использовать для улучшения производительности. Доступ к данным на диске занимает намного больше времени, чем доступ к данным в памяти. Если сразу загружать все элементы блока, то можно будет прочитать их все во время одного обращения к диску. После того, как все элементы окажутся в памяти, их проверка может выполняться намного быстрее, чем если бы пришлось их считывать с диска по одному.

Если для чтения элементов с диска используется цикл For, то Visual Basic будет обращаться к диску при чтении каждого элемента. С другой стороны, можно использовать оператор Visual Basic Get для чтения всего блока сразу. При этом потребуется всего одно обращение к диску, и программа будет выполняться намного быстрее.

Можно создать тип данных, который будет содержать массив элементов, представляющий блок. Так как во время работы программы нельзя изменять размер массива в определенном пользователем типе, то необходимо заранее определить, сколько элементов сможет находиться в блоке. При этом возможности изменения размеров блоков ограничены по сравнению с предыдущим вариантом алгоритма.

Global Const ITEMS_PER_BUCKET = 10 ' Число элементов в блоке.

Global Const MAX_ITEM = 9 ' ITEMS_PER_BUCKET - 1.

Type ItemType

Value As Long

End Type

Global Const ITEM_SIZE = 4 ' Размер данных этого типа.

Type BucketType

Item(0 To MAX_ITEM) As ItemType

End Type

Global Const BUCKET_SIZE = ITEMS_PER_BUCKET * ITEM_SIZE

Перед тем, как начать чтение данных из файла, он открывается для произвольного доступа:

Open filename For Random As #DataFile Len = BUCKET_SIZE

=========288

@Рис. 11.4. Программа Bucket

Для удобства работы можно написать функции для чтения и записи блоков. Эти функции читают и пишут данные в глобальную переменную TheBucket, которая содержит данные одного блока. После того, как данные загружены в эту переменную, можно выполнить поиск среди элементов этого блока в памяти.

Так как при произвольном обращении к файлу записи нумеруются с единицы, а не с нуля, то эти функции должны добавлять к номеру блока в хеш‑таблице единицу перед считыванием данных из файла. Например, нулевому блоку в хеш‑таблице будет соответствовать запись с номером 1.

Private Sub GetBucket(num As Integer)

Get #DataFile, num + 1, TheBucket

End Sub

Private Sub PutBucket(num As Integer)

Put #DataFile, num + 1, TheBucket

End Sub

Используя функции GetBucket и PutBucket, можно переписать процедуру поиск в хеш‑таблице для чтения записей из файла:

Public Function LocateItem(Value As Long, _

bucket_probes As Integer, item_probes As Integer) As Integer

Dim bucket As Integer

Dim pos As Integer

item_probes = 0

' Определить, к какому блоку принадлежит элемент.

GetBucket Value Mod NumBuckets

bucket_probes = 1

' Поиск элемента или пустой ячейки.

For pos = 0 To MAX_ITEM

item_probes = item_probes + 1

If TheBucket.Item(pos).Value = UNUSED Then

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

Exit Function

End If

If TheBucket.Item(pos).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

' Проверить дополнительные блоки

For bucket = NumBuckets To MaxOverflow

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

GetBucket bucket

bucket_probes = bucket_probes + 1

For pos = 0 To MAX_ITEM

item_probes = item_probes + 1

If TheBucket.Item(pos).Value = UNUSED Then

LocateItem = HASH_NOT_FOUND ' Элемента нет.

Exit Function

End If

If TheBucket.Item(pos).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

Next bucket

' Если элемент все еще не найден, его нет в таблице.

LocateItem = HASH_NOT_FOUND

End Function

Программа Bucket2 аналогична программе Bucket, но она хранит блоки на диске. Она также не вычисляет и не выводит на экран среднюю длину тестовой последовательности, так как эти вычисления потребовали бы большого числа обращений к диску и сильно замедлили бы работу программы.

============290

Так как при обращении к блокам происходит чтение с диска, а обращение к элементам блока происходит в памяти, то число проверяемых блоков гораздо сильнее влияет на время выполнения программы, чем полное число проверенных элементов. Для сравнения среднего числа проверенных блоков и элементов при поиске элементов можно использовать программу Bucket.

Каждый блок в программе Bucket2 может содержать до 10 элементов. Это позволяет легко вставлять элементы в блоки до тех пор, пока они не переполнятся. В реальной программе следует попытаться поместить в блок максимально возможное число элементов так, чтобы размер блока оставался при этом равным целому числу кластеров диска.

Например, можно читать данные блоками по 1024 байта. Если элемент данных имеет размер 44 байта, то в один блок может поместиться 23 элемента данных, и при этом размер блока будет меньше 1024 байт.

Global Const ITEMS_PER_BUCKET = 23 ' Число элементов в блоке.

Global Const MAX_ITEM = 22 ' ITEMS_PER_BUCKET - 1.

Type ItemType

LastName As String * 20 ' 20 байт.

FirstName As String * 20 ' 20 байт.

EmloyeeId As Long ' 4 байта (это ключ).

End Type

Global Const ITEM_SIZE = 44 Размер данных этого типа.

Type BucketType

Item(0 To MAX_ITEM) As ItemType

End Type

Global Const BUCKET_SIZE = ITEMS_PER_BUCKET * ITEM_SIZE

Размещение в каждом блоке большего числа элементов позволяет считывать больше данных при каждом обращении к диску. При этом в таблице также может быть больше элементов, прежде чем будет необходимо использовать дополнительные блоки. Доступ к дополнительным блокам требует дополнительных обращений к диску, поэтому следует по возможности избегать его.