AOP_Tom3 (1021738), страница 154

Файл №1021738 AOP_Tom3 (Полезная книжка в трёх томах) 154 страницаAOP_Tom3 (1021738) страница 1542017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 154)

д. Вообще, пусть сх = Ьз(КЕУ[ру]) и р, ь — — (р„— Ьс]) пюб ЛХ; если для всех] и Ь, таких, что Х+Ь < г, узлы ТАВьЕ[р, ь] заняты несли 1 > г+ 1, просматриваем узлы тАВее[ро „], тАВ1.е[рк, г Ц ..., тАВ1.е[р„к1]. если первое пустое место оказывается в позиции р, „,, устанавливаем ТАВ|Е[р, „,] еТАВЬЕ [р ] и вставляем К в позицию р., Лнализ Брента показывает, что среднее количество проб на один успешный поиск уменьшается до уровней, показанных на рис. 44 на с.

583, с максимальным значением, равным приблизителыю 2.49. Количество проб Х+ 1 при неудачном поиске в результате внесенных в алгоритм изменений осталось прежним; оно осталось на уровне, который определен формулой (26) и достигает -'(ЛХ+ 1) при заполненности таблицы. Среднее количество вычислений функции Аэ для одной вставки составляет согласно анализу Брента а'+а~+-'а~+. и достигает в конечном счете 0(з/М): количество дополнительных проб позиций таблицы после решения о том, каким образом будет производиться вставка, составляет около а~ + а~ + —,а + а + С усовершенствованными модификациями Брента работал Е. Г.

Маллах (Е. БЬ Ма11ас1з) [Сошр. Х 20 (1977), 137-140); с другими результатами н этом направлении можно ознакомиться в рабате Оаэсоп Н. Ооппес апд Л. 1ап Мипго, 91СОМР 8 (1979)., 463-478. Удаления. Многие праграммистгя настолько слепо верят в алгоритмы, чта даже не пытаются заду'маться о том, как они работают. Для них неприятным ск)рпризом становится то, что очевидный способ удаления записей из теш-таблицы не работает. Например, чтобы удалить ключ ЕИ на рис. 41, нельзя просто пометить этот узел в таблице как пустой, поскольку окажется потерянным другой ключ, ЕЕИ.

(Вспомним, что и ЕИ, и ЕЕИ хешируются в одно н то же положение. При поиске ЕЕИ мы натолкнемся на пустое место, что свидетельствует о неудачном завершении поиска.) Подобная проблема возникает в случае использования алгоритма С из-за срастания списков; рассмотрите удаление двух ключей — Т0 и Е1ЕŠ— на рис. 40. Вообще говоря, обрабатывать удаление можно, поместив в соответствуницую ячейку специальный код. Таким образом, будет иметься три вида позиций в таблице: пустые, занятые и удаленные.

При поиске ключа следует пропускать удаленные ячейки, как если бы они были запяты. В случае неудачного поиска ключ может быть помещен в первую встреченную удаленву.ю или пустую позицию. Однако такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а значит, посте длинной последовательности вставок и удалений все свабочные позиции исчезнут, а при неудачном поиске будет требоваться М проверок! Более того, время пробы при этом увеличится, так как на шаге 04 придется проверять, не приняло ли 1 свое первоначальное значение, а число проб в случае успешного поиска возрастет с Сн до Сч~.

При использовании линейнога исследования (алгоритм Ь) мовена поступить более разумно, если, конечно, затратить дополнительные усилия на удаление. Алгоритм В. (Удаление при линейном исследовании). Пусть хеш-таблица построена по алгоритму Ь. Алгоритм удаляет запись из данной позиции ТАВЬЕ[с Ь В.1. [Освобождение ячейки.) Пометить ТАВЬЕ [О как пустую и установить у е- Ь К2.

[Уменьшение 1.] Установиты е- 1 — 1 и, если 1 стало отрицательным, установить 1з — г ЬЛХ. НЗ. [Проверить ТАВЬЕ [П,) Если ТАВЬЕ [П пуст., алгоритм завершается. В противном случае установить г +- 6(КЕТ [П) — первоначальный хеш-адрес ключа, который хранится в позиции Ь Если 1 < г < 1 илн если г < 1 < 1 либо 1' < 1 < г (другими главами, если г лежит циклически между 1 и у), вернуться к шагу Й1.

Ы4. [Переместить запись.] Установить ТАВ1.Е [1) +- ТАВЬЕ [П и вернуться к шагу Н1. 1 В упр. 22 показана, что этот алгоритм не вызывает снижения производительности; друтими славами, среднее количество проб, предсказанное в формулах (22) и (23), останется тем же (более слабый результат для вставки в дерево был доказан в теореме 6.2,2Н).

Однако корректность алгоритма В сильно зависит ат того факта, что используется линейное исследование хеш-таблицы, а потому аналогичный алгоритм удаления при применении алгоритма П отсутствует, Среднее время работы алгоритма Н анализируется в упр. 64. Конечно, при использовании метода цепочек с различными списками для всех возможных хеш-значений удаление не вьгзывает проблем, поскольку сводится к простому удалению из связанного линейного списка. Удаление для алгоритма С обсуждается в упр. 23. Алгоритм К позволяет перемещать некоторые элементы таблицы, что может оказаться нежелательно (например, если на элементы имеются ссылки извне). Другой подход к проблеме удаления основывается на адаптировании некоторых идей, использующихся при сборке мусора (см.

раздел 2.3.5): можно хранить количество ссылок с каждым ключом, говорящим о том, как много других ключей сталкивается с ним; тогда при обнулении счетчика можно преобразовать эакве ячейки в пустые. Другой метод состоит в проходе по всей таблице, как только наберется слишком много удаленных элементов, замене всех незанятых позиций пустыми и просмотре всех оставшихся ключей, чтобы выяснить, какие незанятые позиции все еще имеют статус "удаленных".

Эти методы, позволяющие избежать перемещения элементов в таблице и работающие с любой хеш-технологией, были впервые предложены в работе Т. Опп)! апб Е. Со!о, 1. 1пуогта!!оп Ргос. 3 (1980), 1-12. *Анализ алгоритмов. Поскольку при хешировании необходимо опираться на теорию вероятностей, очень важно знать поведение метода хеширования в среднем. Наихудший случай использования этих алгоритмов невообразимо плох, поэтому следует убедиться в том,что поведение в среднем очень хорошее. Прежде чем приступить к анализу линейного исследования и других методов хеширования, рассмотрим приближенную модель ситуации, называемой равномерным исследованием.

В этой модели, предложенной В. В. Петерсоном (%. Ж. Регегэоп) [1ВМ Х Незеагсл й Рече!ортеп1 1 (1957), 135-136], предполагается, !то каждый ключ размещается в совершенно случайном месте таблицы, так что все (л) воз- М можных конфигураций из !У занятых и М вЂ” Х пусгых ячеек равновероятны.

В данной модели игнорируются эффекты первичного или вторичного скучивания; предполагается, что занятость каждой конкретной ячейки не зависит от занятости остальных. Тогда вероятность того, что для вставки (!У+ 1)-го элемента необходимо н точности г проб, равна количеству конфигураций, и которых г — 1 данная ячейка занята, а еще одна пуста, деленному на (,), т. е. м Таким образом, среднее количество проб в случае равномерного исследования со- ставляет м м С!ч = ~' гР~ = М + 1 ~(М + 1 !')Р~ г=! г=! =И~~ — Еэ[!1 ! —,|( ~ ' )!!(~~) = и,- ~ — Е<ы — к)(~~+ ') ~ (~) = лб 1 — [и — лс ( к+,',),~('~~) =М+1 — 1М вЂ” Л) = ', 1<~Ч< М. (Зг) М+1 М+1 М-Н+1 М-я+1' (Мы уже решали, по существу, ту же задачу в связи со случайной выборкой в упр.

3.4,2-5.) Полагая а = Ю/М, точную формулу для С~ можно заменить приблихсенной: =1+а+а +а + (ЗЗ) 1 — а Ее можно интерпретировать примерно так: с вероятностью а требуется более одной пробы, с вероятностью ат — более двух и т. д. Соответствующее среднее число проб при успешном поиске равно (34) Как отмечалось выше, многочисленные тесты показали, что алгоритм Р с двумя независимыми хеш-функциями ведет себя, по сути, так же, как при равномерном исследовании для всех практических целей. В действительности двойное хеширование асимптотически эквивалентно равномерному исследованию в пределе при М вЂ” ~ со (см. упр. 70).

Этим завершается анализ равномерного исследования. Для изучения линейного исследовании и других типов разрешения коллизий следует строить более реалистичную теорию. Вероятностная модель, которая будет использоваться для этой цели, предполагает, что яге М~ яозможных "хеш-последовательностей" (35) а~ оз...охз 0 < а~ < М, равновероятны.

Здесь ау обозначает начальный хеш-адрес 1-го ключа, вставленного и таблицу. Среднее количество проб в случае успешного поиска прн работе по данному алгоритму поиска, как и выше, обозначим через См; зто значение представляет собой среднее количество проб, которые необходимы для поиска йго ключа, усредненное по всем 1 < 1. < Ж при равновероятных ключах и по всем хеш-последовательностям (35) (все послгдонательности считаются равновероятными).

Аналогична среднее количество проб, необходимых при вставке Х-го ключа, считая все последовательности (35) равновероятными, обозначим как Сч~, эта величина представляет собой среднее количество проб в случае неудачного поиска, начинающегося при наличии в таблице Х вЂ” 1 элемента. При использовании открытой адресации (36) /(М, Л) = (1 — — ) М'. (37) По определению также полагаем, что /(О, 0) = 1. Пусть д(ЛХ, Х, й) — число хешпоследонательностей (35), таких, что алгоритм оставляет позицию 0 пустой, позиции от 1 до и занятыми и позицию й + 1 — пустой.

Характеристики

Тип файла
DJVU-файл
Размер
10,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6549
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее