Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2), страница 9

Первые обзоры по проблеме поиска опубликованы А. И. Думи (А. 1, Ощпеу), Сотрпгегэ Хг АиготаВоп 5, 12 (ОесетЬег, 1956), 6-9; В. В. Петерсоном (Ж. %. РеФегэоп), 1ВМ,1. ВеэеагсЬ де Пе е)ортепг 1 (1957), 130-146; Э. Д. Бугом (А, О. ВоосЬ), 1л1огтаг1ол алд Сопего) 1 (1958), 159-164; А. Ш. Дугласом (А. Я. Ооп81аэ), Сотр. д. 2 (1959), 1-9. Более подробный обзор, посвященный проблемам сортировки, был сделан несколько позже Кеннетом К). Айверсоном (КеппесЬ Е.

Ь егэоп), А Ргойташт1л8 Ъвлйиайе (Кеи Ъогй: %!1еу, 1962), 133 — 158, и Вернером Букхольцем (Ъегпег ВцсЬЬоЬ), 1ВМ Яуегегпя д. 2 (1963), 86-111. В начале 60-х годов было разработано несколько новых процедур поиска, основанкых на древовидных структурах (с ними мы встретимся немного позже). Исследования алгоритмов поиска ведутся и в настоящее время. 6Д. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК "Нлчлть с нлчллл и продолжать, пока не будет найден искомый ключ; затем остановитьсн." Эта последовательная процедура представляет собой очевидный путь поиска и может служить отличной отправной точкой длн рассмотрения множества алгоритмов поиска, поскольку они основаны на последовательной процедуре.

Мы увидим, что за простотой последовательного поиска скрывается ряд очень интересных, несмотря на их простоту, идей. Вот более точная формулировка алгоритма. Алгоритм В (Последовательный поиск (Яедиепйа1 ееагсЬ)). Дана таблица записей Вы Вэ,..., Вм с ключами Км Кю..., Кл соответственно. Алгоритм предназначен для поиска записи с заданным ключом К. Предполагается, что Ю > 1. 81. (Инициализация.) Установиты +- 1. 82. (Сравнение.1 Если К = К,, алгоритм заканчиваетсл успешно.

83. [Продвижение.) Увеличиты на 1. В4. (Конец файла?1 Если 1 < Ь', перейти к шагу 82. В противном случае алгоритм заканчивается неудачно. $ Обратите внимание на то, что этот алгоритм может завершиться успешно (искомый ключ найден) и неудачно (искомый ключ отсутствует).

Данное утверждение справедливо для большинства алгоритмов, рассматриваемых в этой главе. йХХ-программа пишется очень просто. Неудаавае ааварвевве Усвеввее аавервеаве Рис, 1. Последовательный поиск. Программа Б (Последовательный поиск). Предположим, что К; хранится по адресу КЕТ + а, а оставшаяся часть записи (В;) — по адресу 1ИРО + й Программа использует УА ал К, гП = 1 — М. По адресу ЯОССЕЯЯ находится команда 1,ОА 1ИРО+И,1, которая помещает необходимую информацию в гА. $ Анализ этой программы несложен. Очевцдно, что время выполнения алгоритма Б зависит от двух факторов: С вЂ” количество сравнений ключей; Я = 1 при успешном окончании поиска, Π— при неудачном, (1) Программа 5 требует для работы 5С вЂ” 25+ 3 единиц времени.

Если при поиске успешно найден К = К,, получим С = а, о' = 1; таким образом, полное время составляет (ба + 1)и. С другой стороны, если поиск неудачен, мы получим С = Ф, Я = О и общее время работы программы — (5Ф + З)и. Если все ключи поступают на вход программы с одинаковой вероятностью, то среднее значение С в случае успешного поиска равно 1-~. 2.~- .~-.в1 й ч-1 (2) М 2 При этом значение среднеквадратичного отклонения, естественно, достаточно велико и составляет около 0.289Ф (см.

упр. 1), Данный алгоритм, несомненно, знаком всем программистам, но лишь некоторые из них знают, что этот способ — не самая лучшая реализация последовательного поиска! Небольшое изменение — и алгоритм выполняется существенно быстрее (если записей не слишком мало). Алгоритм ье (Быспарый последооатаельный поиск). Перед вами тот же алгоритм, что и алгоритм Б, однако в нем имеется дополнительное предположение о наличии фиктивной записи Вв+г в конце файла. ьс1.

(Инициализация,) Установить а +- 1 и Кл+~ <- К. 01 ВТАЕТ 1.ОА К 00 ЕИТ1 1-И 08 2И СИРА КЕТ+И,1 01 ЛЕ ЯОССЕВВ 00 1ИС1 1 06 31ИР 2В 07 ГА1ЫЖЕ ЕЦО а ~а 1+- 1. и Саеааа Выход, если К = Кь аа аае~~~ а~.~~в.й~ Выход при отсутствии в таблице. ь42. )Сравнение.) Если К = Ко перейти к шагу (44. Ссз. )Продвижение.) Увеличить 1 на 1 и перейти к шагу ()2. ь)4. )Конец файлау] Если 1 < Ф, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно (1 = Л + 1). Программа Ц (Быстрый последовательный поиск), гА вз К гП из 1 — Х Я~~. ° . Кл+~ +- К. 1+- О. ЯЮ Пел~~ аа.арв~.

Переход к С)З, если К; ф К. Я к~аыве Выход при отсутствии в таблице. $ используя те же значения С и о', что и в программе Б, получим, что значение времени работы равно (4С вЂ” 48+ 10)и; таким образом, мы получаем выигрыш по срввнеиню с предыдущим алгоритмом в случае С > 6 для успешного поиска и Х > 8 — для неудачного. При переходе от алгоритма Я к алгоритму () использован важный ускоряющий принцип — при нескольких проверках во внутреннем цикле следует постараться свести их к одной. Вот еще один способ сделать программу (4 еп1е быстрее, Программа Я' (Быстрый последовательный поиск). гА ив е К, гП ы 1 — /О.

1 1 1 ((С вЂ” Б + 2)/2) ((С - Б+ 2)/2) ((С вЂ” о *2)/2) ((С вЂ” 5+ 1)/2) ((С вЂ” Б+ 1)/2) (С вЂ” 5) пюо2 1 1 — Б Внутренний цикл дублирован, что позволяет избежать выполнения половины ин- струкций М +-1+ 1", тем самым снижая затраты времени до З,ЗС - З.ЗБ+ 16+ (С ~) шо" 2 2 единиц времени. При работе с большими таблицами это сохраняет до ЗОЯ нашего времени, Такой способ ускорения применим ко многим существующим программам иа языках высокого уровня )см., например, П. Е, Кппй, Сошрпг)лМ Яигтеуэ В (1974), 266-269). Можно воспользоваться другим улучшенным алгоритмом, если ключи расположены в порядке возрастания: 01 ЯТАВТ 02 ОУ ~Ц 05 00 07 08 РА11ЛВЕ 01 БТАВТ ОЗ 08 04 ЗН 00 ОО 07 00 00 10 4Н 11 РАПЛВЕ Ы)А К БТА КЕТ+М+1 ЕМТ1 -М 1МС1 1 СМРА КЕУ+М,1 ЯМЕ ь-2 21МР БУССЕБЯ ЕЦУ ЫА К БТА КЕТ+М+1 ЕМТ1 -1-М 1МС1 2 СИРА КЕУ+М,1 ЛЕ 4Р СМРА КЕТ+М+1,1 ЛМЕ ЗВ 1МС1 1 31МР ЯУССЕЯБ ЕВО 1 1 1 С+1 — Б С+1 — Б С+1 — Б 1 1 — Б Я~ Кл~ы е- К.

1 <- — 1. яьвц.д~~ ь ) Яг. Сд~ Переход к шагу ье4, если К = К;, Я2 ~й~ю ( у Переход к ивгу 123, если К ~ Кьеь Продвюкеиие А я4,е два Выход при отсутствии в таблице. 1 Алгоритм Т (Пооледооатпельпый поиск е упорядоченной 1паблице). Дана таблица записей Вы Вэ,, .., Вл, ключи которых расположены в порядке возрастания: К1 < Кз « Кл. Алгоритм предназначен для поиска записи с заданным ключом К Для удобства и ускорения работы алгоритма предполагается наличие фиктивной записи Вл+~ с ключом Кл+~ = оо > К.

Т1. (Инициализация.) Установить 1 +- 1. Т2. 1Сравнение.) Если К < Кп перейти к шагу Т4. ТЗ. (Продвижение.) Увеличить 1 на 1 и перейти к шагу Т2. Т4. (Равенство?] Если К = К,, алгоритм заканчивается успешно. В противном случае — неудачное завершение алгоритма. $ В предположении, что все входные аргументы-ключи равновероятны, алгоРитм по скорости работы в случае успешного поиска аналогичен алгоритму ь); при неудачном же поиске отсутствие нужного ключа определяется примерно вдвое быстрее. Во всех приведенных здесь алгоритмах использовалась запись с индексами для элементов таблиц (она более удобна для описания алгоритмов).

Однако все описанные алгоритмы применимы и к другим типам данных, например к таблицам со солгоппььи представлением данных, поскольку в них данные также расположены последовательно (см. упр. 2-4). Если мь1 можем размещать записи в таблице в любом порядке, значение Сл минимально при р1 >рэ» 'рм (4) т. е. когда наиболее часто используемые записи находятся в начале таблицы. Рассмотрим случаи Различных распределений вероятностей и выясним, какой выигрыш може г дать оптимальное расположение записей в таблице, указанное в (4).

В случае равновероятного появления ключей р~ = рэ = .. = Рк = 1/В формула (2) сводится к См = (Х + 1)/2, т. е. к ранее полученному нами резущьтату (2). Теперь предположим, что распределение вероятностей имеет вид 1 РМ = 2м, (б) 1 Рз 1 р1 = 2 1 рл-1 =: ~Ф-1 Согласно упр. 7 в данном случае См = 2 — 2' "'; при этом среднее количество сравнений, если записи расположены в надлежащем порядке, меньше доул. Еще одно, клиновидное, распределение вероятностей определяется как (б) Частота обращений. До сих пор мы предполагали, что все аргументы поиска равновероятны.

В общем случае это не так: вероятность запроса на поиск с ключом Вт Равна р;, пРичем р1+рэ+ +рм = 1. Время, требуемое для успешного завершения поиска, пропорционально количеству сравнений С, которое имеет среднее значение где с = — + —;-. Здесь мы не получим такого эффекта, как при распределении (5).

В случае клиновидного распределения Н+2 бл = с ~~'л ~! ( т + 1 !с) = —, а=1 3 Рг сл с/1, рэ = с/2, ..., Рн ле с/Я, (8) где с = 1/Нн. Оно получило известность благодаря работам Д. К. Зипфа (С. К. 21р(), который, исследуя естественные языки, обнаружил, что и-е по частоте употребления слово языка встречается с частотой, примерно обратно пропорциональной и (см.

ТЛе РзусЛо-В!о!ойу ог Ъаляиайе (Возгоп, Мазал НоийЬсои М161ш, 1935); Нитаи ВеЛэь4ог элг! сЛе Рг!лс!р!е ог" Хеэзг Е!!огг (ВеасИп8, Мазал АсИэоп-ттеэ1еу, 1949)]. Аналогичные распределения встречаются, например, в таблицах переписи населения, в которых районы расположены в порядке убывания численности населения. В случае подчинения ключей в таблице закону Знпфа находим Поиск в таком файле осуществляется примерно в 1 1и Н раз быстрее, чем в неупорядоченном файле [см. А. О. ВоосЬ, 1. ВгапсЬноой, апб 3. Р. С!нате, МесЛап!са! Незо!ибоп ог" улпйи!збс РгоЫехиз (Кебич Ъог)с: Асас)еппс Ргезз, 1958), 79), Другое близкое к реальному распределение — это распределение„соответствующее правилу ч80-20", которое часто наблюдается э коммерческих приложениях (свеч напРимеР, %. Р. Не1эш8, ИМ ЯУзсетз Х 2 (1963), 114-115).