случаях можно было использовать более быструю целочисленную арифметику. - Прим. перев.)

Хотя задача сортировки привлекала большое внимание еще на заре компьютерной эры, алгоритмы поиска оставались в забвении достаточно долгое время. Малая внутренняя память и наличие только устройств последовательного доступа (наподобие лент) для хранения больших файлов делали поиск либо тривиальным, либо невозможным.

Развитие и удешевление памяти с произвольным доступом уже в 50-х годах привело к пониманию того, что проблема поиска важна и интересна сама по себе. После многих лет жалоб на ограниченность пространства программисты столкнулись с таким изобилием, которое попросту не могли переварить и эффективно использовать.

Первые обзоры по проблеме поиска опубликованы А. И. Думи (А. I. Dumey), Computers 8z Automation 5,12 (December, 1956), 6-9; В. В. Петерсоном (W. W. Peterson), IBM J. Research к Development 1 (1957), 130-146; Э. Д. Бутом (A. D. Booth), Information and Control 1 (1958), 159-164; A. Ш. Дугласом (A. S. Douglas), Сотр. J. 2 (1959), 1-9. Более подробный обзор, посвященный проблемам сортировки, был сделан несколько позже Кеннетом Ю. Айверсоном (Kenneth Е. Iverson), А Programming Language (New York: Wiley, 1962), 133-158, и Вернером Букхольцем (Werner Buchholz), IBM Systems J. 2 (1963), 86-111.

В начале 60-х годов было разработано несколько новых процедур поиска, основанных на древовидных структурах (с ними мы встретимся немного позже). Исследования алгоритмов поиска ведутся и в настоящее время.

6.1. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

"Начать с начала и продолжать, пока не будет найден искомый ключ; затем остановиться." Эта последовательная процедура представляет собой очевидный путь поиска и может служить отличной отправной точкой для рассмотрения множества алгоритмов поиска, поскольку они основаны на последовательной процедуре. Мы увидим, что за простотой последовательного поиска скрывается ряд очень интересных, несмотря на их простоту, идей.

Вот более точная формулировка алгоритма.

Алгоритм S {Последовательный поиск (Sequential search)). Дана таблица записей i?2,..., Rn с ключами Ki,K2,..., Kjv соответственно. Алгоритм предназначен для поиска записи с заданным ключом К. Предполагается, что N > 1.

51. [Инициализация.] Установить г <- 1.

52. [Сравнение.] Если К = Ki, алгоритм заканчивается успешно.

53. [Продвижение.] Увеличить г на 1.

54. [Конец файла?] Если i < N, перейти к шагу S2. В противном случае алгоритм заканчивается неудачно.

Обратите внимание на то, что этот алгоритм может завершиться успешно (искомый ключ найден) и неудачно (искомый ключ отсутствует). Данное утверждение справедливо для большинства алгоритмов, рассматриваемых в этой главе.

MIX-программа пишется очень просто.

\Нет

SI. Инициализация

->S2. Сравнение

S3. Продвижение

S4. КонегЛ файла? J

Успешное завершение

Рис. 1. Последовательный поиск.

Неудачное завершение

Программа S (Последовательный поиск). Предположим, что Ki хранится по адресу KEY + г, а оставшаяся часть записи (Ri) - по адресу INFO + i. Программа использует гА = К, гИ = i - N.

По адресу SUCCESS находится команда LDA INF0+N,1, которая помешает необходимую информацию в гА.

Анализ этой программы несложен. Очевидно, что время выполнения алгоритма S зависит от двух факторов:

С - количество сравнений ключей;

5 = 1 при успешном окончании поиска, О - при неудачном.

Программа S требует для работы 5С - 25 -Ь 3 единиц времени. Если при поиске успешно найден К = Ki, получим С = г, 5 = 1; таким образом, полное время составляет (5г -I- 1)и. С другой стороны, если поиск неудачен, мы получим С = N, 5 = О и общее время работы программы - {5N + 3)и. Если все ключи поступают на вход программы с одинаковой вероятностью, то среднее значение С в случае успешного поиска равно

l + 2 + ---+iV N + 1

N 2

При этом значение среднеквадратичного отклонения, естественно, достаточно велико и составляет около 0.289Л (см. упр. 1).

Данный алгоритм, несомненно, знаком всем программистам, но лишь некоторые из них знают, что этот способ - не самая лучшая реализация последовательного поиска! Небольшое изменение - и алгоритм выполняется существенно быстрее (если записей не слишком мало).

Алгоритм Q {Быстрый последовательный поиск). Перед вами тот же алгоритм, что и алгоритм S, однако в нем имеется дополнительное предположение о наличии фиктивной записи Rn+i в конце файла. Q1. [Инициализация.] Установить i +- 1 и Kn+i +- К.

Q2. [Сравнение.] Если К = Ki, перейти к шагу Q4.

Q3. [Продвижение.] Увеличить г на 1 и перейти к шагу Q2.

Q4. [Конец файла?] Если i < N, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно (г = Л + 1).

Программа Q {Быстрый последовательный поиск), г А = К, гП = i - N.

START

01 START LDA К

02 STA KEY+N+1

03 ENTl -N

04 INCl 1

05 CMPA KEY+N,1

06 JNE *-2

07 JINP SUCCESS

08 FAILURE EQU *

1 QI. Инициализация.

1 Kn+1 K.

1 i-iO.

С +1 - S 0.3. Продвижение.

C + l-S 0.2. Сравнение.

C+l-S Переход к Q3, если К, ф К.

1 QA. Конец файла?

1 - 5 Выход при отсутствии в таблице.

Используя те же значения С и 5, что и в программе S, получим, что значение времени работы равно (4С - 45 + 10)и; таким образом, мы получаем вьшгрыш по сравнению с предыдущим алгоритмом в случае С > 6 для успешного поиска и N > 8 - для неудачного.

При переходе от алгоритма S к алгоритму Q использован важный ускоряющий принцип - при нескольких проверках во внутреннем цикле следует постараться свести их к одной.

Вот еще один способ сделать програ.мму Q еще быстрее.

Программа Q {Быстрый последовательный поиск), г А = К, rll = i - N.

Внутренний цикл дублирован, что позволяет избежать выполнения половины инструкций "г <- г -I-1", тем самым снижая затраты времени до

3.5С - 3.5S + 10 +

{С - S) mod 2

единиц времени. При работе с большими таблицами это сохраняет до 30% нашего времени. Такой способ ускорения применим ко многим существующим программам на языках высокого уровня [см., например, D. Е. Knuth, Computing Surveys 6 (1974), 266-269].

Можно воспользоваться другим улучшенным алгоритмом, если ключи расположены в порядке возрастания: