Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 43
Текст из файла (страница 43)
Еще одна переменная, В, в среднем примерно равна (С вЂ” 1)/2 (если ограничить диапазон значений 6э(Л ) до, скажем, 1 < 6э(К) < Лб/2, В уменьшится до (С вЂ” 1)~4; такое увеличение скорости, вероятно, не компенсируется заметным увеличением числа проб). Если в таблице Х = аМ ключей, среднее значение А, конечно, равно а при неудачном поиске и А = 1 — в случае поиска успешного. Как и в алгоритме С, среднее значение 51 при успешном поиске составляет 1 — 1!((Ж— 1) /М) ю 1 — ! а. Среднее число проб трудно установить точно, однако эмпирические тесты показывают хорошую согласованность с формулами, выведенными ниже дэя "равномерного исследования" при независимых 6л(К) и 6э(К): М+1 С!!, = ш(1-а) ! ОЕСХ 1 1 — 5 БТХ ЧАСАМСТЕБ 1 — 5 ЫА К 1 — Я БТА ТАВ1Е, 1 1 — 5 1 (неудачный поиск), (26) М+1 -! Сч ы — (Нм+! — Ил!+! !ч) лэ -а !п(1-а) (успешный поиск).
(27) 1Ч Если 6э(К) зависит от 6л(К) согласно (25), вторичная кластеризация увеличивает (26) и (27) до М+1 !Ч Сл= М+1-в М+1 — — +Нм+! — Нм+! и+С(М ') я! (1-а) '-а-1п(1-а); !Ч -! с =1+и „-н „~- — -(н„„-и „)р+о(и-) 2(М+ 1) ш 1- (п(1- а) -Аа 2 (29) (см. упр. 44).
Заметим, что при заполнении таблицы данные значения См стремятся к Нм+! — 1 и Нм+! — - соответственно; это существенно лучше, чем при ! использовании алгоритма 1.,но не так хорошо, кэк в методе цепочек. Поскольку каждая проба в алгоритме 1 отнимает немного меньше времени, двойное хеширование дает выигрыш только при заполненной таблице. На рис. 42 сравниваются средние значения времени работы программ Е, 0 и модифицированной программы 0 (эта модифиш!ция влечет за собой вторичное окучивание; сама модификация сводится к замещению медленного вычисления 6э(К) в строках 10-13 следующими комацлами. ЕММ2 1-М,1 с+- М вЂ” !. ПМХ э+2 (30) ЕМТ2 0 Если ! = О, с !- 1. Программа 0 требует в целом БС+ 19А+ В+ 26- 135-1751 единиц времени: модификация (30) позволяет сохранить около 15(А — 51) 7.5а времени при успешном завершении поиска.
В данном случае вторичная кластеризация предпочтительнее независимого двойного хеширования. бои 50и и 40и 3 зои тои 10и иО оп ОД О.З 0.4 0,5 О.б О.? 0,8 0.9 1.0 Коэффвцвевт завелвеввегтв, и = Ж/М Рнс. 42. Время успешного поиска трех схем открытей адресации. На двоичном компьютере можно было бы увеличить скорость вычисления Ат(К) другилг путем — заменив (если М вЂ” простое число, большее, чем, скажем, 512) строки 10. 13 строками АМ0 511 гА г- гА шог1 512. ЯТА и+1(0:2) (31) ЕМТ2 е с+ — гА+ 1.
Эта идея (предложенная Беллом (Ве!1) и Каманом (Кап1ап), САСЛ1 13 (1970), 675-677, которые независимо открыли алгоритм О) позволяет избежать вторичной кластеризации без затрат на повторное деление. Дчя улучшения алгоритма 1, было предложено много других последовательностей проб, но ни одна нз них не превосходит алгоритм В (за исключением, возможно, метода, описанного в упр.
20), Используя относительный порядок ключей, можно уменьшить среднее время работы прн неудачном поиске согласно алгоритму 1, нли В до среднего времени работы при успешном поиске (см, упр. 66). Эта технология может с успехом применяться для решения задач, в которых неудачный поиск — обычное явление, более частое, чем поиск успешный; например, ЧБХ использует такой алгоритм при поиске исключений нз своих правил переноса.
Изменение Брента. Ричард П. Брент (МсЬагд Р. Вгепг) открыл такой способ модификации алгоритма О, при котором среднее время успешного поиска остается ограниченным при заполнении таблицы, Его метод (САСАХ 16 (1973), 105-109] основан на том факте, что обычно успешный поиск встречается гораздо чаще вставок, а потому его предложение сводится к переносу основной работы на вставку клемента путем такого перемещения записей, чтобы уменьшилось ожидаемое время выборки.
Например, на рис. 43 показано, сколько раз каждый идентификатор встречался в типичной процедуре Р1./!. Эти данные указывают на то, что компилятор Р1,/Т, который использует хеш-табшщу для хранения имен переменных, будет обращаться к ней за многими именами пять и более раз, вставляя их всего однажды. В подобном исследовании Белл и Каман обнаружили, что компилятор СОВ01, использовал свой о т4 м и 3 1 $ 1 ь' 3 м н аИ И 8 юд И Ф 3 у у '" м ъ а м Рис. 43.
Количество поисков имен переменных компилятором в типичном случае. Имен» перечислены слева направо в порядке нх первого появления в программе. табличный алгоритм при компиляции 10988 раз, в то время как было сделано только 735 вставок в таблицу; следовательно, на одну вставку приходилось около 14 успешных поисков. Иногда таблица создается только один раз (например, таблица снмволов кодов операций в ассемблере) и используется исключительно для получения из нее данных.
Идея Брента заключается в изменении процесса вставки в алгоритме О, как показано ниже. Предположим, что прн неудачном поиске бычн проверены ячейки Ро Рт ° ° Рт-т. Рм где РХ = (61(К) Хйт(К)) пют] ЛХ н ТАВ1Е[РД пуст. Если 1 < 1, вставляем К в позицию Рм как обычно; однако, если 1 > 2, вычисляем се = Лв(Ке), где Ке = КЕТ[ро], и смотрим, свободен ли узел ТАВ1.ЕЦРе — се) пюбЛХ]. Если зто так, помещаем в него ТАВ1.Е[ро], а затем вставляем К в позицию Ро. Это приводит к увеличению времени выборки Ко на один шаг, ко время выборки А уменьшается на 1 > 2 шагов, что приводит к общему выигрышу во времени выборки.
Аналогично, если узел ТАВ|ЕЦРо — св) шод ЛХ] занят и Х > 3, проверяем узел ТАВ1.Е Цре — 2со) шот] ЛХ]; если он также занят, вычисляем ст — — Ат(ЕЕУ [Р1]), проверяем ТАВ1.ЕЦРе — гт) шот] ЛХ] и т. д. Вообще, пусть сз = Ал(КЕУ[РХ]) и р л = (РХ— йг ) гаот1 ЛХ; если для всех Х и А, таких, что ]+ А < г, узлы ТАВ1 В [Рва] заняты и еыи т > г + 1, просматриваем узлы тАВ1 е [Ре, ], тАВ1 е [Ри,-т]...., тАВ1 е [р„ь1]. Если первое пустое место оказывается в позиции Р,, м устанавливаем ТАВ1.Е[р „] +- ТАВ|Е[Р,] и вставляем К в позицию Р .
Анализ Брента показывает, что среднее количество проб на один успешный поиск уменьшается до уровней, показанных на рис. 44 на с. 883, с максимальным значением, равным приблизительно 2.49. Количество проб 1+ 1 при неудачном поиске в результате внесенных в алгоритм изменений осталось прежним; оно осталось на уровне„который определен формулой (26) и достигает т(ЛХ+ 1) при заполненности таблицы. Среднее количество вычислений функции Ьз для одной вставки составляет согласно анализу Брента о +о'+-,,о~+ . и достигает в конечном счете 6(~гтМ); количестводополнительных проб позиций таблицы после решения о том, каким образом будет производиться вставка, составляет около оз + о~ + Ззо~ + а + С усовершенствованными модификациями Брента работал Е.
Г. Маллах (Е. 6. Ма))ас1~) ]Сошр. Х 20 (1977), 137--140]; с другими результатами в атом направлении ножи з ознакомиться в работе Пазсоп Н. Ооппег апд 3, 1ап Мипго, ЯСОМР 8 (1979), 463-478. Удаления. Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задуматься о том, как они работают. Для них неприятным сюрпризом становится то, что очевидный способ удаления записей из хези-таблицы не рабошаезп.
Например, чтобы удалить ключ ЕИ на рис. 41„нельзя просто пометить этот узел в таблице как пустой, поскольку окажется потерянным другой ключ, РЕИ. (Вспомним, что и ЕИ, и РЕИ хешируются в одно н то же положение. При поиске РЕИ мы натолкнемся на пустое место, что свидетельствует о неудачном завершении поиска.) Подобная нроблелза возникает в случае использования алгоритма С из-за срастания списков; рассмотрите удаление двух ключей — Т0 и Р1ВŠ— иа рис. 40. Вообще говоря, обрабатывать удаление можно, поместив в соответствующую ячейку специальный код.
Таким образом, будет иметься три вида позиций в таблице; пустые, занятые и удаленные. При поиске ключа следует пропускать удаленные ячейки, как если бы они были заняты. В случае неудачного поиска ключ может быть помещен в первую встреченную удаленную или пустую позицию. Однако такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а значит, после длинной последовапльности вставок и удалений все свободные позиции исчезнут, а прн неудачном поиске будет требоваться М проверок! Более того, время пробы при атом увеличится. так как на шаге В4 придется проверять, не приняло ли 1 свое первоначальное значение, а чя«ло проб в случае успешного поиска возрастет с См до С~,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
