Форум: "Прочее";
Текущий архив: 2006.09.17;
Скачать: [xml.tar.bz2];
ВнизБыстрый поиск в упорядоченном массиве. Найти похожие ветки
← →
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
← →
TUser © (2006-08-24 19:40) [9]> Это както сильно сложно, учитывая, что массив содержит не числовые элементы
Какая разница. Если есть отношение порядка, то почти всегда можно использовать эту процедуру. Я использую бинарный поиск, но ведь мне не надо супер-быстро. Разок использовал хэши.
← →
SergP © (2006-08-24 20:15) [10]> Прошу прощения.. я не правильно выразился... меня интересует
> способ не проще, а быстрее.
> Допустим приведенный вами пример (аналогичный используется,
> кстати, в методе Find класса TStringList) найдет искомый
> элемент в массиве из 4294967296 элементов не более чем за
> 32 итерации. Вопрос в том, можно ли быстрее.
32 итерации - это не так уж и много. Тем более что зависимость количества итераций от размеров массива - логарифмическая. Думаю что важнее то что собой представляет итерация. А в бинарном поиске - она самая простейшая (т.е. будет выполняться за минимальное время)
← →
SergP © (2006-08-24 20:20) [11]> [3] TUser © (24.08.06 19:08)
> Есть еще интерполяционный поиск - примерно как бинарный,
> только не пополам делишь, а рассчитавыешь, где предположительно
> находится твой элемент. Примитивный случай - предполагаем
> равномерное распределение. Тогда,
>
> MiddleIndex:=(Value - A[MinIndex])/(A[MinIndex]-A[MaxIndex])
> *(MaxIndex-MinIndex)+MinIndex
>
> В других случаях можно предполагать другое распределение,
> например, квадратическое. Это ускоряет поиск, хотя асимптотически
> он, разумеется, остается логарифмическим.
ИМХО кол-во итераций уменьшается, но время затрачиваемое на одну итерацию увеличивается из-за усложнения вычислений. Так что этот метод особого выигрыша в скорости не даст. А в некоторых случаях будет тормознее обычного бинарного поиска.
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.09.17;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.092 c