Сравнение методов рандомизации

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

ft = все ключи

где Тг — время, необходимое для вычисления адреса алгоритмом рандомизации, Та — среднее время доступа при обращении к данным на вспомогательной памяти, nk — число синонимов, которые необходимо проверить, прежде чем ключ, равный k, будет найден, и JV — общее количество ключей.

В большинстве практических случаев второй член этого выражения значительно больше, чем первый (Tr<^Ta\ -^zLnb>\). Однако не все данные выбираются с одинаковой частотой. Если pk — вероятность обращения к ключу, равному то в этом приближении ipknk — взвешенное среднее количество выборок — должно быть минимизировано для оптимизаций времени счета. Это означает, что доступ к большинству активных данных должен осуществляться с первой попытки (выборки), либо потому, что они не имеют синонимов, либо потому, что они являются первыми членами в цепочках синонимов. Поэтому имеет смысл либо формировать файл так, что наиболее часто выбираемые данные загружаются первыми, либо реорганизовать файл, согласно этому принципу, после сбора статистических данных о частотах обращений к отдельным данным. Это уменьшит значение (ik для больших pk [13].

k=Bce ключи

Ключ	Вероятность обращения	Порядок загрузки	Адрес блока	Количество Выборок
-4	0:05	1	4	1	0.05
13	0.05	2	2	t	0.05
17	0.10	3	6	1	0.10
24	0.20	4	3	2	0.40
34	0.10	5	1	1	0.10
45	0.20	6	5	6	1.00
65	0.10	7	10.	%	0.10
74	0.05	8	8	1	0.05
88	0.15	9	0	1	0.15

На рис. 9.11 и 9.12 проведенные рассмотрения иллюстрируются простыми примерами. Здесь используются числовые ключи, а адрес блока вычисляется как остаток от деления значения ключа на 11. Синонимы размещаются в следующем пустом блоке. Если файл сформирован путем загрузки данных в порядке возрастания значений ключей, как это показано на рис. 9.11, то среднее количество выборок равно 2.00. Однако если данные запоминаются в течение периода формирования файла в порядке уменьшения их относительных частот обращений, как показано на рис. 9.12, то среднее количество выборок можно снизить до 1.35, обеспечив тем самым экономию процессорного времени на 33%.

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

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

Эффективность алгоритмов рандомизации и хеширования зависит также от коэффициента заполнения, т. е. отношения количества в конце концов запомненных данных к количеству доступных ячеек памяти. Когда коэффициент близок к 1, то весьма вероятно вхождение синонимов. Если все ключи могут использоваться с равной вероятностью, т. е. Pk~j[» то среднее количество выборок при равномерно рандомизирующей функции может быть хорошо аппроксимировано выражением (см. также рис. 5.11) [14].

Поиск разумного компромисса между неиспользуемым объемом памяти и дополнительным машинным временем входит в функции организатора файла или администратора базы данных, если файл создается в большой и сложной базе данных (см. разд. 9.7.6). Если новые данные постоянно добавляются к файлу, то этот человек должен решить, когда целесообразно проводить сеансы реорганизации данных, обеспечивающие уменьшение среднего времени доступа [15].

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