AOP_Tom3 (1021738), страница 210
Текст из файла (страница 210)
Решение этого рекуррентного соотношения — Тк (Н/М) (1 + 1/М) ~ (Такая простая формула заслуживает более простого доказательства!) 42. Я1»р равно количеству элементов, вставленных при А = О, деленному на рУ. 44. (Рассмотренный здесь способ решения "в лоб" был иаССлен автором в 1972 голу; гораздо более элегантное решение М. С. Патерсона (М. Б. Раьегеоа) можно найти в книге Грина (Сгеене) и Кнута (Квасб) Масбепрабсэ Гог с!се Апа1уэтв оГ А!дргййспэ (Всгссбаавег Воэсоа, 1980), 33.4. Патерсон нашел также важные методы упрощения других способов выпалпеиия анализа, описанных в этом разделе.) Пронумеруем позиции массива от 1 до т слева направо. Рассматривая множество всех (") последовательностей операций с й "р-шагами" и и — Ь "д-шагами" как равповероятные, обозначим через д(т,п+1, Ь, г) умиоженную иа (") вероятность того, что первые г — 1 позиций становятся занятыми, а г-я осталась пуста.
Таким образом, д(т,1,Ь,г) равна умножеипой на (т — 1) С' ' "Р сумме по всем канфигурацияи 1<а!« . а«<1, (сс,...,с! ! «), 2<с!<та, вероятностей того, что первая пустая позиция — г, когда а,-я операция представляет собой р-шаг, а оставшиеся 1 — 1 — Ь операций представляют собой д-шаги, которые начинаются с выбора позиций сс, ..., с! !» соответственно. Выполнив суммирование по всем конфигурациям при дополнительном условии, что ар-я операция занимает позицию Ь„при данных 1 < Ь! « Ь» < г, получим рекуррецтиое соотношение д(т,1,1!+1,г) = ~, ';(ти — 1+1)д(т,а,Ь,Ь); «<! ь< ° !<«< д(т,с, О, г) = '(т — 1+ 1) ! Р! + [г тс Ц вЂ” (1 — Р!)), (1 — 1)! (т — г)! / т (- )' 1 — 1 где Р! —— (т/(т — 1)) .
Обозначив С(ти,1, Ь) = 2„„»(т+ 1 — г)д(ти,1, Ь, г), получим, что ! — 1 С(т,1, Ь+1) = ~С(т,а!Ь); =! С(т,1,0) = ти — 1+ 1 (т+ Р!). ти — 1+ 2 Решением поставленной задачи является ти — 2„«в ар«д" «С(т, и+1, Й), что после неко- торых преобразований становится равным т — ((т — и)/(т — и+ 1))Щ + тй+РЯВ), где б); = Р„,д', 43. Пусть Х = аМ' и М = /)М' и пусть е "+Л = 1/3, р = а/р3.
Тогда Си 1+ -'р и С~д ш р+с» при р < Л; Ся ! (еы т« — 1 — 2р+2Л)(3 — 2/13+2Л)+ -(р+2Л вЂ” Л /р) и Сьб 1/13+ -'(етт-р«-1)(3 — 2/д+2Л) — -'(р-Л) при р > Л. Если а = 1, получим иинииютьное Сп 1 69 при 17 ш .883; наименьшее С,'„1.79 получается при,д .782. Установив В = .86, можно получить близкую к оптимальной производительность для широкого диапазона а. Таким образом, помещение первых коллизий в область, не конфликтующую с хеш-адресами, оправдывается, даже если при меныаем диапазоне хеш-адресов получается больше коллизий.
Приведенные результаты были получены Дж. С. Виттером (Зейгеу Б. Лрсссег), ЗАСМ ЗО (1983), 231-268. (1 — — ) с/о (1 — — ) Я! 1 — ( )Чо-! Н (1 — 1/(!и+ 1 — 5))0ь о=о П,=о(1 р/(т+ 1 у)) При р = 1/т, О! = 1 для всех у. Считая н! = т + 1, и = аю, ш -о со, найдем !п Н = -(Н . — Н !!,!)р+ 0(ро); следовательно, Н = 1 + в! ! !п(1 — а) + 0(ш з); аналогично а = а!о+ 0(1).
Таким образом, ответ будет таким: (1 — а) ' — 1 — а — !п(1 — а) + 0(ш '). Приме»оное. Базее простая задача "С вероятностью р займем крайнюю слева позицию; в противном случае займем случайным образом выбранную пустую позицию" решв ется, если принять Р! = 1 в врнведенных выше формулах, и ответом будет ти — (т+ 1)(т— и)Н/(т — и + 1). Чтобы получить С» для случайных проб с вторичной кластеризацией, установим и = !»', т = М и добавим 1 к приведенному выше ответу. 45. Да.
См. ! . Св!Ьао, ОАСМ 25 (1978), 544-555. 46. Определим числа [[" ]] для й > О согласно правилу Р"'и~:11 =""" для всех х и всех целых неотрицательных и. Полагая х = — 1, — 2,..., -и — 1, получим, что Затем, рассматривая х = О, получим, что при !с > и можно считать [["„]] = О, так что обе части определяющего уравнения представляют собой полиномы от х степени и, совпадающие в и+1 точке Отсюда гледует, что чнгза [[", ]] обладают указанным свойством. Пусть /(Х, г) — количество хеш-последовательностей а!... ол, при которых первые г позиций заняты, а слгдующаи — пустая, Существует (и, ', !) способов размещения занятых ячеек, и каждый из ннх встречается столько рвз, сколько имеется последовательностей о',... а';», 1 < о', < !»', таких„что в каждой последовательности каждое из чисел г+ 1, г+ 2, ..., а! содержится хотя бы один раз.
В соответствии с принципом включении-исключения имеется [[, л,Ц таких последовательностей, Таким образом, Теперь У / г — 1 м — ! о',=! м-"-'» г(о,.)(З, » " ' !, о) «=о а=е =г~-! = 1+ М ~ 2: /(Ж.г)(!»'+ (!»' — 1)г). .=о Полагая з„(х) = 2 „5('+,~) [[",]], имеем следовательно, Я„(х) = (х + 1)((х + и + 2)" — (х + и + 1)").
Отсюда вытекает, что С» —— д!(1+ 1/М) — (!»' — 1)(1 — /»/М)(1+ 1/М) /О(1 — (1 — а)е") и Сл = (Х вЂ” 1)((1+ 1/М)/2 + (1 + 1/М)м) + (ЗМ + бМ + 2)((1 + 1/М) — 1)/!Ч вЂ” (ЗМ + 2)(1 + 1/Л4) ~, что равно (е — 2.5)Л4 + О(1) при !Ч = М вЂ” 1. О других свойствах чисел [(„")) можно прочесть в книге Зоба Вхогбап, СошЫпагопа! 1г!епННеа (Неж Уогйо Ч~!!еу, 1968), 228 — 229. 47. Практически так же применим анализ алгоритма 1' Любая последовательность проб с циклической симметрией, которая проверяет только соседние с ранее проверенными позиции, будет вести себя точно так же, 48.
Сл — — 1 + р + рх +, где р = А!/М представляет собой вероитность топь, что слУчайнаЯ позиции заполнена; следовательно, Ст —— М/(М вЂ” А') и См = !Ч 2 ' „С» = М(Нм — Нм-л). Эти значения приблизительно равны значениям при равномерном исследовании, но несколько выше за счет возможности повторного опробования одного и того же места. В действительности при 4 = 7т' < М < 16 линейное исследование имеет лучшие характеристики! На практике нельзя применять бесконечно много хеш-функций; в качестве последнего средства должна использоваться другая схема - — схема наподобие линейного исследования.
Этот метод хуже описанных в тексте и представляет только историческую ценность, твк как он послужил толчком к разработке метода Морриса (Могпэ), который, в свою очередь, привел к разработке алгоритма О. См. САСЛХ 6 (1963), 101, где М. Д. Мак-Илрой (М. О. Мс!!гоу) приписывает эту идею В, А. Высоцкн (Ч. А. Чуаэосз!су); та же технология была открыта в 1956 году А. В. Хольтом (А, ЪЧ. Но!С), который успешно применил ее в системе ОРХ дли БМ!ЧАС. 49. Сл — 1 = 2 ь ь(6 — 6)Рчь 2 ь ь(6 — 6)е ~(п6)~/6.
= пбгь(а), (Примечание, В общем случае имеем ь (ь а-/>1/* =— Р'(1) х(Р(х) — 1) ,/ — 1-. (1 -.Р ь>а»ь для любой производящей функции вероятностей Р(х) = Ра + Р1 х + Ч ~ ( 2 ) ь>ь = — К(6(6 — 1) — 26(6 — 1) + 6(6 — 1))рк М 2,Ч ь>ь аье ь (Ьо) Ь! ~(Ь+ Ьп — 2Ь+ 2+ (Ьо — 2п(6 — 1) + Ь вЂ” 1)22(о,Ь)). (В 1957 году анализ успешного поиска с цепочками был впервые проведен В П. Хайзингом (ЛЧ. Р Не!ыпб). Простые выражения в (57) и (58) были найдены Я. А, ван дер Пулом (3.
А. тап бег Роо!) в 1971 году: им также рассмотрен вопрос о минимизации функции, представляющей комбинированную стоимость используемого пространства и количества обращений. Можно определить дисперсию Сь и числа переполнений на блок, исходя из 2 ь>ь(к 6) Рль = (2А/М)(Ск — 1) — (Сч — 1). Дисперсия общего количествапереполнений может быть приближенно представлена увеличенной в М раз дисперсией в единичном блоке, хотя на самом деле это завышенное значение, потому что общее количество записей вынуждено быть равным )Ч. Истинная дисперсия может быть найдена, как и в упр.
37. Обратитесь также к исследованию Ха-критерив в разделе 3.3.1С.] 50. А затем — что Оа(ЛХ, Л7 — 1) = (М/Ч)(Оа(М, !Ч) — 1). В общем случае гОг(М !Ч) = Мьх — 2(М М) (М 67 )ьг — (М Х) = М(ы -1(м А +1) ь>Ь вЂ” 1 (М !Ч)), ч (М !Ч 1) (М/!Ч) Щ, (М, Ч) — О„ь (М, !Ч) ) . 51. 27(п, и) = и '(и! е"'(оп) " — Оа(пп, п)) 56. См. В1айе апб КопЬесш, ЗАСМ 24 (1977), 591-606. Альфредо Виола (А1(гессе Чсо1а) и Патрицио Поблете (Разпсю РоМезе) (А18осбсйтоса 21 (1998), 37 — 71] показали, что о>о з>1 м)/ — + — +-~~, + / +О 5 'М ), з-! огМ 1 1к 1 о=! где Т вЂ” Функция дерева из 2.3 4.4-(30). 58. 0 1 2 3 4 и 0 2 4 1 3 плюс алдитнвные сдвиги 1 1 1 1 1 шоб 5, каждый с вероятностью —,' . Аналогично при М = б требуется 30 перестановок, и решение существует, начинаясь с Тэ.
х 012345, ! х 013254, — ' х 024315, —,'э х 023451, — ' х 034125. При М = 7 требуется 49 перестановок, и решение порождается из зсз х 0123456 оз х 0153246,,с, х 0243516!,оз х 0263145, зсз х 0361425 соз х 0326415,сз х 0315426. 59. Пи одна перестановка не может иметь большую вероктностзь чем 1/( 'и,), поэтому должно быть не менее ( м ) = ехр(М1л2+ 0(1оКМ)) перестановок с™ненулевыми вероятностями. 60. Предварительные результаты получены в работе А)сас, Косп1бэ, щссС Бзешегессс, 1псогпоасюл Ргосезэтб Ьессегэ 7 (1978), 270-273. 62. См. дискуссию в АММ 81 (1974), 323 — 343, где представлены нан.лучшие циклические последовательности хешировании для М < 9, 63.
МНм согласно упр. 3.3.2-8; стандартное отклонение составляет ш э М/с/6. 64. Среднее количество перемещений составляет — '(Х вЂ” 1)/М+ з (Ао — 1) (озс — 2)/М + с (А!в 1)(Ас — 2)(Ас — 3)/М + —,' — — '1в —,' . [Аналогичная задача решена в Сотр. Х 17 (1974), 139 — 140.) 65. Ключи могут храниться в отдельной таблице с последовательной организацией (предположим, что все удаления, если онн производятся, соответствуют стековому представлению Ь1РО (1эзс-ш-бгэс-опс, эпоследним вставляется — первым удаляетск"). Элементами хеш-таблицы являются указатели на эту "таблицу имен", например, ТАВЬЕЫ может иметь вид где 1., — колнчествослов в ключе,храннщемся в позициях КЕТЫ, КЕТЫ + 1,.... Остаток элементов хеш-таблицы может использоваться несколькнмн способами: (!) как ссылка для алгоритма С; (й) как часть информации, связанной с ключом; (ш) как "вторичный хеш-код".
Последняя идея, предложенная Робертом Моррисом (ВоЬегс Мопса), иногда позволяет ускорить поиск (мы рассматриваем ключ КЕТЫ только в том случае, когда значение некоторой функции Ьо(К) соответствует вторичному хепс-коду). 66. Да; при этом расположить записи можно лишь одним способом. Среднее количество проб при неудачном поиске снижаетск до Сл-с, хотя и остается равным Со; при вставке Ао-го элемента. Эта важная технология именуется упорассоченнмм хешированием. См. СотР. Х 17 (1974), 135 — 142: В. Е.
КппСЬ, ЬйегаСе Ргобгатттб (1992), 144 — 149, 216 — 217. 67. (а) Если в (44) с! = О, оптнмаосьного расположения можно достичзь рассортировав а согласно невозрастающему "циклическому порядку", которым предполагается, что 2 — 1 > > 0 > М вЂ” 1 » ,1. (Ь) Между шагами 12 и ЬЗ поменяйте вставляемую зались и ТЛВЩ), если последняя ближе к начальному положению, чем предььтущая. (Этот алгоритм, названный хешированием Робин Гуда (ВоЬчп Ноос1 ЬавЫпб) в работе Сейв, Еахвоп, апб Мппго, РОСВ 26 (1985), 281 — 288, представляет собой вариант упорядоченного хеширования.) (с) Обозначим через Цт,п,чв) количество хеш-последовательностей, которые приводят к со < И. Можно показать <Сотр..У. 17 (1974), 141), что (Ь(т, и, ч)) — Ь(т, п, ч(— 1))М вЂ” общее количество перемещений ч( ) 0 по всем М хеш-последовательностям и что можно записать ЦМ, чл7,8) = о(М, Ач, И-~-1) — чч'а(М, Ач — 1,ч4+ 1), где а(т, и, ч1) = <")(т+ч1 — Й)" (Й вЂ” 8)".
Сложные вычисления с использованием методов нз упр. 28 и 50 показывают, что среднее значение 2 6ч равно М' "~ дв(ЦМ,Х,В) — Ь(М,3,8-1)) в=ч Мв 2М чл7 члч'~ Ю г ЛХ АГ 21 = — + — + — + — — — — М~ — — — + -) что(Лв, Ач) 2 3 6 6М 6М ч 2 2 3) 1 7 2 а а''1 при 57 = аМ. Если алгоритм не модифицирован (см. упр. 28), Е 2 ч(ч преобразуется в — (Ов(М, Ач) — Оч(М, Ач)) — — (Оо(М, Ач) — 1) +— М М Ач 3 2 6 1 1 3(1 а)в 3(1 — а) 1 1 сч1 2О- )+2 6)+~(~)' — ((М вЂ” Ач) + (Х+ 3)(М вЂ” Ю) + (87ч7 + 1)(М вЂ” Ач) + 5Ач~ в- 4Ач — 1 12 — ((М вЂ” Ач) + 4(М вЂ” Ач)'+ (6Х+ 3)(М вЂ” Ач) + ВХ)Оо(М, Аà — 1)), как можно показать, рассмотрев связь между задачей о парковке и связанными графалчн, о которой упоминалось в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
