Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 45
Текст из файла (страница 45)
Лаже сейчас анализ елгоонтмов остается олннм нз главных занятвй в моей жнзнн. Теперь С~ = ~"„'.~ (к + 1)Ра, с учетом формул (36)-(39) и после определенных упрощений получим гледующий результат. Теорема Р. Среднее количество проб прп успешном лояске с ломошью алгоритма 1, не зависят от порядка, в которо ч ключи были вс|ввлеиы; оя зависят только от числа ключей с тем лля лным хеш-адресом. Другими словами, любое переупорядочеиие хеш-последовательности а1 аз...
аь дает хеш-последовательность с тем же средним смещением ключей от их хеш-адресов. (Предполагается, как упоминалось ранее, что все ключи в таблице одинаково важны. Если обращение к одним ключам происходит чаще, чем к другим, то, используя метод доказательства теоремы 6.13, можно показать, что оптимальное расположение ключей достигается при их вставке в порядке уменьшения частот.) Дояазательсшео. Достаточно показать, что общее количество проб, необходимых для вставки ключей для хеш-последовательности а1 ат... а ко такое же, как и для последовательности а1... а, ~ а;+1 а; а;+т...
ак, 1 < 1 ( Х. Очевидно, что нет никаких отличий между этими двумя случаями, пок» (1+1)-й ключ второй последовательности не попадает в позицию, занимаемую 4-и ключом в первой йоследовательности. Однако тогда 1- и (4+ 1)-й элементы просто меняются местами, так что количество проб для (1+ 1)-го ключа уменьшается на столько же, на сколько увеличивается число для 1-го ключа.
1 Согласно теореме Р средняя длина поиска для хеш-последовательности а1 ат... ал. может быть определена из чисел 6»61...6м ы где 6 представляет собой количество элементов аь, равных у. По этой последовательности можно определить "'пос»едовательиость переносов" со с1... см ы где с, равно числу ключей, для которых при вставке ключа проверяются обе позиции Ц и у -1).
Эта посоедовательность определяется правилом О, если Ь, = сбы1 ~м = 0' с;= Ь, + сбчн,о м — 1 в противном случае. (44) 1+ (со + с1 + . + см 1)/Х. (45) Кажется, что правило (44) представляет собой циклическое определение чисел с через самих себя. но в действительности при любом Х < М система имеет единственное решение (см. упр.
32). Шей и Спрут использовали эту идею ~ля определения вероятности дь того, что с = й через вероятности рь того, что 6, = й. (Этн вероятности не зависят от 1.) Таким образом, Чо =Росе+ Р1чо+РОУ1 сг =Ртсо+Р~Д1 +Родэ Чт = Рзсо + РтД1 + Р1 Чо + РоЧз и т. д., поскольку, например, вероятность того, что со = 2, представляет собой вероятность того, что 61+об+» „ам = 3. Пусть В(х) = 2.'рьс" и С(х) = 2,'сьс"— Например, пусть М = 10, У = 8 и 6о...
Ьо = 0 3 2 О 1 0 О 0 0 2; тогда со... со = 2 3 1 О 0 О 0 1 2 3, поскольку один ключ должен быть перенесен из позиции 2 в позицию 1, три — из позиции 1 в позицию О, два — из позиции О в позицию 9 и т. д. Имеем 6о + 61 + .. + Ьы 1 — — Ф, и среднее количество проб, необходимых для выборки Х ключей. составляет производящие Функции для этих распределений вероятностей; уравнения (46) эк- вивалентны Формуле В(л) С(л) = РоФо+ Ио — РоЧо)л+ д1л'+ "= РоЧо(1 — л) + хС(л). Поскольку В(1) = 1, можно записать В(х) = 1+ (г — 1)В(э). Отсюда вытекает, что РоЧо 1 — В(1) 1 — П(л) 1 — В(л) ' (47) так как С(1) = 1. Среднее количество проб, необходимых для выборки, в соответ- ствии с (45) составляет М, М В'(1) М В" (1) Ю У 1 — В(1) 2Х 1 — В'(1) (43) В связи с тем, что предполагается равновероятность всех хеш-последовательностей о1...ам, имеем рь = Рг(для фиксированного у в точности к нз а; равны 1) = ~') ЙЙ'--')' " Г49) следовательно, г — 1хл, Х В(х) = (1+ — ), В'(1) = —, И 7'' М' Ю( У вЂ” 1) Мт и среднее количество проб согласно (43) составит Сн = -(1+ — ).
(51) В состоянии ли читатель указать неверные рассуждения, вызвавшие отличие между полученным ответом и точным результатом в теореме К7 (См. упр. 33.) "'Анализ оэзтимальности. Мы рассмотрели несколько примеров последовательностей проб для открытой адресации, в результате чего, естественно, возникает вопрос, какая из них наилучшая иэ возможных в некотором разумном смысле. Эта задача имеет интересную постановку, предложенную Д. Д. Ульманом (3. В.
ПР шап) (,УАСМ 19 (1972), 569-'575): вместо того чтобы вычислять хеш-адрес Ь(К), мы отображаем каждый ключ К на перестановку множества (9, 1,..., М вЂ” 1) „которая представляет последовательность проб при использовании К. Каждой из М! перестановок назначена вероятность, и предполагается, что обобщенная хешфункция выбирает каждую перестановку с этой вероятностью.
Вопрос формулируется следующим образом: "Какое назначение вероятностей данным перестановкам даст наивысшую производительность, т. е. минимизирует соответствующие средние числа проб См и С~ну". Например, если назначить каждой перестановке вероятность 1/М!, то получится Равномерное исследование, проанализированное в (32) и (34), Однако Ульманом был найден пример с М = 4 и Х = 2, для которого С~ меньше, чем значение Перестановка 0213 1320 2031 3102 5, полученное для равномерного исследования. Его построение назначает нулевые значения всем перестановкам, кроме следующих шести.
Перестановка Вероятность Перестановка Вероятность 0 1 2 3 (1+ 2е)/б 1 0 3 2 (1+ 2е)/б 2013 (1 — е)/6 2103 (1 — е)/б 3 0 1 2 (1 — е)/б 3 1 0 2 (1 — е)/б Грубо говоря, на первом шаге предпочтение отдается 2 или 3, а вторая проба всегда проверяет О или 1. Среднее количество проб, необходимых для вставки третьего эле- мента, Сэ, равно 5 — 1е+ 0(е~), так что можно улучшить равномерное исследование, присвоив с малое положительное значение, Однако соответствующее значение С, 'для этих вероятностей составляет Лэе + 0(е), чта больше 4 (значение для равномерного исследования).
Ульман доказал, что любое назначение вероятностей., такое, что См с (ЛХ + 1)/(ЛХ + 1 — ЛХ), для некоторого Лг всегда влечет справедливость С,', > (М+ 1)/(ЛХ+ 1-и) для некоторого и < У; нельзя все время побеждать равномерное хеширование... В действительности количества проб при успешном поиске является лучшим критерием, чем Сд, Перестановки в (52) не приводят к улучшени|о значения См для любых Лг, н Ульман предположил, чта никакие назначения вероятностей не сделают См меньше, чем длЯ РавномеРного исследованиЯ: ((ЛХ + 1)/ЛГ)(Нм+1 — Нм+1 и).
Эндрю Яо (Апбгеж Уао) доказал асимптатнческую форму этого утверждения, по- казав, что предельная цена при ЛХ = оЛХ и М -э аа всегда > — ' 1п;-1- (,7АСМ 32 (1985), 687-693!. Строгую форму предположения Ульмана очень сложно доказать. в особенно- сти потому, что существует много вариантов назначения вероятностей для получе- ния эффекта равномернога исследования; нет необходимости назначать вероятности 1/М! каждой перестановке.
Например, следующие назначения также дают эквива- лент равномерного исследования. Перестановка Вероятность Вероятность 0123 1/б 1/12 1230 1/б 1/12 (53) 2301 1/б 1/12 3012 1/6 1/12 (Остальным шестнадцати перестановкам назначена нулевая вероятность.) Следующая теорема характеризует все присвоения, дающие поведение равно- меркого исследования. Теорема Ю. Назначив вероятности перестановкам, все (м) конфигурации пустых и занятых ячеек можно сделать равиоверсятимми после Х вставок лля О < гт' < М гагди и только тогда. когда сумма вероятностей, незначенная всем перестановкам, первые Лг элементов «старых являются члеиаии данного Х-элемеитиого множества„ равна 1/(ь() для всех Х и для всех .У-элементных множеств, Например, сумма вероятностей, назначенных каждой из 3!(ЛХ вЂ” 3)! перестано- вок, которые начинаются числами (О, 1, 2) в заданном порядке, должна составлять 1/(м) = 3!(ЛХ вЂ” 3)!/ЛХ!.
Заметьте, чта (53) удовлетворяет условию теоремы, по- скольку 1/6+ 1/12 = 1/4. обласпли тлереполнеиил. Обычно нс имеет смысла разбивать область переполнения на блоки, поскольку, как правило, возникает сравнительно немного переполнений; таким образом. "лишние'" записи связываются одна с другой, поэтому !Ь+Ь)-я запись списка требует 1+ й обращений. Обычно отбит оставлять место для переполнений в каждом цилиндре дискового файла, чтобы как можно больше обращений оставалось в пределах одного и того же цилиндра. Хотя этот метод обработки переполнений кажется неэффективным, статистически число переполнений достаточно мало для того, чтобы среднее время поиска оставалось очень хорошим.
В табл. 2 и 3 показаны средние количества требуемых обращений как функций коэффициента заполненности а = Х/ЛИ !54) для фиксированного а и М,Ю вЂ” л со. Любопытно, что при а = 1 асимптотическое количество обращений для неудачного поиска увеличивается с ростом Ь. Таблица 2 СРЕДНЕГ КОЛИЧЕСТВО ОВРАШЕНИИ В СХ!УЧАЕ НЕУДАЧНОГО ПОИСКА ПО РАЗДЕЛЬНЫМ ПЕПОЧКАМ Размер Коэффициент заполнения, о блока, Ь 10% 20% 30% 40% 50% 60% 70% 80% 90% 95% Таблица 3 СРЕДНЕЕ КОЛИЧЕСТВО ОБРАШЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПС)ИСКА ПО РАЗДЕЛЬНЫМ ПЕПОЧКАМ Коэффициент заполнения, а 10% 20% 30% 40% 50% 60% 70% 80% 90% 95% Размер блока, Ь В) Использование срастаюи!ихсл цепочек. Можно не выделять специальную область переполнения, а адаптировать алгоритм С для работы с внешними файлами.
Для каждого цилиндра может поддерживаться двусвязный список свободного пространства, связывающий совместно все ие полностью заполненные блоки. При исполь- 1 2 3 4 5 1О 20 50 1 2 3 10 20 50 1.0048 1.0187 1.0408 1,0703 1.1065 1.0012 1.0088 1.0269 1.0581 1.1036 1.0003 1.0038 1.0!62 1,0433 1.0898 1,0001 1.0016 1.0095 1.0314 1.0751 1.0000 1.0007 1.0056 1.0225 1.0619 1,0000 1.0000 1.0004 1.0041 1.0222 1.0000 1.0000 1.0000 1.000! 1,0028 1.0000 1.0000 1.0000 1.0000 1.0000 1.0500 1.1000 1.1500 1.2000 1.2500 1.0063 1.0242 1.0520 1.0883 1Л321 1.0010 1.0071 1.0215 1,0453 1.0806 1.0002 1.0023 1.0097 1 0257 1.0о27 1.0000 1.0008 1.0046 1.0151 1.0358 1.0000 1.0000 1.0002 1,0015 1.0070 1.0000 1.0000 1.0000 1.0000 1.0005 1.0000 1.0000 1.0000 1.0000 1.0000 1.1488 1.197 1.1638 1.238 1,1588 1.252 1.1476 1.253 1.1346 1.249 1.0773 1.201 1.0234 1.113 1.0007 1.018 1.3000 1.350 1.1323 1.238 1 1259 1.181 1.0922 1.145 1.0699 1.119 1.0226 1.056 1.0038 1.018 1,0000 1.001 1.249 1.307 1.34 1.327 1.428 1.48 1.369 1.509 1.59 1.394 1.571 1.67 1.410 1,620 1.74 1.426 1,773 2.00 1.367 1.898 2.29 1.132 1.920 2.70 1.400 1.450 1,48 1.299 1.364 1.40 1.246 1.319 1.36 1.211 1.290 1.33 1,186 1.'268 1.32 1.115 1.206 1.27 1.059 1.1оО 1.22 1.01о 1.033 1.16 Таблица 4 СРЕДНЕЕ КОЛИЧЕСТВО ОБРАШЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПОИСКА ПРИ ЛИНЕЙНОМ ИССЛЕДОВАНИИ Коэффициент заполнения, о 10% 20% 30% 40% 50% 60% 70% 80% 90% 95% Размер блока, Ь 5.500 10.50 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
