AOP_Tom3 (1021738), страница 155
Текст из файла (страница 155)
Имеем д(М, Лг, й) = ~ //(1с+1, к) /(ЛХ вЂ” и — 1, Лг — 1), удг~ (38) поскольку. все такие хеш-последовательности состоят из двух подпоследовательностей. Первая (в ней содержится и элементов а; < к) оставляет позицию 0 пустой, а позиции от 1 до Й занятыми; вторая (в ней содержится Х вЂ” Й элементов а, > й + 1) оставляет позицию к+ 1 пустой. Существует /(1+1, 1) последонательностей первого типа, /(М вЂ” и — 1, Лг-к) последовательностей второго типа и (А) способов их смешения. И, наконец, положим Рь равным вероятности того, что при вставке (Лг+ 1)-го ключа требуется в точности й+ 1 проб.
Отсюда следует (см. упр. 25), что Ра = М ~(д(М,Лг, Й) + д(М, М, 1+1) + .. +д(М,1У,Лг)). (39) ТепеРь С~~, —— 2 а о (Й + 1)Рь, с Учетом фоРмУл (36) — (39) и после опРеделенных упрощений получим следующий результат. " Автор нг может ие делать вставку автобиографического характера: я впервые сформулировал предлагаемый вывод в 1962 году, вскоре после начала работы над "Искусством программнрованняс Поскольку это был первый успешно проанализированный мною нетривиальный алгоритм. он оказал сильное влияние Иа стотктчот этих книг. даже сейчас анализ алгооитмов остается одним из главных занятий в моей жизни. так что можно вывести одну величину из другой, как в (34).
Строго говоря, даже эта уточненная модель не лишена недостатков. Первый из них заключается в том, что не все хеш-погледовательности равновероятны, поскольку сами ключи различны. Это делает вероятность того, что аг — — аз, немного меньше, чем 1/М; однако отличие обычно незначительно, поскольку количество всех различных ключей, как правило, горазда больше, чем М (см. упр. 24). Более того, хорошая хеш-функция способна использовать неслучайность типичных данных, дополнительно уменьшая вероятность того, что аг = аз, 'таким образом, оценки числа проб будут пессимистическими. Другая неточность модели указана на рис. 43: ключи, встретившиеся ранее (за небольшими исключениями), ищутся чаще других. Таким образом, оценки Сл окажутся дважды пессимистичными и на практике алгоритмы будут иметь ббльшую производительность, чем предсказано в результате нашего анализа. С учетом этих предостережений можно приступать к 'точному" анализу линейного исследованная, Пусть /(М, Ж) — — число хеш-последовательностей (35), таких, что позиция 0 таблицы будет пуста после вставки ключей с помощью алгоритма 1.
Из циклической симметрии линейного исследования гледует, что позиция 0 пуста так же часто, как и любая другая позиция, поэтому она пуста с вероятностью 1 — Лг/М; другими словами Теорема Р. Среднее количество проб прп успешном поиске с помощью алгоритма Т не зависит от порядка, в котором ключи были вставлены; оп зависит только от числа ключей с тем пли иным хеш-адресом. Другими словами, любое переупорядочение хеш-последовательности аз аг... аьч дает хеш-последовательность с тем же средним смещением ключей от их хеш-адресов. (Предполагается, как упоминалось ранее, что все ключи в таблице одинаково важны.
Если обращение к одним ключам происходит чаще, чем к друтнм, то, используя метод доказательства теоремы 6.18, можно показать, что оптимальное расположение ключей достигается при их вставке в порядке уменьшения частот.) Доказательсгпео. Достаточно показать, что общее количество проб, необходимых для вставки ключей для хеш-последовательности аз аг... ам, такое же, как и для последовательности аг... а, з аеы а; аз~.г...ач, 1 ( г ( Х. Очевидно, что нет никаких отличий между этими двумя случаями, пока (г+ 1)-й ключ второй последовательности не попадает в позицию, занимаемую г-м ключам в первой йоследовательности.
Однако тогда г- и (г + 1)-й элементы просто меняются местами, так что количество проб для (г + 1)-го ключа уменыпается на столько же,. на сколько увеличивается число для 1-га ключа. 1 Согласно теореме Р средняя длина поиска дгя хеш-последовательности аз аг... ал может быть определена из чисел Ьо Ьг... 6м м где 6, представляет собой количество элементов агн равных г» По этой последовательности можно определить "последовательность переносов" со сг... см з, где с. равна числу ключей, для которых при вставке ключа проверяются обе позиции (~ и ) — 1).
Эта последовательность определяется правилом О, если Ь, = сбэ1>,о м = О; с,= Ьз + сО з~ о м — 1 в противном случае. (44) 1+ (со+ сг + + см-з)/Ф. (45) Кажется, что правило (44) представляет собой циклическое определение чисел с через самих себя. но в действительности при любом Х ( М система имеет единственное решение (см. упр. 32).
Шей и Спрут испольэовали эту идею зля определения вероятности Чь того, что с, = Ь через вероятности рь того, что »г = Ь. (Эти вероятности не зависят от у.) Таким образом, Чо = РоЧо + Рз Чо + РоЧм Чг = РгЧо + РгЧг + РоЧг, Чг = РзЧо + РгЧ1 + РгЧг + РоЧз (4б) и т. д., поскольку, например, вероятность того, что с = 2, представляет собой вероятность того, что Ь, + с~ э1~ „„о м — — 3. Пусть 8(г) = 2.рьго и С(г) = 2 Чьгь— Например, пусть М = 1О, г1' = 8 и Ьо... Ьо = О 3 2 О 1 О О О О 2; тогда со...
со —— 2 3 1 О О О О 1 2 3, поскольку один ключ должен быть перенесен из позиции 2 в позицию 1, три . — из позиции 1 в позиции> О, два — из позиции О в позицию 9 и т. д. Имеем Ьо + Ь, + . + Ьм з = Ю, и среднее количество проб, необходимых для выборки Л ключей, составляет производящие функции для этих распределений вероятностей; уравнения (46) эк- вивалентны формуле В(з)С(э) = родо+ (до — родо)з+ щ-~+ = рода(1 — г) + сС(з).
Поскольку В(1) = 1, можно записать В(х) = 1+ (г — 1)Р(э). Отсюда вытекает, что С родо 1 — Р(1) 1 — Р(г) 1 — Р(э) ' (47) так как С(1) = 1. Среднее количество проб, необходимых для выборки, в соответ- ствии с (45) составляет И, и Р'(1) И В (1) (48) В связи с тем, что предполагается равновероятность всех хсш-последовательностей аы .. ам, имеем рь = рг(ддя фиксированного т' в точности й из о, равны у) =(")Й)'(-6) " (49) следовательно, В(х) = (1+ — ), В'(1) = —, В"(1) = (50) и среднее количество проб согласно (48) составит Си = -~1+ ).
(51) В состоянии ли читатель указать неверные рассуждения, вызвавшие отличие между полученным ответом и точным результатом в теореме К? (См. упр. ЗЗ.) Анализ оэттимальности. Мы рассмотрели несколько примеров последовательностей проб для открытой адресации, в результате чего, естественно, возникает вопрос, какая из них наилучшая из еозжожнмт в некотором разумном смысле. Эта задача имеет интересную постановку, предложенную Д. Д.
Ъ'.вьманом (3. Р. 1'11- шал) [Х4СМ 19 (1972), 569-575): вместо того чтобы вычислять хеш-адрес Ь(К), мы отображаем каждый ключ К на перестановку множества (О, 1....., М вЂ” 1), которая представляет последовательность проб прн использонании К. Каждой из Ы! перестановок назначена вероятность, и предполагается, что обобщенная хешфункция выбирает каждую перестановку с этой вероятностью. Вопрос формулируется следующим образом: "Какое назначение вероятностей данным перестановкам даст наивысшую производительность, т.
е. минимизирует соответствующие средние числа проб С, и С~ч".! Например, если назначить каждой перестановке вероятность 1/ЛХ!, то получится равномерное исследование, проанализированное в (32) и (34). Однако Ульманом был найден пример с ЛХ = 4 и Зд = 2, для которого С' меньше, чем значение уь, полученное для равномерного исследования. Его построение назначает нулевые значения всем перестановкам, кроме следующих шести.
Перестановка Вероятность Перестановка Вероятность 01 2 3 (1+ 2е)/6 1 0 3 2 (1+ 2~)/6 (52) 2 О 13 (1 — г)/6 2 1 О 3 (1 — е)/6 3 О 1 2 (1 — е)/6 3 1 0 2 (1 — е)/6 Грубо говоря, на первом шаге предпочтение отдается 2 или 3, а вторая проба всегда проверяет 0 или 1. Среднее количество проб, необходимых для вставки третьего элемента, Сз, равно т — 1с+ 0(е~), так что можно улучшить равномерное исследование, присвоив с малое положительное значение. Однако соответствующее значение С,' для этих вероятностей составляет ей + 18 0(с), что больше Л~ (значение для равномерного исследования).
Ульман доказал, что любое назначение вероятностей, такое, что С~ < (М + 1Ц(М + 1 — Л), для некоторого Л всегда влечет справедливость С„' > (М+1)/(М+1 — и) для некоторого и < Л'; нельзя все время побеждать равномерное хеширование...
В действительности количество проб прн успешном поиске является лучшим критерием, чем С~,. Перестановки в (52) не приводят к улучшению значения Сгг для любых Л', и Ульман предположил, что никакие назначения вероятностей не сделают Ся меньше, чем для равномерного исследования; ((М + 1)/Л')(Нмь1 — Нэг.ь1 я). Эндрю Яо (Апбгев Уао) доказал асимптотнческую форму этого утверждения, показав, что предельная цена при Л' = аМ и М -э оо всегда > — ' 1и —,', [иАСМ 32 (1985), 687-693). Строгую форму предположения Ульмана очень сложно доказать. в особенности потому, что существует много вариантов назначения вероятностей для получения эффекта равномерного исследования; нет необходимости назначать вероятности 1/ЛУП каждой перестановке.
Например, следующие назначения также дают эквивалент равномерного исследования. Перестановка Вероятность Перестановка Вероятность 0123 1/6 0213 1/12 1230 1/6 1320 1/12 (53) 2301 1/6 2031 1/12 3012 1/б 3102 1/12 (Остальным шестнадцати перестановкам назначена нулевая вероятность.) Следующая теорема характеризует все присвоения, дающие поведение равномерного исследования. Теорема 11. Назначив вероятности перестановкам, все ( .) конфигурации пустых м и занятых ячеек можно сделать равиовероятными после Л вставок для 0 < Х < М тогда и только тогда, когда сумма вероятностей, назначенная всем перестановкам, первые Л' элементов которых являютгя членамп данного Х-элементного множества, равна 1/(,„,) для всех Л' и для всех Л -элементных множеств.
Например, сумма вероятностей, назначенных каждой из 3!(М вЂ” 3)! перестановок, которые начинаются числами (О, 1, 2) в заданном порядке, должна составлять 1/(з) = 3!(М вЂ” 3)!/ЛП. Заметьте, что (53) удовлетворяет условию теоремы, поскольку 1/6 + 1/12 = 1/4. Доказотельстпво. Пусть А С (О, 1,..., ЛХ вЂ” 1) и пусть П(А) — множество всех перестановок, первые )А) элементов которых являются членами А. Обозначим также через Я(А) сумму вероятностей, назначенных этим перестановкам. Пусть Рл(А)— вероятность того, что первые ).4) вставок при помощи процедуры открытой адресации 'займут места, определенные множеством А, и последняя вставка при этом потребует ровно )л проб. П, наконец, пусть Р(А) = Р1 (.4) ь Ра(А) + .. Доказательство проводится по индукции по У ) 1. Предположим, что Р(А) = 5(А) = 1/( ) для всех множеств А с ~А) = и < Х Пусть  — некоторое У-элементное множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
