Задача поиска. Пусть заданы линейные списки: список элементов
В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это
целые числа). Требуется для каждого значения Vi из V найти множество всех
совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V
содержит один элемент, а в В имеется не более одного такого элемента.
Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А}
и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V
в В. Если Pi - относительная частота использования элемента Кi в В, а Si -
количество сравнений, необходимое для его поиска, то
n
Max{А} = max{ Si, i=1,n } ; Avg{А} = Pi Si .
i=1
Последовательный поиск предусматривает последовательный просмотр всех
элементов списка В в порядке их расположения, пока не найдется элемент равный V.
Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо
следить за тем, чтобы поиск не вышел за пределы списка, что достигается
использованием стоппера.
Очевидно, что Max последовательного поиска равен N. Если частота
использования каждого элемента списка одинакова, т.е. P=1/N, то Avg
последовательного поиска равно N/2. При различной частоте использования
элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало
списка.
Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V.
Составим программу для последовательного хранения элементов Кi и поиска среди
них элемента, равного V, причем такого элемента может и не быть в списке. Без
использования стоппера программа может быть реализована следующим образом:
/* последовательный поиск без стоппера */
#include
main()
{
int k[100],v,i;
for (i=0;i<100;i++)
scanf("%d",&k[i]);
scanf("%d",&v);
i=0;
while(k[i]!=v && i<100) i++;
if (k[i]==v) printf("%d %d",v,i);
else printf("%d не найден",v);
}
С использованием стоппера программу можно записать в виде:
/* последовательный поиск со стоппером */
#include
main()
{
int k[101],v,i;
for (i=0;i<100;i++)
scanf("%d",&k[i]); /* ввод данных */
scanf("%d",&v);
k[100]=v; /* стоппер */
i=0;
while(k[i]!=v) i++;
if (i<100) printf ("%d %d",v,i);
else printf ("%d не найден",v);
}
Для упорядоченных линейных списков существуют более эффективные алгоритмы
поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск
состоит в том, что ключ V сравнивается со средним элементом списка. Если эти
значения окажутся равными, то искомый элемент найден, в противном случае поиск
продолжается в одной из половин списка.
Нахождение элемента бинарным поиском осуществляется очень быстро. Max
бинарного поиска равен log2(N), и при одинаковой частоте использования каждого
элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска
заключается в необходимости последовательного хранения списка, что усложняет
операции добавления и исключения элементов .
Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V -
элементы списка и ключ. Известно, что список упорядочен по возрастанию, и
элемент V в списке имеется. Составим программу для ввода данных и осуществления
бинарного поиска ключа V в списке К1,К2,...,К100.
/* Бинарный поиск */
#include
main()
{
int k[100],v,i,j,m;
for (i=0;i<100;i++)
scanf("%d",&k[i]);
scanf("%d",&v);
i=0; j=100; m=50;
while (k[m]!=v)
{
if (k[m] < v) i+=m;
else j=m-i;
m=(i+j)/2;
}
printf("%d %d",v,m);
}
Этот способ удобен при индексном хранении списка. Предполагается, что
исходный упорядоченный список B длины N разбит на M подсписков B1,B2,...,Bm
длины N1,N2,...,Nm, таким образом, что B=B1,B2,..,Bm.
Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M,
последний элемент которого больше V, а потом применить последовательный поиск к
списку Bi.
Хранение списков Bi может быть связным или последовательным. Если длины всех
подсписков приблизительно равны и M= N, то Max М-блочного поиска равен 2 N. При
одинаковой частоте использования элементов Avg М-блочного поиска равен N.
Описанный алгоритм усложняется, если не известно, действительно ли в списке
имеется элемент, совпадающий с ключом V. При этом возможны случаи: либо такого
элемента в списке нет, либо их несколько.
Если вместо ключа V имеется упорядоченный список ключей, то последовательный
или М-блочный поиск может оказаться более удобным, чем бинарный, поскольку не
требуется повторной инициализации для каждого нового ключа из списка V.
Методы вычисления адреса. Пусть в каждом из М элементов массива Т содержится
элемент списка (например целое положительное число). Если имеется некоторая
функция H(V), вычисляющая однозначно по элементу V его адрес - целое
положительное число из интервала [0,M-1],то V можно хранить в массиве T с
номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит
за постоянное время не зависящее от M.
Массив T называется массивом хеширования, а функция H - функцией хеширования.
При конкретном применении хеширования обычно имеется определенная область
возможных значений элементов списка V и некоторая информация о них. На основе
этого выбирается размер массива хеширования M и строится функция хеширования.
Критерием для выбора M и H является возможность их эффективного использования.
Пусть нужно хранить линейный список из элементов K1,K2,..,Kn, таких, что при
Ki=Kj, mod(Ki,26)= mod(Kj,26). Для хранения списка выберем массив хеширования
T(26) с пространством адресов 0-25 и функцию хеширования H(V)= mod(V,26). Массив
T заполняется элементами T(H(Ki))=Ki и T(j)=0 если j (H(K1), H(K2),..,H(Kn)).
Поиск элемента V в массиве T с присваиванием Z его индекса если V содержится
в T, или -1, если V не содержится в T, осуществляется следующим образом
int t[26],v,z,i;
i=(int)fmod((double)v,26.0);
if(t[i]==v) z=i;
else z=-1;
Добавление нового элемента V в список с возвращением в Z индекса элемента,
где он будет храниться, реализуется фрагментом
z=(int)fmod((doule)v,26.0);
t[z]=v;
а исключение элемента V из списка присваиванием
t[(int)fmod((double)v,26)]=0;
Теперь рассмотрим более сложный случай, когда условие Ki=Kj H(Ki)=H(Kj)
не выполняется. Пусть V - множество возможных элементов списка (целые
положительные числа), в котором максимальное число элементов равно 6. Возьмем
M=8 и в качестве функции хеширования выберем функцию H(V)=Mod(V,8).
Предположим, что B=, причем H(K1)=5, H(K2)=3, H(K3)=6,
H(K4)=3, H(K5)=1, т.е. H(K2)=H(K4) хотя K2=K4. Такая ситуация называется
коллизией, и в этом случае при заполнении массива хеширования требуется метод
для ее разрешения. Обычно выбирается первая свободная ячейка за собственным
адресом. Для нашего случая массив T[8] может иметь вид
T=<0,K5,0,K2,K4,K1,K3,0> .
При наличии коллизий усложняются все алгоритмы работы с массивом
хеширования. Рассмотрим работу с массивом T[100], т.е. с пространством адресов
от 0 до 99. Пусть количество элементов N не более 99, тогда в T всегда будет
хотя бы один свободный элемент равный нулю. Для объявления массива используем
оператор
int static t[100];
Добавление в массив T нового элемента Z с занесением его адреса в I и числа
элементов в N выполняется так:
i=h(z);
while (t[i]!=0 && t[i]!=z)
if (i==99) i=0;
else i++;
if (t[i]!=z) t[i]=z, n++;
Поиск в массиве T элемента Z с присвоением I индекса Z, если Z имеется в T,
или I=-1, если такого элемента нет, реализуется следующим образом:
i=h(z);
while (t[i]!=0 && t[i]!=z)
if (i==99) i=0;
else i++;
if (t[i]==0) i=-1;
При наличии коллизий исключение элемента из списка путем пометки его как
пустого, т.е. t[i]=0, может привести к ошибке. Например, если из списка B
исключить элемент K2, то получим массив хеширования в виде
T=<0,K5,0,0,K4,K1,K3,0>, в котором невозможно найти элемент K4, поскольку
H(K4)=3, а T(3)=0. В таких случаях при исключении элемента из списка можно
записывать в массив хеширования некоторое значение непринадлежащее области
значений элементов списка и не равное нулю. При работе с таким массивом это
значение будет указывать на то, что нужно просматривать со средние ячейки.
Достоинство методов вычисления адреса состоит в том, что они самые быстрые,
а недостаток в том, что порядок элементов в массиве T не совпадает с их порядком
в списке, кроме того довольно сложно осуществить динамическое расширение
массива T.
Задача выбора. Задан линейный список целых, различных по значению чисел
B=, требуется найти элемент, имеющий i-тое наибольшее значение в
порядке убывания элементов. При i=1 задача эквивалентна поиску максимального
элемента, при i=2 поиску элемента с вторым наибольшим значением.
Поставленная задача может быть получена из задачи поиска j-того минимального
значения заменой i=n-j+1 и поиском i-того максимального значения. Особый интерес
представляет задача выбора при i=a/n, 0<a<1, в частности, задача выбора медианы
при a=1/2.
Все варианты задачи выбора легко решаются, если список B полностью
отсортирован, тогда просто нужно выбрать i-тый элемент. Однако в результате
полной сортировки списка B получается больше информации, чем требуется для
решения поставленной задачи.
Количество действий можно уменьшить применяя сортировку выбором только
частично до i-того элемента. Это можно сделать, напри мер при помощи функции
findi
/* выбор путем частичной сортировки */
int findi(int *s, int n, int i)
{
int c,j,k;
for (k=0; k<=i; k++)
for (j=k+1; j<=n; j++)
if (s[k] < s[j])
{ c=s[k];
s[k]=s[j];
s[j]=c;
}
return s[i];
}
Эта функция ищет элемент с индексом i, частично сортируя массив s, и
выполняет при этом (n*i) сравнений. Отсюда следует, что функция findi приемлима
для решения задачи при малом значении i, и малоэффективна при нахождении
медианы.
Для решения задачи выбора i-того наибольшего значения в списке B модифицируем
алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B' и
B", такие, что если Ki -B', то Ki>K1, и если Ki - B", то Ki<K1, и список B
реорганизуется в список B',K1,B". Если K1 элемент располагается в списке на
j-том месте и j=i, то искомый элемент найден. При j>i наибольшее значение
ищется в списке B'; при j<i будем искать (i-j) значение в подсписке B".
Алгоритм выбора на базе быстрой сортировки в общем эффективен, но для
улучшения алгоритма необходимо, чтобы разбиение списка на подсписки
осуществлялось почти пополам. Следующий алгоритм эффективно решает задачу выбора
i-того наибольшего элемента в списке B, деля его на подсписки примерно равной
величины.
1. Если N<21, то выбрать i-тый наибольший элемент списка B обычной
сортировкой.
2. Если N>21 разделим список на P=N/7 подсписков по 7 элементов в каждом,
кроме последнего в котором mod(N,7) элементов.
3. Определим список W из медиан полученных подсписков (четвертых наибольших
значений) и найдем в W его медиану M (рекурсивно при помощи данного алгоритма)
т.е. (P/2+1)-й наибольший элемент.
4. С помощью элемента M разобьем список B на два подсписка B' с j элементами
большими или равными M, и B" c N-j элементами меньшими M. При j>i повторим
процедуру поиска сначала, но только в подсписке B'. При j=i искомый элемент
найден, равен M и поиск прекращается. При j < i будем искать (i-j)-тый
наибольший элемент в списке B".
/* алгоритм выбора делением списка почти пополам */
int search (int *b, int n, int i)
{
int findi(int *, int, int);
int t, m, j, p, s, *w;
if (n<21) return findi(b, n, i); /* шаг 1 */
p=(int)(n/7);
w=calloc(p+1,sizeof(int)); /* шаги 2 и 3 */
for (t=0; t < p; t++)
w[t]=findi(b+7*t, 7, 3);
if (n%7!=0)
{ w[p]=findi(b+7*p,n%7,(n%7)/2);
p++;
}
m=search(w, p, p/2);
free (w);
for (j=0, t=0; t < n; t++) /* шаг 4 */
if (b[t]>=m) j++;
if (j>i)
{
for (p=0, t=0; p < n; t++)
if (b[t]>=m)
{ b[p]=b[t]; p++; }
m=search(b, j, i); /* поиск в B" */
}
if (j < i)
{
for (p=0, t=0; t < n; t++)
if (b[t] < m) b[p++]=b[t];
m=search(b, n-j, i-j); /* поиск в B" */
}
return m;
}
Рекурсивная функция search реализует алгоритм выбора i-того наибольшего
значения. Для ее вызова можно использовать следующую программу
#include
#include
main()
{
int search (int *b, int n, int i);
int *b;
int l, i, k, t;
scanf("%d%d",&l,&i);
printf
("\nВыбор %d максимального элемента из %d штук",i,l);
b=(int *)(calloc(100,sizeof(int)));
for (k=0; k<100; k++)
b[k]=k; /* заполнение массива */
for (k=1; k < l/4; k++)
{ t=b[k]; /* перемешивание */
b[k]=b[l-k]; /* массива */
b[l-k]=t;
}
k=search(b,l,i); /* выбор элемента */
printf ("\n выбран элемент равный %d\n\n",k);
return 0;
}
Используя метод математической индукции, можно доказать, что для функции
search требуется выполнить в самом неблагоприятном случае 28*N сравнений.
Действительно, если N<21, то выполнение функции findi потребует сравнений
порядка N*(N-1)/2, т.е. меньше чем 28*N. Предположим, что для любого T<N
количество сравнений при выполнении функции search не более 28*T и подсчитаем,
сколько сравнений потребуется функции search при произвольном значении N. Для
поиска медианы в каждом из подсписков функцией findi требуется не более
7*(7-1)/2=21 сравнений, а для формирования массива W в целом не более
21*(N/7)=3*N сравнений. По предположению индукции для поиска медианы в массиве
W длины N/7 требуется 28*(N/7)=4*N сравнений. После удаления из B части
элементов с помощью медианы в B' (или в B") останется не более N*5/7 элементов,
и для удаления ненужных элементов необходимо количество сравнений порядка N. Для
поиска в оставшейся части массива (в B' или B") по предположению индукции
требуется не более 28*(N*5/7)=20*N сравнений. Таким образом, всего потребуется
3*N+4*N+N+20*N=28*N сравнений, т.е. выдвинутое предположение доказано.
[ Назад | Оглавление | Вперед ]
|
