AOP_Tom3 (1021738), страница 116
Текст из файла (страница 116)
В противном случае следует сначала установить с е — 1+ д, р е- р — О, а затем — о +- Π— р н перейти к шагу Е2. $ В приведенной ниже И1Х-реализации алгоритма используется дублирование внутреннего цикла для повышения скорости работы.
В одном из циклов р хранится в г12, а д — в г13; в другом цикле регистры меняются ролями. В действительности в регистрах хранятся значения р — 1 и д — 1, что облегчает проверку "р = 17е на шаге Е4. Программа Е шений; гА— : К, 01 БТАИТ ХРА 08 ЕИТ1 ОЯ ЕИТ2 04 ЕИТЗ ОО ЭИР 06 Р4А 1ИС1 07 РЕС2 08 РЕСЗ 00 Р2А СИРА 10 Л. 11 ЗЕ (Поиск Фибоначчи). Мы придерживаемся предварительных согла- г11 = 1, (г12 или г13) = р — 1, (г13 или г12) = 0 — 1. К гг. и Ре 1 г е-Гы Гь-г 1 1 р +- Ге Г, ,-1 1 Ч+- Гь-с.
Р2А 1 Переход к шагу Е2. 1,3 С2 — Я вЂ” А Г4 Увеличение г. г е- с+Ф 1,3 С2 — Я вЂ” А р+- р — Ф 1,2 С2 — Я вЂ” А О+- о — р. КЕУ,1 с гг.с РЗА С Переход к шагу РЗ, если К < Ко БРССЕЯЯ С2 Выход, если К = К,. С2 — Я А С1 С1 С1 1 — 3 — А Переход к шагу Е4, если р ф 1, Выход при отсутствии в таблице. ЕЗ. Уменьшение ь 1+-1 — 9. Р~ Р 4. Обмен регистрами при д > 9.
Выход при отсутствии в таблице. (Строки 18-29 параллельны строкам Об — 17.) ЯЫ 1 Время работы этой программы анализируется в упр. 18. Из рис. 8 видно (и анализ это доказывает), что левая ветвь выбирается чаще, чем правая. Обозначив количество выполнения шагов Е2, ЕЗ и Г4 через С, С1 и (С2 — Я) соответственно, получим С = (ате фй/~/5 + 0(1), шах А — 1), С1 = (аъе к/з/5+ 0(1), |пах /с — 1), (8) 02 — Я = (аче ф 1й/з/5+ 0(1), гпах (и/21).
Таким образом, левая ветвь выбирается примерно в ф - 1.618 раз чаще, чем правая (вполне понятный и предсказуемый результат, поскольку после каждого сравнения оставшийся интервал делится на две части; левая часть при этом приблизительно в ф раз бюльше правой). В итоге суммарное среднее время работы программы Е составляет около для успешного поиска плюс (9 — Зф)и = 4.15и — для неудачного.
Это меньше, чем в случае использования программы С, хотя наихудшее время работы (около 8.6 !ЕЙ) несколько больше. 18 18 1б ЕЗА 18 18 17 18 Е4В АО 81 Е2В ЯЯ 88 Еб Еб Яб ЕЗВ 87 28 1282 Е4А ЗМР ЕА1ЕРЕЕ РЕС1 1,З РЕС2 1,3 13ММ Е2В ЛМР ЕА1ЕРЕЕ 1МС1 1,2 РЕСЗ 1,2 РЕС2 1,3 СМРА КЕ?,1 11 ЕЗВ ЗЕ ЯРССЕЗБ ЛЗМ2 Е4В ЗМР ЕА11РВЕ РЕС1 1,2 РЕСЗ 1,2 32ММ Е2А ЗМР ЕА11.0ЕЕ -' ((18 + 4ф) й + 31 — 26ф) и = (7 050 18 Ж + 1.08) и Интерполяцнонный поиск.
Забудем ненадолго о компьютерах и посмотрим, как с задачей поиска справляется человек. Очень часто хороший алгоритм можно создать, проанализировав собственные действия в реальной жизни. Представьте, что вы ищете слово в словаре. Вероятно, вы не станете открывать словарь посередине и идти к странице, расположенной на 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 25 40 49 12 27 49 09 07 12 48 49 41 15 48 45 22 59 25 25 55 ЗЗ 20 48 36 Сортировка 500 подобных чисел при помощи технологий тех времен является просто феноменальной! (См.
Р. Е. Кпп1Ь, Яе!ссСе6 Рарегв оп Соглрисег Бс1епсе (СашЬг1пбе Нппп Ргезэ, 1996), СЛарьег 1Ц поиска вполне применима в мире компьютеров; о таких алгоритмах мы поговорим в разделе 6.3. Но и после этого первого шага ваши действия ничуть не похожи на то, что происходит при реализации какого-либо из рассмотренных алгоритмов.
Если вы заметите, что искомое слово находится ближе к концу группы слов на нужную букву, вы просто пропустите изрядное количество страниц (или начнете поиск от следующей буквы к предыдущей). Вот в чем состоит основное отличие ваших действий от действий, выполняемых в алгоритмах, для которых понятия "немного болыпе" и "существенно болыпе" одинаковы. Эти рассуждения приводят нас к алгоритму, который может быть назван иншерполлционным иопскоаи если мы знаеъц что К находится между К~ и К„, гледуюшую проверку мы будем делать примерно на расстоянии (К вЂ” К~)/(ʄ— К~) от 1 (в предположении, что ключи представляют собой числовые значения, близкие к арифметической прогрессии).
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный поиск. В то время как один шаг бинарного поиска уменьшает количество проверяемых записей от и до -и, один шаг интерполяционного поиска 1 уменыпает это количество до ~/т~ (если ключи распределены в таблице случайным образом). В результате интерполяционный поиск требует в среднем 1818% шагов для уменьшения диапазона проверки от Х до 2 (см. упр. 22). Однако имитационные вычислительные эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика), Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями 1818% и 18Х становится значительной только при больших Х (скажем, при Ж = 2гв = 65536).
Интерполяция наиболее успешно применяется на ранних стадиях поиска в большом внешнем файле; после того как диапазон поиска существенно уменьшится, следует перейти к бинарному поиску. (В связи с этим заметим, что поиск в словаре представляет собой внешний поиск, о котором мы поговорим немного позже.) Представляется совершенно естественной сортировка числовых значений, однако отношение порядка для букв или слов не столь очевидно. Тем не менее уже в наиболее древних алфавитах имелись последовательности букв, которые служили для их сравнения.
Например, во многих библейских псалмах содержатся стихи, следующие друг за другом в строгом алфавитном порядке: первый стих начинается с альфы, второй — с беты и т. д., что облегчает запоминание. Часто стандартная последовательность букв использовалась семитами и греками для обозначения чисел", например сг, д и Т означали 1, 2 и 3 соответственно. Алфавитный порядок с.лов, который представляется сейчас естественным даже школьнику, был гораздо более поздним изобретением и потребовал немалой работы. Отдельные списки, датируемые примерно 300 г.
до н. э., которые были найдены на островах Эгейского моря, содержат имена членов некоторых религиозных общин, упорядоченные только по первой букве (представляя, таким образом, результат одного прохола поразрядной сортировки слева направо). Некоторые греческие папирусы, датируемые 134-135 г. н. э., содержат списки налогоплательщиков, упорядоченных по первым двум буквам. Аполлоний Софист*в (Аро!1опшв Борьбе!а) использовал алфавитный порядок по первым двум буквам (а иногда н по последующим) в своем словаре поэзии Гомера (1 в. н.
э.). Известны примеры более совершенного упорядочения, например Н!рросгабс С!ивлев Галена*"в (ок. 200 г.), но это было крайне редким явлением. По первым буквам были упорядочены слова и в Ввушо!о8!агиш Св. Исидора (80 !в!г)огиз)вввв (ок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
