until -n(/t in [A.. Z, 0.. 9]); if fc >. fcl then fcl := fc else repeat [fcl] fcl := fcl-1 until fcl = fc; pack{a,\,id); search; end else

begin {проверка на кавычку или комментарий] if /I then

repeat write{fX); get(J)

until /t = else if /t = { then

repeat write{f\); get(J)

until /Г = } ; wnVcC/t);

.end end ;

writeln; get(j) end ; 13: page; printable end .

Программа 4.8. Построение таблицы перекрестных ссылок с использованием

функций расстановки.

опробирование. Отметим, что для эффективной работы существенно, чтобы размер таблицы был простым числом.

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

for i := О to /? do tii].key := free;

while -neofif) do.

hin if c4 then n 0;

П :== n+l; wi7e(n:c3); {следующая трока\

writeif );

while -[eohfj) do

begin {просмотр непустой строки) if /t in [A.. Z] then begin :== 0;

repeat if < cl then

begin к fc+1; a[k] := /f; end ;

. .--write{f\); gexij+

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

4.6.3. Анализ метода прео6разован1<!я ключа

Щ Очевидно, что в наихудшем случае включение и поиск при пользовании метода расстановки будут иметь очень плохие характеристики. Ведь вполне может быть, что аргумент поиска будет таким, что все пробы будут попадать как раз на 1анятые места и пропускать нужные (или свободные). В самом деле, тому, кто использует метод расстановки, нужно свято верить в теорию вероятностей. Всё, в чем мы хотим быть уверенным ; - это что в среднем число проб мало. Следующие вероятностные рассуждения показывают, что оно даже очень мало.

Вновь предположим, что все возможные ключи равновероятны и функция расстановки Н равномерно рассеивает их по всему интервалу индексов. Затем предположим, что нужно вставить ключ в таблицу размером п, которая уже содержит k элементов. Вероятность попадания на свободное место с первого раза в этом случае равна 1 - k/n. Одновременно Sto есть вероятность pi того, что потребуется только одно сравнение. Вероятность, что понадобится ровно одна вторая проба, равна вероятности конфликта при первой попытке, умноженной на вероятность попадания на свободное место в следующий раз. В целом мы получаем вероятность pi того, что включение потребует i проб:

k п - k

Р^ - п n-l

k k - 1 n - k

3 - 1 и - 2

k- 1 k-2 k - i+2 n-k

n n-l n - 2 n~:i + 2 n - i+\

(4.93)

Следовательно, среднее значение числа проб, требующихся при вставке (&+ 1)-го ключа, равно ft+i

I /fc I 14 (1 fe- I *-2 I n+i

(4.94)

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

т т

(4.95)

где Я„=1+4+-- - гармоническая функция. Функ-

цию Нп можно аппроксимировать следующим образом: s ln(n) + Y, где -у - эйлерова константа. Если, кроме того, в (4.95) т/{п+- 1) заменить на а, то мы получим

Е^{1п{п+1)~[п{п-т+1)) =

где а приблизительно равно отнощению занятой и имеющейся памяти, называемому коэффициентом заполнения; а = О предполагает пустую таблицу, а = n/(n-f-1) -заполненную таблицу. Среднее значение Е числа проб при поиске или включении случайно выбранного ключа как функции от коэффи циента заполнения а приведено в табл. 4.6.

Таблица 4.6. Среднее значение числа проб как функция от коэффициента загрузки

а Е

0,1 1,05

0,25 1,15

0.5 1,39

0,75 1,85

0,9 2,56

0,95 3,15

. 0,99 4,66 .