Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 14
Текст из файла (страница 14)
упр. 12). Еще один вариант бинарного поиска, который осуществляется быстрее всех опасаммык при очень больших Х, обсуждается в упр. 23. Но в упр. 24 вы найдете еще более быстрый метод... ейоиск Фибоиаччи. При рассмотрении многофазного слияния мы видели, что числа Фибоначчи могут играть такую же роль, что и степени чигша 2. Подобное явление наблюдается и при поиске, где числа Фибоначчи позволяют разработать альтернативу бинарному поиску.
Для некоторых компькперов предлагаелгый метод предпочтителен в связи с тем, что в нем используются только сложение и вычитание (без деления на 2). Следует различать процедуру, которую мы начинаем обсуждать, и важный численный метод, также называемый "'поиском Фибоначчи", используемый для поиска максимума унимодальной функции (см. ЯЬопассг' Япаггег1у 4 (1966), 265-269).
Совпадение названий* нередко приводит к недоразумениям! Технология поиска Фибоначчи, на первый взгляд, представляется весьма загадочной, и, если просто взять программу и постараться понять, как она работает, вам покажется, что это полное шаманство. Однако шаманство превратится в обычный танец с бубном„как только мы построим соответствующее дерево поиска. Поэтому наш рассказ начнется с деревьев Фнбомаччи. На рис. 8 показано дерево Фибоначчи порядка 6. Оно больше похоже на реальный, не очень хороню подстриженный куст, чем на другие деревья, которые мы рассматривали. Возможно, зто связано с тем, что многие природные процессы описьгвакпся законом Фибоначчи.
В целом, дерево Фнбоначчи порядка Ь имеет Гвег — 1 внутренних (на рисунке — - круглых) н Геч.г внешних (на рисунке— квадратных) узлов. Строится оно следующим образом. Если Ь = О или )с = 1, дерево вырождается в ( Е. Если Ь > 2, .корнем является Гв; левое полдерево представляет собой дерево Фибоначчи порядка )г — 1; правое поддерево представляет собой дерево Фибоначчн порядка )с — 2 с числами, увеличенными на Ке. Обратите внимание на то, что, за исключением внешних узлов, числа двух дочерних узлов каждого внутреннего узла отличаются от него на одну и ту же величину, и зта величина — не что иное, как число Фибоначчи (например, на рассматриваемом рисунке 5 = 8 — Рв и 11 = 8+ Гв).
Если разница на каком-либо уровне составляет Рз, то на следУющем УРовне она бУдет Равна гу г длЯ левой ветви и гУ з — длЯ правой. Так, например, 3 = 5 — Гз, а 10 = 11 — Х~. Комбинируя эти наблюдения с механизмом распознавания внешних узлов, мы получим следукхций алгоритм поиска. Алгоритм У (Поиск Фибомаччи (Ггбопассгагг веагсй)). Дана таблица записей Кг Вз ...Вн, ключи которых расположены в порядке возрастания Кг < Кз « . Кяь Алгоритм осуществляет поиск заданного аргумента К. ' Нужно отметить, что в английском языке чеков совпадение превращается в обычную свежесть; метод поиски, который мы будем рвссматриватгь именуется "Иьопвсювп венгсЬ", а метод поиска максимума уннмодвльной Функции — "Р1ьопвгс) вевгсЬ".
— Лрнвс перев. Рис. 8. Дерево Фибоначчи порядка б. Для удобства описания предполагается, что Ю + 1 представляет собой число Фибоиаччи ге+1 (выполиив соответствуюшую инициализацию, алгоритм несложно распространить иа любые значения К; см. упр. 14). Е1. )Ииициализация.) Устаиовиты е- Гы р +- г» ы е +- ге я. 1В описании этого алгоритма р и о означают последовательиые числа Фибоиаччи.) г2. )Сравиеяие.) Если К с Ко перейти к шагу гЗ; если К > К„перейти к шагу Р4; если К = К„алгоритм успешно завершаетси, Р3. )Умеиьшеиие Ц Если О = О, алгоритм завершается неудачно. В противном случае следует устаиовить1 е- 1-д и (р,д) +- ~б,р-д); затем перейти к шагу г2. г4.
)Увеличеиие 1,) Если р = 1, алгоритм завершается иеудачио. В противном случае следует сиачала установить 1 +- 1+ о, р +- р — е, а затем — 4 е- д — р и перейти к шагу Р2. $ В приведенной ниже Х1Х-реализации алгоритма используется дублирование виутреииего цикла для повьппеиия скорости работы. В одном из циклов р хранится в г12, а 4 — в г13; в другом цикле регистры меняются ролями. В действительяости в регистрах хранятся зиачеиия р — 1 и д — 1, что облегчает проверку "р = 1?'" иа шаге г4.
Программа Г шеиий; гА ш К, 01 ЯТАЕТ ЫА ОО ЕМТ1 ОЮ ЕЫТ2 04 ЕЯТЗ 05 ОНР 06 Р4А 1МС1 07 ВЕС2 08 ВЕСЗ ОО Г2А СНРА 10 Л. Л ЛЕ 1гуоиск Фибоначчи). Мы придерживаемся предварительных соглаг11 из 1, 1г12 или г13) ш р — 1, ~г13 или г12) изб — 1. К ~~. и ре 1 ~е-р». Ре-~ 1 1 р+- га-ь Г -1 1 о е- Гь-и Г2А 1 Переход к шагу Г2. 1,3 С2 — Я вЂ” А ги Увеличениеб гф-г'+Ф 13 С2 — Я вЂ” А Р 1,2 С2 — Я вЂ” А 4+- Ч вЂ” Р ЕЕТ„1 а и шиииж РЗА С Переход к шагу РЗ, если К < К,.
ВОССЕЯЕ С2 Выход, е«ли К = Кь 19 12И2 Р4А С2 — Я 16 ЛМР РАПЛВЕ А 14 Рзй Вес1 1,з С1 16 ВЕС2 1,З С1 16 ЛЗММ Р2В С1 1? ЗИР РАПЛВЕ 1 — М вЂ” А 16 Р4В 1МС1 1,2 19 ВЕСЗ 1,2 96 ВЕСг 1.З И Р2В СИРА КЕ?,г йй Л. РЗВ ау ЗЕ ВВССЕЗЗ 64 АЗИЗ Р4В 66 ЗИР РА110ВЕ 96 РЗВ 0ЕС1 1,2 97 ВЕСЗ 1,2 96 12ИИ Р2А 99 ЛИР РА ПЛИЕ 1 Время работы этой программы анализируется в упр.
18. Из рис. 8 видно (и анализ это доказывает), что левая ветвь выбирается чаще, чем правам. Обозначив количество выполнения шагов Р2„РЗ и Р4 через С, С1 н (С2 — Я) соответственно, получим Переход к шагу Р4, если р ф 1. Выход при отсутствии в таблице. пхшо~г — д. р+ Р ч. Обмен регвстрамн прн у > О. Выход при отсутствии в таблице. (Строки 16-29 параллельны строкам 06-17.) С = (ате 4А/~/5+ О(1), п1ах А — 1), С1 = (ате А/Я+ О(1), шах А — 1), (8) С2 — Я = (ате Ф 'А/~/5+ О(1), шах )А/2)). Таким образом, левая ветвь выбирается примерно в <6 ш 1.618 раз чаще, чем правая (вполне понятный и предсказуемый результат, поскольку после каждого сравнения оставшийся интервал делится на две части; левая часть при этом приблизительно в И раз больше правой), В итоге суммарное среднее время работы программы Р составляет около -'((18+ 4ф)А+ 31 — 260)и ш (705018%+ 1 08)и (9) для успешного поиска плюс (9-Зф)и ш 4.15и — для неудачного.
Это меньше, чем в случае использования программы С, хотя наихудшее время работы (около 8.61х Ф) несколько больше. Иитерполяциоииый поиск. Забудем ненадолго о компьютерах н посмотрим, как с задачей поиска справляется человек. Очень часто хорошпй алгоритм можно создать, проанализировав собственные действия в реальной жизни. Представьте, что вы ищете слово в словаре. Вероятно, вы не станете открывать словарь посередине и идти к странице, расположенной на 1/4 или 3/4 от начала, т. е. выполнять алгоритм бинарного поиска. Шансы на то, что вы воспользуетесь поиском Фибоначчи, просто смехотворны.
Но ведь вы находите нужное слово в словаре? Так как же вы это делаете? Если слово начинается с буквы А, вероятно, вы ищете его в начале книги. Во многих словарях есть ярлычки, которые позволяют мгновенно найти страницу, на которой начинаются слова на заданную букву. Данная технология ускорения История и библиография. Наиболее ранним известным примером рассортированного для упрощения поиска длинного списка элементов является известная вавилонская таблица обратиых величин Ииакибит-Ану, датируемая примерно 200 г.
до н. з. Эта глиняная табличка содержит более 100 пар звачений, которые представляют собой начало списка из приблизительно 500 многозначных шестидесятеричиых чисел и их обратных величин, рассортированных в лексикографическом порядке. Например, список включает последовательность 01 13 09 34 29 08 08 53 20 01 13 14 31 52 30 01 13 43 40 48 01 13 48 40 30 01 14 04 26 40 49 12 27 49 09 07 12 48 49 41 15 48 46 22 59 25 25 55 33 20 48 36 Сортировка 500 подобных чисел при помощи технологий тех времен является просто феноменальной! (См.
О, Е. КппгЬ, Яе)есгед Рарегз оп Сошригег Яс1епсе (СашЬНбйе ()п1ч. Ргезз, 1996), СЬартег Щ поиска вполне применима в мире компьютеров; о таких алгоритмах мы поговорим в разделе 6.3. Но и после этого первого шага ваши действия ничуть не похожи на то, что происходит при реализации какого-либо из рассмотренных алгоритмов. Если вы заметите, что искомое слово находится ближе к концу группы слов на нужную букву, вы просто пропустите изрядное количество страниц (или начнете поиск от следующей буквы к предььаущей).
Вот в чем состоит основное отличие ваших действий от действий, выполияемых в алгоритмах, для которых понятия "немного больше" и "существенно больше" одинаковы. Зти рассуждения приводят иас к алгоритму, который может быть назван инглерполлциоииым поиском: если мы знаем, что К находится между К1 и К„, следующую проверку мы будем делать примерно на расстоянии (К вЂ” К~)/(ʄ— К1) от 1 (в предположении, что ключи представляют собой числовые значения, близкие к арифметической прогрессии).
Асимптотически иитерполяциоиный поиск превосходит по своим характеристикам бинарный поиск, В то время как один шаг бинариого поиска уменьшает количество проверяемых записей от и до -и, один шаг интерпояяционного поиска 2 уменьшает зто количество до фа (если ключи распределеиы в таблице случайным образом). В результате интерполяциоиный поиск требует в среднем 1к16Ю шагов для уменьшеиия диапазона проверки от Х до 2 (см.
упр. 22). Однако имитационные вычислительные эксперименты показали, что интерполяциониый поиск ие настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика), Кроме того, типичные таблицы недостаточно случайны, да и разница между зиачениями 1х!я Х и 1яХ становится значитечьной только при больших Х (скажем, при Х = 2'~ = 65 536). Интерполяция наиболее успешно применяется на ранних стадиях поиска в большом внешнем файле; после того как диапазон поиска существенно уменьшится, следует перейти к бинарному поиску.
(В связи с этим заметим, что поиск в словаре представляет собой внешний поиск, о котором мы поговорим немного позже.) Представляется совершенно естественной сортировка числовых значений, однако отношение порядка для букв нли слов не столь очевидно. Тем не менее уже в наиболее древних алфавитах имелись последовательности букв, которые служили для их сравнения. Например, во многих библейских псалмах содержатся стихи, следующие друг за другом в строгом алфавитном порядке: первый стих начинается с альфы, второй — с беты и т. д., что облегчает запоминание. Часто стандартная последовательность букв использовалась семитами и греками для обозначения чисел*, например о,~З и у означали 1, 2 и 3 соответственно. Алфавитный порядок слов„который представляется сейчас естественным даже школьнику, был гораздо более поздним изобретением и потребовал немалой работы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
