Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 41
Текст из файла (страница 41)
г[1 = [, гА = К. О[ КЕТ Е00 3:5 02 01ВК Е00 Оьй С1. )(е~йоянние. 1+- А(К) +1. С2. Есть ли список7 Переход к СО, если ТАВ1.ЕИ луст. .а жх~. Выход, есян К = КЕХИ, Переход к С5, если ьХМК И = О. С4. Пе ехо и сл ю емк И,~хр ~ Выход, если К = КЕХИ. Продвижение при ьХМК И ф О. С5. Поиск и стого л. ХХ+-  — 1. Повторять, пока ТЯВКАЯ Ы) пуст. Выход, если не осталось пустых узлов. 1.ХМКИ +- Л. 1+- 11, Обновление В в памяти. Сб. Вставка нового ключа. Х.ХМКИ < — О.
КЕХИ +- К. $ Время работы программы зависит от следующих параметров; С вЂ” число проверенных во время поиска узлов таблицы; А — [первая проверка обнаружила занятый узел); и' — (поиск был успешен); Т вЂ” количество элементов таблицы, проверенных при поиске пустого пространства. Здесь 3 = 31 + 32, где 51 = 1 прн успешной первой попытке. Общее время работы поисковой фазы программы С равно (7С + 4А + 17 — ЗЗ + 251) а, а вставка нового ключа при 5 = О требует дополнительного времени (ЯА + 4Т + 4) а.
Предположим, что в начале работы программы в таблице содержалось )У ключей, и введем а = й(/М = коэффициент заполнения таблицы. (14) Тогда среднее значение А при неудачном поиске, очевидно, равно о, если хешфункция случайна; в упр. ЗО доказывается, что среднее значение С длн неудачного поиска равно 1 /1 2 хм 2;Ух етя 1 2о С.=1+ ~~1+ ~' 1- — ~=1+ «~Ц м1 м~ 4 (1о) 62 ЯТАЕТ 64 66 67 66 62 16 11 12 16 14 16 4Н 16 17 18 12 26 бн 21 22 28 24 26 26 27 26 бн 29 Х.ОХ К ЕМТА О 01У =Н= ЗТХ *+1(Ог2) ЕИТ1 * ХМСХ 1 ЫА К 1.02 ТАВ(.Е, 1(Х.ХМК) 32М ЗР СИРА ТАВЕЕ„1(КЕУ) ЛЕ ЗОССЕЗЯ 122 ЯГ ЕМТ1 0,2 СИРА ТАЯХ,Е,1(КЕУ) дЕ БОССЕЗЗ Ы2 ТАВХЕ,1(11МК) 12МЕ 4В 002 й ОЕС2 1 Х.ОХ ТАВ1Е„2 ХХММ ь-2 122 ОУЕВРЬОМ ЗТ2 ТАВЕЕ,1(01ИК) ЕИТ1 0,2 ЗТ2 й ЗТЕ ТАВЕЕ,1(ЕХМК) ЗТА ТАВЬЕ,1(КЕУ) 1 1 1 1 1 1 1 1 1 А А А — 51 С вЂ” 1 С вЂ” 1 С вЂ” 1 С вЂ” 1 — 52 С вЂ” 1 — 52 А — 5 у у у А — 5 А — 3 А — 5 А — 5 1 — 5 1 — 3 Следовательно, если таблица заполнена наполовину, среднее числа проб, выполняемых прн неудачном поиске, составляет около -'(е+ 2) 1.18.
И даже еслн таблица заполнена полностью, среднее количество проб при вставке последнего злемента равно всего лишь -'(е + 1) ы 2.10. Стандартное отклонение также невелико (что показано в упр. 40). Приведенные статистические выкладки показывают, что при случайной хеш-функция сянскн остантлсл короткими, хотя елеориглм допрсхаетв нх "срастание ". Конечно. С может оказаться равным даже Х, если функция плоха нли вы -- исключительно невезучий человек... При успешном завершении поиска А всегда равно 1. Среднее количество проб можно вычислить путем суммирования величин С + А по первым Х неудачным поискам и деления на Х в предположении, что все ключи равновероятны.
Таким образом, получаем следующее среднее количество проб прн случайном успешном поиске: А„~1 М1 8Х~О И! М) 4 И ет — 1 — 2а а + —. 8а 4' (16) Даже если таблица будет полностью заполненной„ в среднем потребуется только 1.80 пробы для нахождения элемента! Аналогично (см. упр. 42) среднее значение 51 равно 81,ч = 1 — ~ ((А' — 1'~М) ы 1 — з (17) т — (неудачный поиск); Х(Х вЂ” 1) С' = 1+ — 1+ 2Мт Аг-1 См =1+ — ы1+ 2 (18) (успешный поиск). 2 (19) Это, пожалуй, не слишком большое улучшение по сравнению с (15) я (16), чтобы прибегать к такому изменению алгоритма.
На первый взгляд может показаться, что шаг С5 незффективен, поскольку поиск пустой позиции на нем осуществляется последовательно. Но в действительности общее количество проб на шаге Сб при построении таблицы никогда не будет превышать количества злементов в таблице; значит, в среднем мы делаем не более одной такой пробы на вставку. В упр. 41 доказывается, что при случайном неудачном поиске Т т ае". Можно модифицировать алгоритм С так, что никакие два списка не будут "срастаться", но тогда придется прибегнуть к перемещению записей. Напрнмер, рассмотрим ситуацию, представленную на рнс.
40, непосредственно перед вставкой ВЕКЕ в позицию 9. Чтобы списки оставались раздельными, необходимо переместить г1ЕЕ, а для етого нужно найти узел, указывающий на Р1ЕЕ. Решить вту проблему можно, используя не двусвязный список, а хеширование РХЕЕ н поиск в его списке, как было предложено Д. Э. Фергюсоном (О. К. гегуиоп), поскольку списки невелики по размеру. В упр, 34 показано, что среднее количество проб в случае раздельных списков уменьшаегся до С другой стороны, Батлер Лэмпсон (Впт1ег Еашрэотт) заметил, что большая часть пространства, в действительности занятая ссылками, может быть сэкономлена при использовании метода цепочек, если избавиться от "срастания" списков. Это позволяет получить интересный алгоритм, обсуждающийся в упр.
13. Метод Лэмпсона вводит дополнительный бит в каждый элемент, слегка уменьшая прн этом среднее количество проб, которые необходимы при неудачном поиске: с (18) до (18') Раздельные цепочки, показанные на рис. 38, могут использоваться при Ат > М; и, таким образом, проблема переполнения снимается. При срастания списков (см. рис. 40 и алгоритм С) можно поместить переполняющие элементы во вспомогательный пул памяти; Л.
Гтоиба (Е, 6шЬаэ) доказал, что среднее количество проб при вставке (М + Е+ 1)-го элемента составляет (1/2М+ -') ((1+ 2/М) м — 1) + т. Однако обычно предпочтительнее использовать альтернативную схему, прн которой первые вызывающие коллизию элементы помещаются во вспомогательную область памяти; в таком случае списки будут "срастаться" только при заполнении вспомогательной области (см. упр. 43).
Разрешение коллизий методом открытой адресации. Другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы одну за одной до тех пор, пока не будет найден ключ К или пустая позиция. Идея заключается в формулировании правила, согласно которому по данному ключу К определяется "пробная последовательность", т.
е. последовательность позиций таблицы„которые должны быть просмотрены при вставке или поиске К. Если при поиске К согласно определенной этим ключом последовательности встречается пустая позиция, можно сделать вывод о том, что К в таблице отсутствует (поскольку та же последовательность проверок должна выполняться при каждом поиске К), Этот общий класс методов назван открмтаой адресацией [см. %. Ж. Рететэоп, ШМ,7. Вгвеагс)т й 12еге)ортвпе 1 (1937), 130-146). Простейшая схема открытой адресации, известная как линейное исслеттвваииа, использует цикдическую последовательность проверок Ь(К), )т(К) — 1, ..., О, М вЂ” 1; М вЂ” 2, ..., )т(К) + 1 (20) и описывается следующим образом.
Алгоритм 1 (Линейное исследование и всптавка). Этот алгоритм выполняет поиск данного ключа К в таблице с М узлами. Если К отсутствует в таблице и таблица не полна, ключ К будет вставлен в таблицу. Узлы таблицы обозначаются как ТАВ1.Е[т), 0 < т < М, н могут быть двух типов — п1тстпььии и занлшмми. В занятых узлах содержатся ключи КЕТЫ и, возможно, другие поля. Вспомогательная переменная Т используется для отслеживания количества занятых узлов; она рассматривается как часть таблицы и увеличивается на 1 прн каждой вставке нового ключа.
Алгоритм использует хепт-функцию Ь(К) и линейную последовательность проб (20) для адресации таблицы. Модификации этой последовательности обсуждаются ниже. Ь1. (Хеширование.) Установить 1 ~ — А(К). (Теперь О < 1 < ЛХ.) Ь2. (Сравнение.] Если узел ТАВЬЕ(П пуст, перейти к шагу Ь4. В противном случае, если КЕХИ = К, алгоритм успешно завершается. ЬЗ. [Переход к следук)щему.) Установиты' с- 1 — 1; если таперы < О, установить 1+-1+ М, Вернуться к шагу Ь2. Ь4.
(Вставка.) (Поиск оказался неудачньш.) Если Л = М -1, алгоритм завершается в связи с переполнением (условне полного заповнения таблицы полностью в данном алгоритме выглядит как Л = М вЂ” 1, а не как 1Ч = М; см. упр. 15). В противном случае установить 1Ч +- 1Ч + 1, пометить узел ТАВ~.Е(П как занятый н установить КЕТЫ +- К, $ На рнс. 41 показано, что происходит прн вставке семи ключей нашего примера с норвежскими цифрами согласно алгоритму Ь из примера с хеш-кодами 2, 7, 1, 8, 2, 8, 1; при этом последние три ключа, ГЕИ, ЗЕКЗ н БХЧ, смещены со своих начальных позиций й(К). Рне.
41. Линейная открытая адресация. Программа 1 (Линейное наследование и встнавка). Эта программа работает с ключами, занимающими полное слово; однако ключ 0 использовать нельзя, поскольку нулевое значение ключа означает, что данный узел в таблице свободен (другое решение состоит, например, в том, чтобы наложить на ключи условие неотрицательности, а пустые позиции пометить значением -1).
Размер таблицы — М (предполагается, что это простое число), а узлы таблицы ТАВЬЕ(11 имеют адреса ТАВЬЕ+ т, О < 1 < М. Для ускорения внутреннего цикла в ячейке ТАВ1.Š— 1 содержится О. В ячейке ЧАСАИС1ЕЗ хранится значение М вЂ” 1 — Ж; и, наконец, гА ьз К, г11 ат (. Для ускорения внутреннего цикла этой программы из него удалена проверка 'И с 0", так что в нем остались только существенные части шагов 12 и ЬЗ. Общее время работы программы на фазе поиска составляет (7С+ ЗЕ+ 21-48)и, а вставка в случае неудачного поиска добавляет к этой величине еще Зн. 01 ЗТАЯТ ЬОХ К 1 ив р~ 00 ЕЙТА О 1 00 01Ч =И= 1 04 ЗТХ а+1(0:2) 1 дд ЕИТ1 ь 1 1+- А(К). 06 ЬОА К 1 07 ЗИР 2У 1 1ИС1 И+1 РЕС1 1 СИРА ТАВ1.Е,1 ЛЕ ЯОССЕЯЯ ЫИ ТАВЕЕ,1 3ХНХ ЯВ 11Н ЯВ ЕРХ УАСАИСХЕЯ ЛХХ 07ЕЕРЕОЫ а8 Вн ОУ зн 10 2Н 11 1Х 13 14 15 4Н 16 ЬЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
