Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
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
Размещение в каждом блоке большего числа элементов позволяет считывать больше данных при каждом обращении к диску. При этом в таблице также может быть больше элементов, прежде чем будет необходимо использовать дополнительные блоки. Доступ к дополнительным блокам требует дополнительных обращений к диску, поэтому следует по возможности избегать его.
С другой стороны, если блоки достаточно велики, то они могут содержать большое число пустых ячеек. Если данные неравномерно распределены по блокам, то одни блоки могут быть переполнены, а другие — практически пусты. Использование другого варианта размещения с большим числом блоков меньшего размера может уменьшить эту проблему. Даже если некоторые блоки все еще будут переполнены, а некоторые пусты, то почти пустые блоки будут иметь меньший размер, потому они не будут содержать так много пустых ячеек.
На рис. 11.5 показаны два варианта расположения одних и тех же данных в блоках. В расположении наверху используются 5 блоков, каждый из которых содержит по 5 элементов. При этом дополнительные блоки не используются, и всего имеется 12 пустых ячеек. Расположение внизу использует 10 блоков, каждый из которых содержит по 2 элемента. В нем имеется 9 пустых ячеек и один дополнительный блок.
========291
@Рис. 11.5. Два варианта расположения элементов в блоках
Это пример пространственно‑временного компромисса. При первом расположении все элементы расположены в обычных (не дополнительных) блоках, поэтому можно быстро найти любой из них. Второе расположение занимает меньше места, но помещает некоторые элементы в дополнительные блоки, при этом доступ к ним занимает больше времени.
Связывание блоков
Можно использовать другой подход, если при переполнении блоков создавать цепочки из блоков. Для каждого заполненного блока создается своя цепочка блоков, вместо того, чтобы хранить все лишние элементы в одних и тех же дополнительных блоках. При поиске элемента в заполненном блоке нет необходимости проверять элементы в дополнительных блоках, которые были помещены туда в результате переполнения других блоков. Если множество блоков переполнено, то это может сэкономить довольно много времени.
На рис. 11.6 показано применение двух разных схем хеширования для одних и тех же данных. Вверху лишние элементы помещаются в общие дополнительные блоки. Чтобы найти элементы 32 и 30, нужно проверить три блока. Во‑первых, проверяется блок, в котором элемент должен находится. Элемента в этом блоке нет, поэтому проверяется первый дополнительный блок, в котором элемента тоже нет. Поэтому требуется проверить второй дополнительный блок, в котором, наконец, находится искомый элемент.
В нижнем расположении заполненные блоки связаны со своими собственными дополнительными блоками. При таком расположении любой элемент можно найти после обращения не более чем к двум блокам. Как и раньше, вначале проверяется блок, в котором элемент должен находиться. Если его там нет, то проверяется связный список дополнительных блоков. В этом примере чтобы найти искомый элемент нужно проверить только один дополнительный блок.
=========292
@Рис. 11.6. Связные дополнительные блоки
Если дополнительные блоки хеш‑таблицы содержит большое число элементов, то организация цепочек из дополнительных блоков может сэкономить достаточно много времени. Предположим, что имеется относительно большая хеш‑таблица, содержащая 1000 блоков, в каждом из которых находится 10 элементов. Предположим также, что в дополнительных блоках находится 1000 элементов, для которых понадобится 100 дополнительных блоков. Чтобы найти один из последних элементов в дополнительных блоках, потребуется проверить 101 блок.
Более того, предположим, что мы пытались найти элемент K, которого нет в таблице, но который должен был бы находиться в одном из заполненных блоков. В этом случае пришлось бы проверить все 100 дополнительных блоков, прежде чем выяснилось бы, что элемент отсутствует в таблице. Если программа часто пытается найти элементы, которых нет в таблице, то значительная часть времени будет тратиться на проверку дополнительных блоков.
Если дополнительные блоки связаны между собой и ключевые значения распределены равномерно, то можно будет находить элементы намного быстрее. Если максимальное число дополнительных элементов для одного блока равно 10, то каждый блок может иметь не больше одного дополнительного. В этом случае можно найти элемент или определить, что его нет в таблице, проверив не более двух блоков.
С другой стороны, если хеш‑таблица только слегка переполнена, то многие блоки будут иметь дополнительные блоки, содержащие всего один или два элемента. Допустим, что в каждом блоке должно находиться 11 элементов. Так как каждый блок может вместить только 10 элементов, для каждого обычного блока нужно будет создать один дополнительный. В этом случае потребуется 1000 дополнительных блоков, каждый из которых будет содержать всего один элемент, и всего в дополнительных блоках будет 900 пустых ячеек.
Страницы: 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, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82
