Szybkie wyszukiwanie

Mam posortowaną tablicę która zawiera około 200 000 stringów, aktualnie przeszukuję ja w sposób liniowy (każdy string sprawdzam z wzorcem posem) co nie jest zbyt szybkie. Jeżeli ktoś zna coś szybszego to proszę o odpowiedź

Hmm może napisz kod tego sprawdzenia... takie wyszukiwanie powinno być "niby" najszybsze...

Hmm może napisz kod tego sprawdzenia... takie wyszukiwanie powinno być "niby" najszybsze...

OK
[code]for i:=0 to BCD.CDCount-1 do
if pos(Edit1.Text,BCD.CD[i].CDName)<>0 then AddItem(BCD.CD[i].CDName);[/code]

hm, nie wiem czy to ważne, ale czy przypadkiem nie interesuje cie żeby znajdował string bez względu na wielkość liter ???
i nie wydaje mi sie by można było szybciej...nie mam pomysła :(

hm, nie wiem czy to ważne, ale czy przypadkiem nie interesuje cie żeby znajdował string bez względu na wielkość liter ???
i nie wydaje mi sie by można było szybciej...nie mam pomysła :(

Z wielkością liter poradzę sobie. <font color="white">na pewno </span>można szybciej, np. korzystając z wyszukiwania przez haszowanie... (może ma ktoś <font color="white">pożądny</span> przykład?)

Skoro tablica jest posortowana, to istnieje znacznie szybszy algorytm przeszukiwania (nie wiem jak sie oficjalnie nazywa) <font color="darkblue">(dopisane - dzieki Dryobatesowi wiem, ze nazywa sie to przeszukiwanie binarne i ze nie ma lepszego algorytmu w tej sytuacji)</span>. Sprawdzasz element w srodku tablicy. Jesli szukany element jest mniejszy, to wyrzucasz gorna polowke tablicy i sprawdzasz element posrodku dolnej polowki itd.

Przyklad:

zrobilem posortowana tablice skladajaca sie z 10 000 losowych 6-literowych elementow.

Kod 1 (twoja metoda) wyglada u mnie tak:

   for j:=1 to szukan do   //szukan= liczba szukan do testowania, robilem na 10 000
   begin
     szukany:=tablica[Random(size)];  //szukam losowego elementu tablicy
     for i:=0 to Pred(size) do    //bez Pos
        if szukany=tablica[i] then Break;
   end;

Kod 2 (moja metoda) wyglada tak:

   for j:=1 to szukan do
   begin
     szukany:=tablica[Random(size)]; //szukam losowego elementu tablicy
     top:=size;
     bottom:=0;
     repeat
       i:=bottom+((top-bottom) div 2);
       if szukany=tablica[i] then Break;
       if szukany<tablica[i] then
         top:=i
          else
         bottom:=i;
     until false;
   end;

Wyniki kilku prob (Athlon 2000+ (1.67 GHx)) mowia same za siebie:

created
Kod 1: wykonanie 10000 razy zajelo: 1103.11729563394 ms
Kod 2: wykonanie 10000 razy zajelo: 8.1175121419063 ms
created
Kod 1: wykonanie 10000 razy zajelo: 1379.87314030135 ms
Kod 2: wykonanie 10000 razy zajelo: 7.04754375206905 ms
created
Kod 1: wykonanie 10000 razy zajelo: 1791.76124339825 ms
Kod 2: wykonanie 10000 razy zajelo: 7.2908707670947 ms
created
Kod 1: wykonanie 10000 razy zajelo: 1172.72949494978 ms
Kod 2: wykonanie 10000 razy zajelo: 6.94082627820016 ms
created
Kod 1: wykonanie 10000 razy zajelo: 1463.11584293535 ms
Kod 2: wykonanie 10000 razy zajelo: 7.14308662134433 ms
created
Kod 1: wykonanie 10000 razy zajelo: 1209.75598854044 ms
Kod 2: wykonanie 10000 razy zajelo: 7.54453429136943 ms

Metoda PQ jest oczywiście OK, jeśli chodzi na pewno o wyszukiwanie ciągu znaków, który jest równy elementowi tablicy (ewnetualnie el. tablicy zaczyna się od niego) . Co jednak z takim ciągiem, którego element tablicy zawiera?
np. gdy szukamy 'MA' w stringu 'ALA MA KOTA' [???]

Berl ??
Mamy posortowane

A Ola ma kota
I Ela ma kota
Znów Ala ma kota

Znajdzie mi wyraz Ala? Jeśli zaczniemy od elementu 2 - środek, to 'Ala' <'I Ela'...

Po prostu w tym miejscu, gdzie jest porównanie

szukany=tablica[i] 

i nierówność szukany<tablica[i]

 wstawiasz warunek sprawdzający, czy ten element tablicy zawiera stringa szukany. Oczywiście wtedy to wszystko będzie wolniej działało. I będzie wyszukiwało tylko pierwszy z pasujących elementów, nawet jeśli będzie ich kilka.

//Dopisane
Tiger27 : Cholera, masz rację, nie da się ukryć...

Dzięki PQ za poświęcenie, ale tej metody nie będę mógł zastosować ponieważ (co zapomniałem powiedzieć) tablica składa się z stringów o różnej długości (co zasugerował Tiger27). Zacząłem kombinować z drzewami. I w tym kierunku chyba będę podążał. Oczywiście wszelkie nowe pomysły mile widziane.