AOP_Tom3 (1021738), страница 156
Текст из файла (страница 156)
Тогда Рл(В) = Е Е Рг(т)Р(В ~ (кл)), Айн леп(А) )А)=л где Рг(к) представляет собой вероятность, назначенную перестановке к., и кл — ее и-й элемент. По инлукции Рл(В) = ~~, ~ Рг(к), АСлв (Х вЂ” 1) ТЕЩА) )А)=л что равняется ( )/(, )( ) при й<Х. Следовательно, ю — 1 (к) ч Р(В) = †„ (В(В) + ~ (л -1) ~ л=~ ( л ) а это может быть равно 1,/(л,) тогда и только тогда, когда Я(В) имеет корректное значение.
1 Внешний поиск. '1ехнология хеширования нполне подходит для внешнего поиска на устройствах хранения с прямым доступом наподобие дискон или барабанов. Для таких приложений, как и в разделе 6.2.4, желательно минимизировать количество обращений к файлу. Это условие двояко влияет на выбор алгоритмов. 1) Разумно потратить больше времени на вычисление хеш-функции, поскольку потери из-за плохого хеширования гораздо больше цены дополнительного времени, требуемого для аккуратного выполнения вычислений. 2) Записи обычно группируются н страниць~ или блоки с тем, чтобы за один раз извлекать из внешней памяти несколько записей.
Файл делится на М блоков по Ь записей. 14оллизии при этом не вызывают никаких проблем до тех пор, пока одинаковые хеш-адреса имеют ие более Ь ключей. Похоже, что наилучшими методами разрешения коллизий являются следующие. А) Исгшльзоаание цепочек с раздельнеими списками. Если в один и тот же блок попадает более Ь записей, в конце первого блока можно вставить ссылку на переполняющую запись. Такие переполняющие записи содержатся в специальной обласши переполнения.
Обычно не имеет смысла разбивать область переполнения на блоки, поскольку, как правило, возникает сравнительно немного переполнений; таким образом, 'лишние" записи связываются однао другой, поэтому (6+6)-я запись списка требует 1+ 6 обрашений. Обычно стбит оставлять место для переполнений в каждом цилиндре дискового файла, чтобы как можно больше обращений оставалось в пределах одного и того же цилиндра. Хотя этот метод обработки переполнений кажется неэффективным, статистически число переполнений достаточно мало для того, чтобы среднее время поиска оставалось очень хорошим.
В табл. 2 и 3 показаны средние количества требуемых обращений как функций коэффициента заполненности о =- 7х'/АХ6 (54) для фиксированного о и МнУ -э оо. Любопытно, что при о = 1 асимптотическое количество обращений для неудачного поиска увеличивается с ростом 6. Таблица 2 СРЕДНЕЕ КОЛИЧЕСТВО ОВРАЩЕНИЙ В СЛУЧАЕ НЕУДАЧНОГО ПОИСКА ПО РАЗЛГЛЬНЫМ ЦЕПОЧКАМ Коэффициент заполнения, о 10% 20% 30% 40% 50% 60% 70% 80% 90% 95% Размер блока, 6 Таблица 3 СРЕДНЕЕ КОЛИэ1ЕСТВО ОБРАЩЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПОИСКА ПО РАЗДЕЛЬНЫМ ЦЕПОЧКАМ Коэффициент заполнения, а 30% 40% 50% 60% 70% 80% 90% 95% Размер блока, 6 10% 20% 1.0500 1.1000 1.0063 1.0242 1.0010 1.0071 1.0002 1.0023 1.0000 1 0008 1.0000 1.0000 1.0000 1.0000 1 0000 1.0000 1.350 1.400 1.450 1.48 1.238 1.299 1.364 1.40 1.181 1.246 !.319 1.36 1.145 1.211 ! 290 1.33 1.119 1.186 1 268 1.32 1.056 1.115 1.206 1.27 1.018 1.059 1.150 1 22 1.001 1.015 1.083 1 16 В) Испольэоеание срастпающияся цепочек, Можно не выделять специальную область переполнения, а адаптировать алгоритм С для работы с внепшими файлами.
Для каждого цилиндра может поддерживаться двусвязный список свободного пространства, связывающий совместно все не полностью заполненные блоки. При исполь- 1 2 3 5 10 20 50 1 2 3 4 5 10 20 50 1.0048 1.0012 1.0003 12!001 1.0000 1.0000 1.0000 1. 0000 1.0187 1.0088 1.0038 1.0016 1.0007 1.0000 1 0000 1.0000 1.0408 1.0703 1,1065 1.0269 1.0581 1,1036 1.0162 1.0433 1.0898 1.0095 1.0314 1,075! 1.0056 1.0225 1 06!9 1.0004 1.0041 1.0222 1 0000 1.0001 1.0028 1.0000 1.0000 1.0000 1.1500 1.2000 1.2500 1.0520 1.0883 1.1321 1 0215 1 0458 1.0806 1.0097 1.0257 1.0527 1.0046 1.0151 1.0358 1.0002 1.0015 1.0070 1,0000 1,0000 1.0005 1.0000 1.0000 1 0000 1.
1488 1. 1638 1.1588 !.!476 1.!346 1.0773 1.0234 1 0007 1.3000 1.1823 1.1259 1.0922 ! 0699 1.0226 1.0038 1.0000 1,197 1.249 1.238 1.327 1 252 1.369 1.253 1.394 1.249 1 410 1.201 1.426 1.113 1.367 !.018 1.182 1.307 1.34 1.428 1,48 1 509 1.59 1.571 1.67 1.620 1.74 1 773 2.00 1.898 '2.29 1.920 2.70 Таблица 4 СРЕДНЕЕ КОЛИЧЕСТВО ОБРАЩЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПОИСКА ПРИ ЛИНЕЙНОМ ИССЛЕДОВАНИИ Коэффициент заполнения, а 20% 30% 40% 50% 60% 70% 80% 90% 95% Размер блока. 5 10% 5.500 10.50 3.147 5.64 2.378 4.04 2.000 3.24 1.777 2.77 1.345 1.84 1.144 1,39 1 040 113 2.167 3.000 1.494 1.903 1.286 1.554 1.190 1.386 1.136 1.289 1,042 1.110 1.010 1.036 1.001 1.005 1.1250 1.0242 1.0066 1.0021 1.0007 1.0000 1 ОООО 1.0000 1.0556 1.0062 1.0009 1.0001 1.0000 1.0000 1.0000 1.
0000 1.2143 1.3333 1.5000 1.7500 1.0553 1.1033 1.1767 1,2930 1.0201 1.0450 1.0872 1.1584 1,0085 1.0227 1.0497 1.0984 1.0039 1 0124 1.0307 1 0661 1.0001 1.0011 1.0047 1.0154 1 0000 1.0000 1.0003 1.0020 1.0000 1 ОООО 1.0000 1.0000 1 2 3 4 10 20 50 Анализ методов А и С влечет очень интересные с математической точки зрения выводы; здесь мы приведем лишь некоторые результаты, поскольку подробности приводятся в упр.
49 и 55. формулы содержат две функции, тесно связанные с (,)-функциями из теоремы К, а именно: В(а, и) — + + + (55) и+ 1 (я+ 1)(в+ 2) (и+ 1)(п+ 2)(в+ 3) (ап) "+ (и + 3)! 7' (ап)" (ап)" ' е — ПО лваП (1 — (1 — а) 77(а, и) ) . и! (56) С помощью этих функций среднее число обращений, выполняемых при неудачном поиске по методу А, выражается как зовании этой схемы в каждом блоке содержится счетчик, указывающий количество пустых позиций записей. Такой блок удаляется из двусвязного списка только по достижении счетчиком нулевого значения.
Для распределения переполнений может применяться "блуждающий указатель" (см. упр. 2.5 — 6) с тем, чтобы различные цепочки использовали различные блоки переполнения. Этот метод все еще не проанализирован, но моясет быть весьма полезен. С) Использование открытой адресации. Можно обойтись и без ссылок и использовать поткрытыйп метод. При рассмотрении внешнего поиска линейное исследование, вероятно, лучше случайных проб, потому что величина с зачастую может быть выбрана таким образом, чтобы минимизировать скрытые задержки между последовательными доступами. Приближенная теоретическая модель линейного исследования, с которой мы работали ранее, может быть обобщена для учета влияния блоков.
Она показывает, что линейное исследование в самом деле вполне удовлетворительно, пока таблица не слишком заполнена. Например, взгляните на табл. 4; при коэффициенте заполненности. равном 90%, и размере блока, равном 50, среднее количество обращений при успешном поиске равно всего лишь 1.04. Это даже лучше, чем требуемые при использовании метода цепочек (А) с тем же размером блока 1.08 обращения! См —— 1+ аЬЬ6(о) + 0( — ) Г11 (,М) (57) при М,Л' -ь оо, а соответствующее число при успешном поиске может быть записано как с — ьаЬьоь г См = 1+ (2+ (о — 1)Ь+ (о~+ (о — 1) (Ь вЂ” 1))й(о,Ь)) + 0( — ). (58) 25! '1М/' Предельные значения соответствуют величинам, приведенным в табл. 2 и 3. Поскольку метод цепочек (А) требует отдельной области переполнения, необходимо оценить количество возможных переполнений.
Среднее число переполнений составляет М(С~, — 1) = №6(о), так как С~, — 1 — среднее число переполнений в любом данном списке, Таким образом, табл. 2 может использоватьгя для нахождения требуемого размера области переполнения. Для фиксированного а стандартное отклонение общего количества переполнений будет примерно пропорционально ь/ЬМ при М -ь оо. Асимптотические значения С)ч и См приведены в упр.
53, однако эти приближения не очень хороши при малых Ь или больших сс К счастью, ряд для В(о, и) сходится очень быстро даже при больших оа так что формулы могут быть вычислены с любой же.тательной точностью без больших трудностей. Максимальное значение достигается при а = 1,. когда при Ь -6 со /Ь шах СС = 1+ = 1/ — + 1+ О(Ь '~2), Ь! 'Ь/ 2я е — ЬЬ6 шах См —— 1+, (Я(Ь) -Ь 1) = — + ь/ + 0(Ь ') (59) (60) согласно приближению Стирлинга и анализу функции 71(п) = Л(1, и) — 1 (см.
раздел 1.2.11,3). Среднее количество обращений при успешном внешнем поиске с помощью линейньго исследования имеет необыкновенно простой вид: Сю 1 + Йь(о) + 126(о) + ЙЬЬ(о) + " (61) Эту формулу можно пояснить следующим образом: общее среднее количество обращений при поиске всех Х ключей равно Л2См, что представляет собой Х + Ть + Т2 +, где Ть — среднее количество ключей, требующих более Ь обращений. Теорема Р гласит, что ключи можно вставлять в любом порядке без влияния на См, отсюда следует, что Ть равно среднему числу переполняющих записей, которые имелись бы при использовании метода цепочек с М/Ь блоками размером ЬЬ, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
