Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 46
Текст из файла (страница 46)
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 1,13 1.0556 1,1250 1.2143 1,3333 1.0062 1.0242 1.0553 1.1033 1.0009 1.0066 1.0201 1.0450 1.0001 1.0021 1,0085 1.0227 1.0000 1.0007 1.0039 1.0124 1.ОООО 1.0000 1.ООО1 1.0011 1.ОООО 1.ОООО 1.ОООО 1.ОООО 1.ОООО 1.ОООО 1.ОООО 1.ОООО 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.5000 1.7500 1.1767 1.2930 1.0872 1.1584 1.0497 1,0984 1.0307 1.0661 1.0047 1.0154 1.0003 1.0020 1.0000 1.0000 1 2 3 5 10 20 50 Анализ методов А и С влечет очень интересные с математической точки зрения выводы; здесь мы приведем лишь некоторые результаты, поскольку подробности приводятся в упр.
49 и 55. Формулы содержат две функции, тесно связанные с Я-функциями нз теоремы К, а именно: и 2,„ и о В(о, и) — + и+ 1 (и+ 1)(и+ 2) (и+1)(и+ 2)(и+ 3) + + (55) / (О~ )и ( )о+2 (Оп)а+2 1„(о) =е ~ +2 +3 — +. ° . 1(п+1)! (и+2)! (и+3)! е ""п'"о" (1 — (1 — а) й(а, и) ) . (56) С помощью этих функций среднее число обращений, выполняемых при неудачном поиске по методу А, выражается как зовании этой схемы в каждом блоке содержится счетчик, указывающий количество пустых позиций записей.
Такой блок удаляется из двусвязного списка только по достижении счетчиком нулевого значения. Для распределения переполнений может применяться "блуждающий указатель" (см. упр. 2.5-6) с тем, чтсбы различные цепочки использовали различные блоки переполнения. Этот метод все еще не проанализирован, но может быть весьма полезен. С) Испааьзование аткрмтао адресации. Можно обойтись и без ссылок и использовать "открытый" метод. При рассмотрении внешнего поиска линейное исследование, вероятно„лучше случайных проб, потому что величина с зачастую может быть выбрана таким образом„чтобы минимизировать скрытые задержки между последовательными доступами.
Приближенная теоретическая модель линейного исследования. с которой мы работали ранее, может быть обобщена для учета влияния блоков. Она показывает, что линейное исследование в самом деле вполне удовлетворительно, пока таблица не слишком заполнена. Например, взгляните на табл. 4: при коэффициенте заполненности, равном 90%, и размере блока. равном 50, среднее количество обращений при успешном поиске равно всего лишь 1.04. Это даже лучшие, чем требуемые при использовании метода цепочек (А) с тем же размером блока 1.08 обращения! /1з С~, = 1+ айь(а) + О( — ) (.му при М,Х -+ оо, а соответствующее число при успешном поиске может быть записано как -ьЯЬьаь г г1х См = 1+ (2+ (а — 1)Ь+ (а + (а — 1)г(Ь вЂ” 1))11(а,Ь)) + О( — ~.
(58) 2Ы (,м1' Предельные значения соответствуют величинам, приведенным в табл. 2 и 3. Поскольку метод цепочек (А) требует отдельной области переполнения, необходимо оценить количество возможных переполнений. Среднее число переполнений составляет ЛХ(Сч — 1) = №ь(а), так как С~ — 1 — среднее число переполнений в любом данном списке. Таким образом, табл.
2 может использоваться для нахождения требуемого размера области переполнения. Для фиксированного а стандартное отклонение общего количества переполнений будет примерно пропорционально ~/ЛХ при М -ч оо. Асимптотические значения С~а, и Ся приведены в упр. 53, однако зти приближения не очень хороши при малых Ь или больших а.
К счастью, ряд для 11(а, и) сходится очень быстро даже при болыпих а, так что формулы могут быть вычислены с любой желательной точностью без больших трудностей. Максимальное значение достигается при а = 1, когда при 6 -~ оо е ььь+1 Г 6 щахС~ = 1+ — = ~( — +1+ 0(6 '~г), Ь. 'у' 2 е ба шахСм = 1+ — (11(6)+ Ц = -+ 14( — +0(6 ') 26! 4 т' 9хЬ (59) (60) согласно приближению Стирлинга и анализу функции 11(п) = В(1,п) — 1 (см. раздел 1.2.11.3). Среднее количество обращений при успешном внешнем поиске с помощью линейного исследования имеет необыкновенно простой вид: См ж 1+ гь(а) + 1гь(а) + ггь(а) + (61) Эту формулу можно пояснить следующим образом: общее среднее количество обращений при поиске всех К ключей равно Л'Свч что представляет собой А'+ Тг + Тг +, где Ть — среднее количество ключей, требующих более Ь обращений.
Теорема Р гласит, что ключи можно вставлять в любом порядке без влияния на См; отсюда следует, что Тг равно среднему числу переполняющих записей, которые имелись бы при использовании метода цепочек с Л1/й блоками размером ЬЬ, т. е. №ы(а), как и говорилось выше. Подробный анализ формулы (61) приводится в упр. 55. Обсуждение практических вопросов построения внешних хеш-таблиц дано Чарльзом Л. Ольсоном (С)гаг!ев А. 01воп) (Ргос. АСМ Хай СопК 24 (1969), 539- 549). В его работу включено несколько практических примеров; в ней указано, что количество переполняющих записей значительно увеличивается, если файл служит объектом частых вставок/удалений без перемещения записей, В работе также представлен анализ этой ситуации, выполненньгй совместно с Дж. А. деПейстером (1.
Л. ЙеРеузгег). Сравнение методов. Мы изучили много различных методов поиска, однако какой метод лучше выбрать для конкретного прнложенияу Б нескольких словах невозможно из.ложить все, что хотелось бы учесть при выборе метода поиска; однако следующие соображения представляются наиболее важными в отношении скорости работы алгоритма н объема памяти, требуемой этими методами. На рис. 44 представлены результаты анализов алгоритмов, проведенных в данном разделе, и показано, что различные методы разрешения коллизий приводят к различному числу проб. Однако количество проб — не единственный критерий, так как прн использовании разных методов на проведение пробы требуется разное время, что существенно влияег на время работы и целом (см.
рис. 42). При линейном исследовании приходится значительно чаще по сравнению с другими методами. показанными на рис. 44, обращаться к таблице, зато этот метод чрезвычайно прост, Кроме того, линейное исследование — не такой уж плохой метод: при заполненности таблицы на 90% алгоритм Ь требует в среднем меньше 5.5 проб для поиска в таблице случайного элемента (впрочем, при 90% заполненности таблицы алгоритм Ь нуждается в примерно 50.5 пробах для вставки каждого нового элемента). Как показано на рис. 44,метод цепочек очень экономичен с точки зрения числа проб и не экономичен с точки зрения требуемой дополнительной намятн для хранения полей ссылок, что особенно неприятно прн наличии малых записей. При этом более выгодным по сравнению с методом цепочек становится метод открытой адресации.
Так, при выборе между таблицей с цепочками объемом 500 элементов и таблицей с открытой адресацией объемом 1 000 элементов последняя явно предпочтительнее, поскольку обеспечивает эффективный поиск среди 500 записей и вмещает в два раза больше данных. С другой стороны, иногда в силу размера записей или специфики используемого формата можно получить место для полей ссылок фактически бесплатно (см. упр. 65), Как ведут себя методы хеширования по сравнению с другими методами поиска, изученными в этой главе? С точки зрения скорости работы они лучше других методов при большом количестве записей, поскольку среднее время поиска при хешметоде остается ограниченным, когда Л -+ оо, если таблица не становится слишком заполненной. Например, программа Ь требует всего лишь 55 единиц времени для успешного поиска при заполненной на 90% таблице, что быстрее самой быстрой йХХ-программы (см. упр.
6.2.1-24) при )э' > 600, и цена этой скорости составляет 11% пространства. Более того, бинарный поиск годится только для фиксированных таблиц, в то время как хеш-таблицы позволяют делать эффективные вставки. Можно также сравнить программу Ь с метелями поиска, ориентированными на работу с деревьями, которые позволяют выполнять динамические вставки. Программа Ь при таблице, заполненной на 90%, работаег быстрее, чем программа 6.2.2Т при Х > 90, и быстрее, чем программа 6.30 (упр.
6.3-9) при Ж > 75. Только один метод из рассмотренных в данной главе эффективен в случае удачного поиска и не перерасходует память — это модификация Брента алгоритма О. Метод Брента позволяет поместить Х записей в таблицу размером М = Х + 1 и найти любую запись в среднем за 2.5 пробы. При этом не требуется дополнительное пространство для полей ссылок или битов дескрипторов; однако неудачный поиск может оказаться весьма медленным (для него может потребоваться около )У/2 проб). 3 е з % о 1 0 О.! 0.2 0.3 0,4 0.5 0.6 0.7 0.3 0.9 1,0 Коэффициент заполненности, о = !Е/М (а) Яе1мачные поиск 3 в и и 3 й о Р 2 и О 0.1 0.2 0.3 0.4 ОЛ 0.6 0.7 0.8 0.9 1.0 Коэффициент заполненности, а = У/М (Ъ) Удачныа попок Рис.
44, Сравнение методов разрешении коллизий: предельные значения среднего количества проб прн М -е оо. Таким образом, хеширование имеет ряд преимушеств. С другой стороны, есть три важных аспекта, по которым хеширование уступает рассмотренным ранее ме. толам А) После неудачного поиска в хеш-таблице известно только то, что искомый ключ отсутствует в таблице, а методы, основанные на сравнении ключей, всегда дают дополнительную информацию, например позволяют найти наибольший ключ < К и/или наименьший ключ > К». Во многих приложениях получить такую информацию крайне важно; -например, она позволяет интерпслировать функцию » Впрочем, поскольку мы говорим о неудачном поиске, приведенные автором неравенства ставоввтсн строгими. — Прим.
иерее. по ее табличным значениям или использовать алгоритм, основанный на сравнении ключей для поиска всех ключей, лежащих между двумя данными значениями К и К', Кроме того, алгоритмы поиска по дереву нз раздела 6.2 позволяют легко представить содержимое таблицы в порядке возрастания без отдельной сортировки. В) Часто очень сложно распределить память для хеш-таблицы — для нее следует заблаговременно выделить область памяти, и не всегда удается заранее сказать, какой размер необходим. Выделяя слишком много памяти, можно тем самым ограничить объем памяти для других списков или других пользователей; при выделении недостаточного количества памяти произойдет переполнение таблицы.
В противоположность этому методу алгоритмы поиска и вставки по дереву никогда не увеличиваются сверх необходимого размера. В среде с виртуальной памятью можно локализовать обращения к памяти при выполнении поиска по дереву (или цифрового поиска по дереву), в то время как при создании большой хеш-таблицы необходимо обращаться к операционной системе, чтобы получить доступ к новой странице памяти почти всякий раз при хешировании очередного ключа. С) Наконец, нужно свято верить в теорию вероятностей, применяя методы хеширования, поскольку они эффективны только в среднем, в то время как наихудшие случаи просто ужасны. Как и при использовании датчиков случайных чисел, никогда нельзя быть абсолютно уверенным в том, что хеш-функция будет удовлетворительно работать с новым множеством данных.
Таким образом, хеширование — не самый подходящий метод для некоторых приложений реального времени (наподобие контроля за дорожным движением), когда на карту поставлены человеческие жизни. Алгоритмы сбалансированных деревьев из разделов 6,2.3 н 6.2.4 более безопасны, поскольку обеспечивают гарантированную верхнюю гранину времени поиска. История. Идея хеширования впервые была высказана Г. П. Ланом (Н. Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
