ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА Постановка задачи. Имеется N элементов-записей в исходном файле, каждая из которых сопровождается ключом поиска K[1] ... K[N] и неко- торой информационной частью, которую мы можем не рассматривать без потери общности. Требуется найти позицию ключа, имеющего заданное значение X. Запросы на поиск поступают последовательно и в некоторых случаях известны вероятности поступления каждого из них P[1] ... P[N]. В зависимости от количества элементов файла N, диапазона и равномерности распределения значений ключей K[i], вероятностей зап- росов на поиск конкретных значений Х наиболее подходящим может ока- заться один из известных методов и структур данных, которые будут описаны ниже. 6. Последовательный поиск Название этой группы методов произошло от использования последо- вательного списка в качестве структуры данных для хранения ключей. Список называют упорядоченным, если он упорядочен по значениям клю- чей, в противном случае он не называется упорядоченным, хотя некото- рый порядок ему можно придать за счет размещения в начале списка элементов, которые ищутся наиболее часто, то есть в порядке убывания вероятностей запросов P[1] ... P[N]. 6.1. Последовательный поиск в неупорядоченном файле Алгоритм поиска имеет вид: for i=1 to N ┌────────────────────────────────────────────┐ │if(X=K[i]) Конец: поиск удачен. │ └────────────────────────────────────────────┘ Конец: поиск неудачен. Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. Среднее время удачного поиска можно значительно сократить, если вероятности появления запросов на поиск различных ключей сильно от- личаются друг о другаи и ключи располагать в порядке убывания веро- ятностей. Алгоритм в этом случае не изменяется, но должен быть пред- варительный этап упорядочения списка. Также предполагается, что но- вые ключи при неудачном поиске не вставляются в список. 6.2. Последовательный поиск по связанному списку. Вероятности появления запросов на поиск часто не известны зара- нее. В этом случае можно использовать эмпирический алгоритм, дающий на практике хорошие результаты: каждый раз при удачном поиске най- денный ключ переставляется в начало списка. Естественно такие перес- тановки удобно делать на связанном списке. Каждому ключу K[i] соот- ветствует поле связи L[i], указывающее на следующий логически за ним ключ. На первый элемент указывает поле связи L[0]. ┌────┬────┐ ┌────┬────┐ ┌────┬────┐ │K[1]│L[1]├──> ... ─>┤K[i]│L[i]├─>─ ... ──>┤K[N]│L[N]├─> =0 └─┬──┴────┘ └────┴────┘ └────┴────┘ ┌┴───┐ │L[0]│ └────┘ Алгоритм имеет следующий вид. m=0; lm=L[m]; while (lm ╪ 0) do ┌────────────────────────────────────────────┐ │ ┌──────────────────────────────┐ │ │ │ Поиск удачен.Перестановка │ │ │if(X=K[lm])│ ключа K[lm] в начало списка │ │ │ ├──────────────────────────────┤ │ │ │L[0]=lm; │ │ │ │L[m]=L[lm]; │ │ │ │Конец алгоритма. │ │ │ └──────────────────────────────┘ │ │ m=lm; lm=L[m]; │ └────────────────────────────────────────────┘ Конец: поиск неудачен. Этот алгоритм легко модифицируется и для случая, когда после не- удачного поиска ключ Х должен быть вставлен первым в список. Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 6.3. Последовательный поиск в упорядоченном файле Если расположить ключи в возрастающем порядке, то время неудачно- го поиска можно существенно сократить. В простейшем алгоритме поиска в упорядоченном файле поиск прекращается, если при последовательном просмотре величмна Х становится больше или равной очередному ключу K[i]. В среднем при этом сокращается время неудачного поиска до N/2, среднее время удачного поиска остается по-прежнему равным N/2. Алгоритм имеет вид: ┌───── for i=1 to N ──────────────┐ │if(X══════════════════>╡ │if(X=K[i]) Конец: поиск удачен. │ │Конец: поиск неудачен │ └─────────────────────────────────┘ Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма и не зависящая для данного алгоритмаот результата поиска: удачен-неудачен. 6.4. Бинарный поиск в упорядоченном файле. Алгоритм предполагает деление упорядоченного списка ключей попо- лам до тех пор, пока в результате очередного деления число элементов в отрезке файла не уменьшится до одного. В этом случае уже можно сказать, был поиск удачным или нет. Алгоритм имеет вид: l=1; u=N; ┌──────────── while(u>=l) ───────┐ │i=│(l+u)/2│; │ │ └ ┘ │ │if(X══════╡ │if(X>K[i]] l=i+1; ══════>══════╡ │if(X=K[i]] Конец: поиск удачен.│ └────────────────────────────────┘ Конец: поиск неудачен. Время работы алгоритма t примерно оценивается формулой: t=a*lgN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. Лучших результатов не может дать ни один метод, основанный на срав- нении ключей, появляющихся с равной вероятностью.Однако, метод пред- назначен только для поиска, как и все методы, основанные на структу- ре исходного файла в виде последовательного списка. При включении новых ключей очевидны большие затраты по пересылке элементов. 6.5. Однородный бинарный поиск Эта модификация бинарного поиска требует сохранения таблицы значений величин D[1] ... D[max] max= │lgN│+2. Эти величины отражают возможное └ ┘ изменение текущего индекса i на каждом шаге поиска i=i(+-)d, где d - один из элементов массива D. При этом может достигаться экономия времени за счет более эффективной программы. Схема алгоритма имеет вид. ┌────────────────────────────────────────────────────────────────┐ │ j-1 j │ │Сформировать массив D, D[j]=│(N + 2 )/2 │ ,j=1,2,..., │lgN│+2│ │ └ ┘ └ ┘ │ └────────────────────────────────────────────────────────────────┘ i=D[1]; j=2; ╔════════════════════════════════════<══════╗ ║ ┌────────────────────────────────┐║ if(X════╪╣ └────────────────────────────────┘║ ┌────────────────────────────────┐║ if(X>K[i]] │if(D[j]=0) Конец:поиск неудачен.│║ │else i=i+D[j];j=j+1; ══════>════╪╝ └────────────────────────────────┘ if(X=K[i]] Конец: поиск удачен. Время работы алгоритма t примерно оценивается формулой: t=a*lgN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 6.6. Интерполяционный поиск Алгоритм интерполяционного поиска предполагает, что исходный файл упорядочен по величинам ключей поиска. Идея алгоритма состоит в том, что делается предположение о равномерном распределении величин в некотором их диапазоне от u до l. Поэтому, зная величину Х ключа поиска, можно предсказать более точное положение искомой записи, чем просто в середине некоторого отрезка файла. Формула нахождения положения следующего элемента для сравнения следует из деления длины отрезка u-l пропорционально величинам разностей ключей K[u]-K[l] и X-K[l]. Интерполяционный поик ассимптотически предпочтительнее бинарного, если только соблюдается гипотеза о равномерном распределении величин ключей. Алгоритм имеет вид: l=1; u=N; while(u>=l) ┌────────────────────────────────────┐ │ i=l+│(u-l)*(X-K[l])/(K[u]-K[l])│ │ │ └ ┘ │ │if(X══════════╡ │if(X>K[i]] l=i+1; ══════>══════════╡ │if(X=K[i]] Конец: поиск удачен. │ └────────────────────────────────────┘ Конец: поиск неудачен Время работы алгоритма t примерно оценивается формулой: t=a*lgN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен.