AOP_Tom3 (1021738), страница 151
Текст из файла (страница 151)
Другой подход предусматривает использование концепции "самоорганизованности", обсуждавшейся в разделе 6.1; записи могут быть упорядоченными не по значениям ключей списка, а по последнему времени обращения к ним. Для повышения быстродействия желательны большие значения М, однако в этом случае слишком многие списки будут пусты и будут зря расходовать память на содержание заголовков списков.
При небольших размерах записей можно воспользоваться следующим подходам: совместить пространства для записей с пространством для заголовков списков, отводя место для М записей и ЛХ ссылок вместо места для ?У записей н АХ + Х ссььюк. Иногда можно совершать проход по всем данным для поиска заголовков списков, которые будут использоваться, а затем при втором проходе вставлять "переполняющиек записи в пустые "щели".
Однако зачастую это непрактично или невозможно, поэтому хотелось бы иметь метод, работающий с каждой записью только раз .. при ее помещении в систему. Следующий алгоритм, предложенный в рабате Е. А. %!11[ашэ, САСМ 2,6 (Лше, 1959), 21 — 24, позволяет бьютро решить эту задачу. Алгоритм С (ХХоиск и всшаека е хеш-шаблице с цепочками). Этот алгоритм (рнс. 39) ищет данный ключ К и таблице из М узлов. Если К в таблице отсутствует, а таблица не заполнена, К вставляется в таблицу.
Узлы таблицы обозначаются через ТАЕТЕ[И, О < 1 < АХ, и могут быть двух различных типов — пустмхчи н заняшммн. В занятом узле содержатся поле ключа КЕУИ, поле ссылки Е16К[П и, возможно, другие поля. Алгоритм использует хеш-функцню Ь(К). Применяется также вспомогательная переменная Л для упрощения поиска пустых мест; если таблица пуста, Л = АХ + 1; по мере выполнения вставок всегда будет оставаться истинным утверждение, что узлы ТАЕТЕ [ХЧ заняты для всех Х в диапазоне Л < Х < М. По соглшпению узел ТАВьЕ [Оз всегда пуст. С1. [Хеширование.) Установиты < — й(К) + 1.
(Теперь 1 < 1 < М.) С2. [Есть лн список?] Если ТАВЬЕ Я пуст, перейти к шагу С6. (В противном случае ТАЕТЕ [П занят и мы присту пнм к поиску в списке, начинающемся в этом узле.) СЗ. [Сравнение.) Если К = КЕУ [П, алгоритм успешно завершается. С4. [Переход к следующему.) Если /.16К[П ~ О, установнты +- Е1КК [П и верну.ться к шагу СЗ. Сб. [Поиск пустого узла.) (Поиск был неудачным, и необходимо найти пустое место в таблице.) Уменьшать Л адин или более раз, пока нс будет найдено такое значение, при котором узел ТАВЕЕ[Л) будет пуст.
Если Л = О, алгоритм завершается в связи с переполнением (свободных узлов больше нет); в противном случае установить Е1ИК[П з- Л, 4 е- Л. Пересезяекяе зззершеяяе Рис. 39. Поиск и вставка в хеш-таблнце с цепочками. Сб. [Вставка нового ключа.) Пометить узел ТАВЗЕН) как занятый с КЕУ[П +- К и Е1МКП) е- О, 1 Алгоритм позволяет объединить несколько списков, позтому записи не нужно перемещать после вставки в таблицу. Например, взгляните на рис.
40, на котором ЯЕКБ попадает в список, содержащий ТО и Е1ЕЕ, поскольку последний уже был вставлен в позицию 9. ТАВЬЕ[Ц; ТАВЬЕ [21: ТАВЬЕ[33: тввье[П: тАВье[51: ТАвье[51. ТАвье[т1: ТАВЬЕ[83: ТАВЬЕ[91: Рис. 40. еСросшнесяз цепочки. Для сравнения алгоритма С с другими алгоритмами втой главы можно написать следующую М11-программу.
Выполненный анализ показал, что цепочки, как правило, коротки, и приведенная программа написана с учетом зтого факта. Программа С (Поиск и вставка в хеш-зпабеице с цепочками). Для удобслаа считаем, что ключи состоит из трех байтов, а узлы имеют следующий вид: Пустой узел Занятый узел В качестве размера таблицы М выбирается простое число; ТАВЕЕ[[] хранится по адресу ТАШ.Е+ 1.
г11 = [, гА = К. 01 КЕТ ЕЦО Еп б 02 Е1ИК ЕДУ О: 2 сс х. к +- И(К) + 1. С2. Есть ли список? Переход к СО, если ТАВРЕЫ пуск. ссз. ' Выход, если К = КЕТЫ. Переход к С5, если ь1МКЫ = О. С4. Пе ех ксле ю ем. сх. с Выход, есчи К = КЕТЕ]. Продвижение при 11МК Ы Ф О, Св, Поиск п стога зла. Повторять, пока ТАВьЕ()к) пуст. Выход, если не осталось пустых узлов. 11МКП) +- В.
1 к — В. Обновление К в памяти. С6. Вставка нового ключа. 11МКЫ +- О. КЕТЫ к- К, ! Время работы программы зависит от следующих параметров: С вЂ” число проверенных во время поиска узлов таблицы; А — (первая проверка обнаружила занятый узел); 5 — (поиск был успешен): Т вЂ” количество элементов таблицы, проверенных при поиске пустого пространства. Здесь 5 = 51+ 52, где 51 = 1 прн успешной первой попытке. Общее время работы поисковой фазы программы С равна (7С + 4А+ 17 — 35+ 251)и, а вставка нового ключа при 5 = О требует дополнительного времени (БА + 4Т+ 4) и.
Предположим, что в начале работы программы в таблице содержалось 11к ключей, и введем а = )х'/М = коэффициент заполнения таблицы. (14) Тогда среднее значение А при неудачном поиске, очевидно, равно а, если хеш- функция случайна; в упр. 39 доказывается, что среднее значение С для неудачного поиска равно 1 у,' 2 ' л' 2Нхх~ езс — 1 — 2а С,' =1+- ~()+ — ) — 1 — — ) =1+ ' 41к, М) М) 4 (13) ОВ БТАНТ 94 Ов Оо О7 ов Оо 19 11 12 12 14 15 4Н 16 17 18 19 ЯО БН 21 ЯЯ ЯВ 24 26 26 27 ЯВ ОН 29 РРХ К ЕИТА 0 РТУ =М= Ятх *+1(0:2) Ент1 ь ТМС1 1 РРА К 1Р2 ТАВРЕ,1(РХИК) 52М БР СИРА ТАВРЕ,1(КЕУ) ЭЕ БОССЕЯБ 522 БР ЕИТ1 0,2 СМРА ТАВОТЕ,1(КЕУ) ЛЕ БУССЕБЯ РР2 ТАВОТЕ,1(РТМК) 52ИЕ 4В РР2 Н РЕС2 1 РРХ ТАВРЕ,2 5ХМИ ь-2 322 ОУЕНГ10М БТ2 ТАВРЕ,1(Р1ИК) ЕМТ1 0,2 БТ2 Н БТХ ТАВРЕ,1(Р1МК) БТА ТАВРЕ,1(КЕТ) 1 1 1 1 1 1 1 1 1 А А А — 51 С вЂ” 1 С вЂ” 1 С вЂ” 1 С вЂ” 1 — 52 С вЂ” 1 — 52 А — 5 Т Т Т А — 5 А — 5 А — 5 А — 5 1 — 5 1 — 5 Следовательно, если таблица заполнена наполовину; среднее число проб, выполняемых при неудачном поиске, составляет около -„'(е + 2) = 1.18.
И даже если таблица заполнена полностью, среднее количество проб при вставке последнего элемента равно всего лишь ~1(е + 1) и 2.10. Стандартное отклонение также невелико (чта показано в упр. 40). Приведенные статистические выкладки показывают, что пря случайной хеш-функцин списки остаются короткими, хотя алгоритм допускает их "срастание". Конечно. С может оказаться равным даже Х, если функция плоха или вы — исключительно невезучий человек... При успешном завершении поиска А всегда равно 1. Среднее количество проб можно вычислить путем суммирования величин С + А по первым Л неудачным поискам и деления на Х в предположении, что все ключи равновероятны.
Таким образом, получаем следующее среднее количестно проб при случайном успешном поиске: 1 й 1М / 2 л 2ХЗ 1Л' — 1 С,,= — ~- (С,+ — ) =1+- — ~(1+ — ) -1- — ~+- о<о<к ее а 1 2а -1+ + —. (16) 8а 4 Даже если таблица будет полностью заполненной, в среднем потребуется талька 1.80 пробы для нахождения элемента! Аналогично (см.
упр. 42) среднее значение Я1 равно ~1л =1 — э((-" — 1)/М) =1 — ~а (17) На первый взгляд может показаться, что шаг С5 неэффективен, поскольку поиск пустой позиции на нем осуществляется последовательно. Но в действительности общее количество проб на шаге С5 при построении таблицы никогда не будет превышать количества элементов в таблице; значит, в среднем мы делаем не более одной такай пробы на вставку. В упр. 41 доказывается, что при случайном неудачном поиске Т чае . Можно модифицировать алгоритм С так, что никакие два списка не будут "срастаться", но тогда придется прибегнуть к перемещению записей. Например, рассмотрим ситуацию, представленную на рис. 40, непосредственно перед вставкой ЗЕЕБ в позицию 9, Чтобы списки оставались раздельными, необходимо переместить г1ЕЕ, а для этого нужно найти узел, указывающий на г1ЕЕ.
Решить эту проблему можно, используя не двусвязный список, а хеширование гХЕЕ и поиск в его списке, как было предложено Д. Э. Фергюсоном (1У. Е. Регйпэоп), поскольку списки невелики по размеру. В упр. 34 показано, что среднее количество проб в случае раздельных списков уменьшается до Х(Х вЂ” 1) аэ С' =1+ 2Мэ ~1+— 2 Х вЂ” 1 О Сл =1+ — а 1+в 2 2 (неудачный поиск); (успешный поиск).
(18) (19) Это, пожалуй, не слишком большое улучшение по сравнению с (15) и (16), чтобы прибегать к такому изменению алгоритма, С другой стороны, Батлер Лэмпсон (Вн1!ег Ьашрэоп) заметил, что ббльшая часть пространства, в действительности занятая ссылками, может быть сэкономлена при использовании метода цепочек, если избавиться от "срастания' списков. Это позволяет получить интересный алгоритм, обсуждающийся в упр. 13. Метод Лэмпсона вводит дополнительный бит в каждый элемент, слегка уменьшая при этом среднее количество проб, которые необходимы при неудачном поиске: с (18) да 1~У Х 1 — — ) + — =е +и. (18') М) М Раздельные цепочки, показанные на рис.
38, могут использоваться при К > М; и, таким образом, проблема переполнения снимается. При срастании списков (см. рис. 40 и алгоритм С) можно поместить переполняющие элементы во вспомогательный пул памяти; Л. Гюиба (Ь. СшЬаэ) доказал, что среднее количество проб при вставке (М+ Ь+1)-го элемента составляет (Ь/2М+ —,') ((1+2/М)м — 1) + -'. Однако обычно предпочтительнее использовать альтернативную схему, при которой первые вызывающие коллизию элементы помещаются во вспомогательную область памяти; в таком случае списки будут "срастаться" толька при заполнении вспомогательной области (см.
упр. 43). Разрешение коллизий методом открытой адресации. Другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы одну за одной до тех пор, пока не будет найден ключ К или пустая позиция. Идея заключается в формулировании правила, согласно которому по данному ключу К определяется "пробная последовательность", т. е, последовательность позиций таблицы, которые должны быть просмотрены при вставке или поиске К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
