Методы оптимизации поиска

Индексно-последовательный поиск

Пример программы

function BSearch (item: DataArray; count:integer;

key:DataItem):integer;

var

low, high, mid: integer;

found:boolean;

begin

low:=1; high:=count;

found:=false; { не найден }

while (low<=high) and (not found) do

begin

mid:=(low+high) div 2;

if key<item[mid] then high:=mid-1

else if key>item[mid] then low:=mid+1

else found:=true; { найден }

end;

if found then BSearch:=mid

else BSearch:=0; { не найден }

end; { конец поиска }

При индексно-последовательномпоиске организуется две таблицы:

· таблица данных со своими ключами (упорядоченная по возрастанию)

· таблица индексов, которая тоже состоит из ключей данных,
но эти ключи взяты из основной таблицы через определен­ный интервал (рис. 5.3).

Сначала производится последовательный поиск в табли­це индексов по заданному аргументу поиска. Затем проходим ключ, который оказался меньше заданного и устанавливаем нижнюю границу поиска в основной таб­лице - low, а затем - верхнюю – hil на которой (kind > key).

Например, key = 101.

Поиск идет не по всей таблице, а от low до hi.

рис. 26 – индексно-последовательный поиск

Эффективность индексно-последовательного по­иска

Если считать равновероятным появление всех случаев, то эффективность поиска можно рассчитать следующим образом:

Например, m = n/р, где т- размер индекса; р - размер шага, тогда

Q = (n+1)/2 + (р+1)/2 = (n/р+1)/2 + (р+1)/2 = n/2р+р/2+1

Продифференцируем Q по р и приравняем производную к нулю:

dQ/dp=(d/dp) (n/2p+p/2+]) = -n/2р² + 1/2 = 0

Следовательно р² = n; Р_опт =

Подставив р_опт в выражение для Q, получим следую­щее количество сравнений:

Порядок эффективности индексно-последовательного поиска О ()

Существует некоторая вероятно­сть поиска того или иного элемента в таблице. Пусть в таблице данный элемент существует. Тогда вся таблица по­иска может быть представлена как система с дискретными состояниями, а вероятность нахождения искомого эле­мента - p(i),т.еi - го состояния системы.

Количество сравнений при поиске в таблице, представ­ленной как дискретная система, представляет собой матема­тическое ожидание значения дискретной случайной величи­ны, которая определяется вероятностями состояний и номерами со­стояний системы.

Z=Q=1p(l)+2p(2)+3p(3) +... +nр(n)

Желательно, чтобы р(1)≥р(2)≥р(3) ≥...≥р(п) – это минимизирует количество сравнений и увели­чивает эффективность.

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