Задача поиска. Пусть заданы
линейные списки: список элементов
В=<К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, причем такого
элемента может и не быть в списке.
Без использования стоппера
программа может быть реализована
следующим образом:
С использованием стоппера
программу можно записать в виде:
Для упорядоченных линейных
списков существуют более
эффективные алгоритмы поиска, хотя
и для таких списков применим
последовательный поиск. Бинарный
поиск состоит в том, что ключ V
сравнивается со средним элементом
списка. Если эти значения окажутся
равными, то искомый элемент найден,
в противном случае поиск
продолжается в одной из половин
списка.
Нахождение элемента бинарным
поиском осуществляется очень
быстро. Max бинарного поиска равен
log2(N), и при одинаковой частоте
использования каждого элемента Avg
бинарного поиска равен log2(N).
Недостаток бинарного поиска
заключается в необходимости
последовательного хранения списка,
что усложняет операции добавления
и исключения элементов .
Пусть, например, во входном потоке
задано 101 число, К1,К2,...,К100, V -
элементы списка и ключ. Известно,
что список упорядочен по
возрастанию, и элемент V в списке
имеется. Составим программу для
ввода данных и осуществления
бинарного поиска ключа V в списке
К1,К2,...,К100.
Этот способ удобен при индексном
хранении списка. Предполагается,
что исходный упорядоченный список 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
Эта функция ищет элемент с
индексом 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".
Рекурсивная функция search
реализует алгоритм выбора i-того
наибольшего значения. Для ее вызова
можно использовать следующую
программу
Используя метод математической
индукции, можно доказать, что для
функции 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 сравнений, т.е.
выдвинутое предположение доказано.
|