Быстрый поиск в упорядоченном массиве.

← →
vidiv © (2006-08-24 18:43) [0]

Есть упорядоченный массив Arr (т.е. Если даны два его элемента, можно сказать в каком порядке они могут встречаться в массиве). Есть элемент Element. Как максимально быстро провести поиск в массиве Arr элемента Element.
Самый простой способ - перебор до предпологаемого места.
Способ по сложнее, но в разы быстрее - это метод "деления пополам". Т.е. Element сравнивается с элементом массива, который находится в середине этого самого массива, затем аналогичная операция проделывается с той половинкой массива котором находится (или может находится) Element.
Есть способы проще?

← →
Чапаев © (2006-08-24 18:46) [1]

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

← →
vidiv © (2006-08-24 18:50) [2]

> есть прямой поиск (по хэшу)

можно в кратце описать принцип?

← →
TUser © (2006-08-24 19:08) [3]

Есть еще интерполяционный поиск - примерно как бинарный, только не пополам делишь, а рассчитавыешь, где предположительно находится твой элемент. Примитивный случай - предполагаем равномерное распределение. Тогда,

MiddleIndex:=(Value - A[MinIndex])/(A[MinIndex]-A[MaxIndex])*(MaxIndex-MinIndex)+MinIndex

В других случаях можно предполагать другое распределение, например, квадратическое. Это ускоряет поиск, хотя асимптотически он, разумеется, остается логарифмическим.

← →
Desdechado © (2006-08-24 19:09) [4]

ищешь "хэш-таблицы" в гугле

← →
Чапаев © (2006-08-24 19:10) [5]

Есть некоторая функция (хэш-функция) h(x)=n, n є [0;N]. Есть массив A[0..N] такой что A[n]=x. Поиск любого элемента выполняется за один шаг: нужно просто выбрать элемент массива A[h(x)].

Пример. Пусть h(x)=S(Ord(x[i]),i=1 to Length(x)) mod 100. h(x) є [0;99]. S -- сумма. x -- некоторая строка. Нужно добавить строку "Вася". h("Вася")=4718 mod 100=18. Васю заносим в восемнадцатый элемент массива, состоящего из 100 элементов. Нужно добавить строку "Пупкин". h("Пупкин")=6480 mod 100=80. Пупкина добавляем в восьмидесятый элемент. Теперь если нам нужно найти Васю, мы вычисляем хэш Васи и проверяем, действительно ли на восемнадцатой позиции находится Вася.

Вкратце принцип такой...

← →
SergP © (2006-08-24 19:14) [6]

> [0] vidiv © (24.08.06 18:43)
> Есть упорядоченный массив Arr (т.е. Если даны два его элемента,
> можно сказать в каком порядке они могут встречаться в массиве)
> . Есть элемент Element. Как максимально быстро провести
> поиск в массиве Arr элемента Element.
> Самый простой способ - перебор до предпологаемого места.
> Способ по сложнее, но в разы быстрее - это метод "деления
> пополам". Т.е. Element сравнивается с элементом массива,
> который находится в середине этого самого массива, затем
> аналогичная операция проделывается с той половинкой массива
> котором находится (или может находится) Element.
> Есть способы проще?

почему это метод деления пополам сложный? Он почти не сложнее метода перебора до нужного места...

Например я когда-то так делал (правда пришлось подправлять прямо здесь) поэтому возможны и ошибки...
function BinarySearch(var A:Array of integer; d:integer):integer; var iStart,iEnd,iMid:integer; begin if Length(A)>0 then begin iStart:=0; iEnd:=high(A); while iEnd-iStart>1 do begin iMid:=(iStart+iEnd) div 2; if d>=A[iMid] then iStart:=iMid else iEnd:=iMid; end; if d=A[iEnd] then result:=iEnd else if d=A[iStart] then result:=iStart else Result=-1; end else Result=-1; end;

← →
vidiv © (2006-08-24 19:34) [7]

> SergP © (24.08.06 19:14) [6]

Прошу прощения.. я не правильно выразился... меня интересует способ не проще, а быстрее.
Допустим приведенный вами пример (аналогичный используется, кстати, в методе Find класса TStringList) найдет искомый элемент в массиве из 4294967296 элементов не более чем за 32 итерации. Вопрос в том, можно ли быстрее.

> Чапаев © (24.08.06 19:10) [5]

Идея в принципе понятна... иначе говоря "проин
дексировать" массив :)

> TUser © (24.08.06 19:08) [3]

Это както сильно сложно, учитывая, что массив содержит не числовые элементы

← →
Дураг (2006-08-24 19:35) [8]

Поиск в строках, массивах, последовательностях
http://algolist.manual.ru/search/index.php

> Это както сильно сложно, учитывая, что массив содержит не числовые элементы

Какая разница. Если есть отношение порядка, то почти всегда можно использовать эту процедуру. Я использую бинарный поиск, но ведь мне не надо супер-быстро. Разок использовал хэши.

> Прошу прощения.. я не правильно выразился... меня интересует
> способ не проще, а быстрее.
> Допустим приведенный вами пример (аналогичный используется,
> кстати, в методе Find класса TStringList) найдет искомый
> элемент в массиве из 4294967296 элементов не более чем за
> 32 итерации. Вопрос в том, можно ли быстрее.

32 итерации - это не так уж и много. Тем более что зависимость количества итераций от размеров массива - логарифмическая. Думаю что важнее то что собой представляет итерация. А в бинарном поиске - она самая простейшая (т.е. будет выполняться за минимальное время)

> [3] TUser © (24.08.06 19:08)
> Есть еще интерполяционный поиск - примерно как бинарный,
> только не пополам делишь, а рассчитавыешь, где предположительно
> находится твой элемент. Примитивный случай - предполагаем
> равномерное распределение. Тогда,
>
> MiddleIndex:=(Value - A[MinIndex])/(A[MinIndex]-A[MaxIndex])
> *(MaxIndex-MinIndex)+MinIndex
>
> В других случаях можно предполагать другое распределение,
> например, квадратическое. Это ускоряет поиск, хотя асимптотически
> он, разумеется, остается логарифмическим.

ИМХО кол-во итераций уменьшается, но время затрачиваемое на одну итерацию увеличивается из-за усложнения вычислений. Так что этот метод особого выигрыша в скорости не даст. А в некоторых случаях будет тормознее обычного бинарного поиска.

Быстрый поиск в упорядоченном массиве. Найти похожие ветки