Файл: Методы поиска данных: эволюция и сравнительный анализ. Примеры использования..pdf
Добавлен: 15.05.2023
Просмотров: 179
Скачиваний: 3
Для индексно-последовательного поиска в дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной. Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующей этому ключу. Элементы в индексной таблице, как элементы в основной таблице, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий 1/8 от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице.
Если размер основной таблицы — n, то размер индексной таблицы — ind_size = n/8.
Достоинство алгоритма – сокращается время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.
Примеры использования методов поиска данных
Проиллюстрируем процесс бинарного поиска. Число элементов массива n = 17, тогда [n/2] = 8. Поэтому первоначально выполняется сравнение key с x8 = 57. Так как key > x8, то зона поиска на следующем шаге ограничивается участком от 9-го элемента до 17-го. Этот участок состоит из девяти элементов и его серединой является элемент x13 = 107 ([(9 + 17)/2] = 13). Поскольку key > x13, то зона поиска ограничивается участком от 14-го до 17-го элемента. Его серединой является элемент x15. На этом процесс поиска завершен, так как x15 = key. Всего для завершения поиска потребовалось 3 итерации.
Отобразим на рис. 1 процесс поиска элемента key = 129, выделяя посредством подчеркивания на каждом шаге зоны поиска.
|
Итерация 0 |
5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 |
|
Итерация 1 |
5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 |
|
Итерация 2 |
5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 |
|
Итерация 3 |
5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 |
Рис. 1. Пример дихотомии
Каждое сравнение уменьшает число возможных кандидатов в два раза. Максимальное число шагов поиска будет в том случае, когда искомый элемент находится в начале или в конце массива. Для завершения поиска потребуется не более log2n + 1 итераций. Действительно, если число элементов в массиве равно n = 2m, то элемент будет найден через m шагов. В свою очередь, при заданном n имеем m = log2n. После анализа последнего элемента получаем общее число итераций log2n + 1. Поэтому вычислительная сложность бинарного поиска составляет O(log2n). Вычислительная сложность последовательного поиска равна O(n).
Однако приведенный алгоритм не позволяет в общем случае точно решить задачу поиска, когда файл или массив содержат повторяющиеся значения ключей. Рассмотрим, например, массив 5 7 11 18 26 32 44 57 81 90 94 97 107 129 129 147 179, в котором элемент (ключ) 129 содержится два раза. Тогда, если аргумент поиска равен 129, поиск по приведенному алгоритму завершится на элементе с номером 15, то есть будет найдено не первое, а второе значение ключа 129 (первое значение ключа расположено в позиции 14). В ряде случаев эта неточность принципиальна, впрочем, она легко устраняется.
Последовательный поиск предполагает последовательный просмотр всех записей множества, организованного как массив.
Пример: Найти в массиве элемент со значением, равным 3.
#include <stdio.h>
#include <stdlib.h>
int search(int *k, int n, int key) {
int index = -1;
for(int i=0; i<n; i++) {
if(k[i] == key) {
index = i;
break;
}
}
return(index);
}
int main() {
int i, k[8];
int point;
system("chcp 1251");
system("cls");
for(i=0;i<8;i++) {
printf("Введите k[%d]: ",i);
scanf("%d",&k[i]);
}
point = search(k,8,3);
if(point == -1)
printf("Элементов равных 3 в массиве нет!\n");
else
printf("Элемент с индексом %d равен 3", point);
getchar(); getchar();
return 0;
}
Метод транспозиции
Улучшением рассмотренного метода является метод транспозиции: каждый запрос к записи сопровождается сменой мест этой и предшествующий записи; в итоге наиболее часто используемые записи постепенно перемещаются в начало таблицы; и при последующем обращении к ней запись будет находиться почти сразу.
int search(int *k, int n, int key) {
int index = -1;
int temp;
for(int i=0; i<n;i++) {
if(k[i] == key) {
index = i;
if(index==0)
break;
temp = k[i];
k[i] = k[i-1];
k[i-1] = temp;
break;
}
}
return(index);
}
int main() {
int i, k[8];
int point;
system("chcp 1251");
system("cls");
for(i=0;i<8;i++) {
printf("Введите k[%d]: ",i);
scanf("%d",&k[i]);
}
for(i=0; i<6; i++) {
point = search(k,8,3);
if(point == -1)
printf("Элементов равных 3 в массиве нет!\n");
else
printf("Элемент с индексом %d равен 3", point);
}
getchar(); getchar();
return 0;
}
Результат выполнения
Метод перемещения в начало
Каждый запрос к записи сопровождается её перемещением в начало таблицы; в итоге в начале таблицы оказывается запись, используемая в последний раз.
int search(int *k, int n, int key) {
int index = -1;
int temp;
for(int i=0; i<n;i++) {
if(k[i] == key) {
index = i;
temp = k[i];
k[i] = k[0];
k[0] = temp;
break;
}
}
return(index);
}
Реализация индексно-последовательного поиска
#include <stdio.h>
#include <stdlib.h>
int main() {
int k[20]; // массив ключей
int r[20]; // массив записей
int i, j, ind_size;
int key;
int kindex[3]; // массив ключей индексной таблицы
int pindex[3]; // массив индексов индексной таблицы
system("chcp 1251");
system("cls");
// Инициализация ключевых полей упорядоченными значениями
k[0] = 8;
k[1] = 14;
k[2] = 26;
k[3] = 28;
k[4] = 38;
k[5] = 47;
k[6] = 56;
k[7] = 60;
k[8] = 64;
k[9] = 69;
k[10] = 70;
k[11] = 78;
k[12] = 80;
k[13] = 82;
k[14] = 84;
k[15] = 87;
k[16] = 90;
k[17] = 92;
k[18] = 98;
k[19] = 108;
// Ввод записей
for(i=0;i<20;i++) {
printf("%d. k[%d]= %d: r[%d]=",i,i,k[i],i);
scanf("%d",&r[i]);
}
// Формирование индексной таблицы
for(i=0, j=0;i<20;i=i+8) {
kindex[j] = k[i];
pindex[j] = i;
j++;
}
ind_size = j;
pindex[j] = 20;
// Поиск
printf("Введите key: ");
scanf("%d",&key);
for(j=0; j<ind_size; j++) {
if(key < kindex[j])
break;
}
if(j==0) i=0;
else i = pindex[j-1];
for(i; i<pindex[j];i++) {
if(k[i]==key)
printf("%d. key= %d. r[%d]=%d",i,k[i],i,r[i]);
}
getchar(); getchar();
return 0;
}
Результат выполнения
Реализация бинарного поиска
#include <stdio.h>
#include <stdlib.h>
int main() {
int k[20];
int r[20];
int key, i;
system("chcp 1251");
system("cls");
k[0] = 8;
k[1] = 14;
k[2] = 26;
k[3] = 28;
...
k[19] = 108;
for(i=0;i<20;i++) {
r[i] = i+1;
printf("%d. k[%d]= %d: r[%d]=%d\n",i,i,k[i],i,r[i]);
}
printf("Введите key: ");
scanf("%d",&key);
int low = 0;
int high = 19;
int search = -1;
while (low<=high) {
int mid=(low+high)/2;
if (key==k[mid]) {
search=mid;
break;
}
if (key<k[mid])
high=mid-1;
else
low=mid+1;
}
if(search==-1)
printf("Элемент не найден!\n");
else
printf("%d. key= %d. r[%d]=%d",search,k[search],search,r[search])
getchar(); getchar();
return 0;
}
Результат выполнения
Заключение
В результате выполнения работы сравним алгоритмы последовательного и бинарного поиска.