AOP_Tom3 (1021738), страница 153
Текст из файла (страница 153)
(Например, если М простое число, то Ьв(К) может быть любой величиной от 1 до М вЂ” 1 включительно; или, если М = 2'", Ьз(К) может быть любым нечесаным числом от 1 до 2"' — 1.) П1. [Первое хеширование.] Установиты +- 61(К). 1У2. (Первая проба.] Если ТАВ1.Е[П пуст, перейти к шагу ТУ6. В противном случае, если КЕТ[П = К, алгоритм завершается успешно. 1УЗ. [Второе хеширование.] Установить с в- Ьа(К). В4. [Переход к следующему.) Установиты +- 1 — с; если после этого 1 ( О, установить 1+- э + ЛЬ Т15. [Сравнение.) Если ТАВЬЕ[П пуст, перейти к шагу 1У6.
В противном случае, если КЕТ[П = К, алгоритм завершается успешно; иначе — вернуться к шагу П4. П6. [Вставка.] Если У = М вЂ” 1, выполнение алгоритма прекращается в связи с переполнением. В противном случае установить гУ в- Л1 + 1, пометить узел ТАВЬЕ[з) как занятый и установить КЕТЫ +- К. $ (25) с двойным хешированием), Поскольку эта 1. она представлена здесь без комментариен. Программа 1) (Рткрытоя адресация программа очень похожа на программу В программе г12 = с — 1.
01 ЯТАНТ ЕОХ К ОЯ ЕМТА 0 ОЮ 017 =М= 04 ЯТХ в+1(0:2) Об ЕМТ1 ь Об ЮХ ТАВОТЕ,1 07 СМРХ К Об ЗЕ ЯОССЕЯЯ 00 дХЕ 4Р А — 51 А — 51 А — 51 А — 51 А — 51 С вЂ” 1 С вЂ” 1 В С вЂ” 1 10 ЯНАХ 11 017 1О ЯТХ 1У ЕМТ2 Ц 1.0А 1Б ЗН ОЕС1 10 д1ММ !7 1МС1 10 СМРА 5 =М-2= в+1(0:2) К 1,2 9+2 М ТАВЕЕ,1 Дня вычисления Ь (К) было предложено несколько различных вариантов. Если М вЂ” простое числа и !И(К) = К шос1 М, можно положить !гт(К) = 1+ (Кшоб (М вЂ” 1)); однако, поскольку ЛХ вЂ” 1 четно, была бы лучше положить Ьз(К) = 1+ (К пюб (ЛХ вЂ” 2)).
Это приводит к мысли о таком выборе М, что ЛХ и М вЂ” 2 были "простыми близнецами" наподобие 1021 и 1019. Кроме тога, можно взять Ьз(К) = 1+ ((К/М) шоб (М вЂ” 2)) в связи с тем, что частное (К/ЛХ) молсет быть получено в регистре как побочный резу.льтат вычисления !н (К). Если М = 2 и используется мультипликативное хеширование, !гт(ХХ) может быть вычислена методом простого сдвига на т дополнительных битов влево с выполнением операции "ИЛИь с 1, так чта к последовательности команд (5) необходимо добавить следующее. ЕМТА 0 Очистить гА Бьн ш Сдвинуть гАХ на тп бит влево.
(24) Ок 1 гА < — гАу! 1. Эти операции выполняются быстрее метода деления. В каждом из предложенных выше метадон !В(К) и Ьо(К) существенно независимы — в том смысле, что для различных ключей вероятность совпадения Ь~ и Ьз пропорциональна 1/Мэ, а не 1/М. Эмпирические тесты показывают, что число проб в алгоритме В с независимыми хеш-функциями неотличимо от числа проб, требующихся при случайной вставке ключей в таблицу; в этой ситуации практически отсутствует "окучивание", или "кластеризация", как в алгоритме Е.
Можно также допустить зависимость 6з(К) от 6~(К), как было предложено Гари Кноттом (Сагу Кпом) в 1968 году; например, при простом М можно положить ~2( ) если !и(К) = 0; М вЂ” Ь,(К), если Ь!(К) > О. Этот метод выполняется быстрее повторного делении, однако он вызывает определенную вшоричную кластеризацию, что приводит к небольшому увеличению числа проб из-за повышения вероятности того, что два или несколько ключей пойдут по одному и тому же пути. Выведенные ниже формулы могут использоваться для определения того, превышает ли выигрыш во времени хеширования потери времени на дополнительных пробах.
Алгоритмы Е и В очень похожи, однако между ними найдется достаточно различий, чтобы было полезно сравнить время работы соответствующих И1Х-программ. 12 1Е ВОССЕВВ С - 1 20 ООХ ТАВОТЕ,1 С вЂ” 1 — 52 21 ЮХИЕ ЗВ С вЂ” 1 — 52 22 4Н СОХ ЧАСАИС1ЕБ 1 — 5 22 ЛХЕ ОУЕКРЕОИ 1 — 5 ОЕСХ 1 1 — 5 ЯТХ ЧАСАИС165 1 — 5 ООА К 1 — 5 ЯТА ТАВ1.Е,1 1 — 5 ! 24 25 26 27 Счетчики частот А, С, 51, 52 здесь имеют тот же смысл, что и в программе С, приведенной выше. Еще одна переменная, В, в среднем примерно равна (С вЂ” 1)/2 (если ограничить диапазон значений Ья(К) да, скажем, 1 < Ьз(К) < М/2, В уменьшится до (С вЂ” 1)/4; такое увеличение скорости, вероятно, не компенсируется заметным увеличением числа проб). Если в таблице )Ч = аМ ключей, среднее значение А, конечна, равно а при неудачном поиске и А = 1' — в случае поиска успешного.
Как и в алгоритме С, среднее значение 51 при успешном поиске составляет 1 — -'((и†1)/М) я~ 1- $о. Среднее число проб трудно установить точно, однако эмпирические тесты показывают хорошую согласованность с формулами, выведенными ниже для "равномерного исследования' при независимых Ьс(К) и Ьз(К): (1 — а) ' (неудачный поиск), (26) М+1 — Х АХ+ 1 См = (Нмч~ — Нмчс-м) — а ~ 1п(1 — а) (успешный поиск). (27) 1Ч Если Ьз(К) зависит от 10(К) согласно (25), вторичная кластеризация увеличивает (26) и (27) до Л4+ 1 Дт См = — +Н вЂ” Н -О(М ') М+1 — и М+1 - (1 — а) ' — а — 1п(1 — о), (28) -1 См — 1+Нмьс Нмз-~-м (Нм-.с Нм-,~ — л)/57+С(Н ) 2(М+ 1) 1 1п(1 а) за (29) ЕИИ2 1-М,1 с+- М вЂ” О 11ИЕ в+2 (30) ЕИТ2 0 Если1= О, сс — 1.
Программа П требует в целом 8С+ 19А+ В+ 26 — 135 — 1751 единиц времени; моди- фикация (30) позволяет сохранить около 15(А — 5Ц - 7.5а времени при успешном завершении поиска. В данном случае вторичная кластеризация предпочтительнее независимого двойного хеширования. (см. упр. 44). Заметим, что при заполнении заблипы данные значения См стремятся к Нмзл — 1 и Нмт, —; соответственно; зто существенно лучше, чем прн 1 использовании алгоритма Е, но не так хорошо, как в методе цепочек.
Поскольку каждая проба в алгоритме Е отнимает немного меньше времени, двойное хеширование дает выигрыш талька прн заполненной таблице. На рис. 42 сравниваются средние значения времени работы программ Е, 0 и модифицированной программы Р (эта модификация влечет за собой вторичное окучивание; сама модификация сводится к замещению медленного вычисления Ьз(К) в строках 10-13 следующими командами. 40и 3 и Зоо и $ 20о Ж гби Ои 0 0.1 0 2 О.З 0.4 0.5 О.б 0 7 0.8 0.9 1.О Коэффициент эаполиеииоети, о = А7М Рис. 42.
Время успешного поиска трех схем открытой адресации. На двоичном компьютере можно было бы увеличить скорость вычисления йэ (К) другим путем — заменив (если М вЂ” простое число, болыпее, чем, скажем, 512) строки 10 — 13 строками А14Р =511= гА е — гА шог1 512. 3ТА и+1(0:2) (31) ЕиТ2 и е е-гА+1. Эта идея (предложенная Беллом (Ве!1) и Каманом (Кашап), САСМ 13 (1970), 675 — 677, которые независимо открыли алгоритм 1)) позволяет избежать вторичной кластеризации без затрат на повторное деление. Для улучшеяия алгоритма Ь было предложено много других последовательностей проб, но ни одна из них не превосходит алгоритм П (за исключением, возможно, метода, описанного в упр. 20).
Используя относительный порядок ключей, можно уменьшить среднее время работы при неудачном поиске согласно алгоритму Ь или !) до среднего времени работы при успешном поиске (см. упр. 66). Эта технология может с успехом применяться для решения задач, в которых неудачный поиск — обычное явление, более частое, чем поиск успешный; например, ТЕХ использует такой алгоритм при поиске исключений из своих правил переноса. Изменение Брента. Ричард П. Брент (ЖсугаЫ Р. Вгепб) открыл такой способ модификации алгоритма П, при котором среднее время успешного поиска остается ограниченным при заполнении таблицьь Его метод (СЛСМ 16 (1973), 105 — 109] основан на том факте, что обычно успешный поиск встречается горазда чаще вставок, а потому его предложение сводится к переносу основной работы на вставку элемента путем такого перемещения записей, чтобы уменьшилось ожидаемое время выборки.
Например, на рис. 43 показано, сколько раз каждый идентификатор встречался в типичной процедуре РЬ/1. Эти данные указывают на го, что компилятор РЬ/1, который использует хеш-таблицу для хранения имен переменных, будет обращаться к ней за многими именами пять и более раз, вставляя их всего однажды. В подобном исследовании Белл и Каман обнаружили, что компилятор СОВОЬ использовал свой 25 1а о ы ь ы ы Н т ь ы ы ы ы ы ыь в $ М Н ь ы нь ы ь п н ы й ы ~ ч ыо Рнс.
43. Количество поисков имен переменных компилятором в типичном етучве. Имена перечислены слева направо в порядке нх первого появлення в программе. табличный алгоритм при компиляции 10988 раз, в то время как было сделано только 735 вставок в таблицу; следовательно, на одну вставку приходилось около 14 успешных поисков. Иногда таблина создается только один раз (например, таблица символов кодов операций в ассемблере) и используется исключительна для получения нз нее данных.
Идея Брента заключается в изменении процесса вставки в алгоритме Р, как показано ниже. Предположим, что при неудачном поиске были проверены ячейки ро, рм ..., р... ре, где рх —— (Ь1(К) — ХЬг(К)) лют М н ТАВ1.Е[р~] пуст. Если 1 < 1, вставляем К в позицию рн как обычно; однако, если 1 > 2, вычисляем се = Ьт(Ке), где Ке = КЕТ[ре], и смотрим, свободен ли узел ТАВЬЕЦро — со) шоб М]. Если зто так, помещаем в него ТАВЬЕ[ро], а затем вставляем К в позицию ро. Это приводит к увеличению времени выборки Ко на один шаг, но время выборки К уменьшается на 1 > 2 шагов, что приводит к общему выигрышу во времени выборки. Лналогично, если узел ТАВЬЕЦро — со) шоб М] занят н 1 > 3, проверяем узел ТАВ1.ЕЦре — 2со) пюб М]; если он также занят, вычисляем с, = Ьт(КЕУ[р,) ), провернем ТАВ|ЕЦро — с~) шай ЛХ] и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
