Wyszukiwanie na listach

Wyszukiwanie danych w dużej tablicy może sprawić problem. Liniowe przeszukiwanie jest niezbyt wydajne, a szukania binarnego nie ma jak użyć (no chyba że posortuje się tablicę quicksortem tak żeby nie zgubić informacji o położeniu danych w tablicy i żeby odtworzyć potem tą tablicę). Jednym ze sposobów szybkiego wyszukania może być wyszukiwanie na listach. Pierwszy krok to O(n), drugi natomiast zależy od ilości znalezionych elementów cząstkowych. Pomysł jest taki :
a) do dwóch list wpisujemy położenie pierwszej i ostatniej szukanej litery, tablicę przeszukujemy liniowo ( stąd te O(n) )
b) bierzemy obydwie listy (A i B) i porównujemy odległości pomiedzy położeniami w nich zapisanymi. Jeśli (A.poz - B.poz) < length(szukany) to przesuwamy wskaźnik B na następny element. Jeśli (A.poz - B.poz) > length(szukany) to przesuwamy A na następny element.
c) jeśli długość się zgadza to dopiero wtedy porównujemy ciąg bajtów z tabeli z szukanym ciągiem
d) jeśli dojdziemy z A lub z B do końca listy to znaczy, że szukanego ciągu bajtów nie ma w tablicy

Do wyszukiwania będzie potrzebna lista z głową (żeby za każdym razem mieć dostęp do ostatniego elementu, przyspieszy to dodawanie elementów do listy). Z potrzebnych funkcji należy wymienić : dodawanie elementu do listy oraz kasowanie listy. Poniżej przedstawione są potrzebne funkcje i procedury.

Program był napisany we Free Pascalu.

type
  TWskaznik = ^TElement ;
  TElement = record
                      adres    : LONGINT ;
                      nastepny : TWskaznik ;
                    end ;
var
    Wskazniki : array [ 0 .. 255, 0 .. 1 ] OF INTEGER ;  { bajty wskazujace na jakiejs miejsce }
    IloscWskaznikow : INTEGER ; { ilosc zapamietanych wskaznikow }

{* wyzeruj wskazniki, dla pewnosci *}
PROCEDURE ustaw_wskazniki ;
VAR 
  a : BYTE ;
BEGIN
  FOR a := 0 TO 255 DO
     BEGIN
        TabAdresow[a] := NIL ;
        TabHead[a] := NIL ;
     END ;
  FOR a := 0 TO 255 DO
    BEGIN
      Wskazniki[a,0] := -1 ;
      Wskazniki[a,1] := -1 ;
    END ;
END ;

{ dodawanie do listy, oznaczony koniec listy zeby bylo szybciej }
PROCEDURE add_addres( VAR poczatek, koniec : TWskaznik ; element : TWskaznik ) ;
BEGIN
  IF ( poczatek = NIL ) THEN { lista pusta }
    BEGIN
      Poczatek := element ;
      Koniec := element ;
    END
  ELSE { dodaj na koniec }
    BEGIN
      Koniec^.nastepny := element ;
      Koniec := element ;
    END ;
END ;

{* dodaj adres poczatkowego bajtu do listy i ustaw znacznik glowy na nastepny element *}
PROCEDURE dodaj_adres( znak, nr : byte ; adres : LONGINT ) ;
VAR 
  tmp : TWskaznik ;
BEGIN
  new ( tmp ) ;
  tmp^.adres := adres ;
  tmp^.nastepny := NIL ;
  add_addres( TabAdresow[nr], TabHead[nr], tmp ) ;
END ;

{ usuwanie zmiennych dynamicznych }
PROCEDURE kasuj_adres ;
VAR 
  tmp : TWskaznik ;
  a : BYTE ;
BEGIN
  FOR a := 0 TO 255 DO
    IF ( TabAdresow[a] <> NIL ) THEN
      WHILE ( TabAdresow[a] <> NIL ) DO
        BEGIN
          tmp := TabAdresow[a] ;
          TabAdresow[a] := TabAdresow[a]^.nastepny ;
          DISPOSE( tmp ) ;
        END ;
END ;


VAR
  Tmp1, Tmp2 : TWskaznik ;


(* Faster Searching Routine - czesc szukajaca *)
FOR b := wPliku TO IloscDanych DO
BEGIN
  { dane - tablica 
     w_pliku - polozenie poczatkowe szukania 
     ilosc_danych - ilosc danych w tablicy 
     zdanie2 - szukany ciag znakow
  }

  IF (Dane[b] = Zdanie2[1]) THEN
     dodaj_adres( ord(dane[b]), 0, b ) ;
  IF (Dane[b] = Zdanie2[length(zdanie2)]) THEN
     dodaj_adres( ord(Dane[b]), 1, b ) ;
END ;

{ polozenie pierwszej litery }
Tmp1 := TabAdresow[0] ;
a := wPliku ;
znaleziony := FALSE ;
WHILE ( tmp_1 <> NIL ) AND NOT( znaleziony ) AND NOT( keypressed ) DO
 BEGIN
   StartTu := Tmp1^.adres ; { adres pierwszej litery }
   { znajdz adres wiekszy od polozenia kursora }
   WHILE ( Tmp1 <> NIL ) AND ( StartTu < a ) DO
     BEGIN
       Tmp1 := Tmp1^.nastepny ;
       StartTu := Tmp1^.adres ;
     END ;

   { ostatnia litera szukanego zdania}
   Tmp2 := TabAdresow[1] ;
   IF Tmp2 <> NIL THEN KoniecTu := Tmp2^.adres 
   ELSE KoniecTu := 1000000 ; { adres ostatniej litery }

   { wyszukiwanie odpowiedniej roznicy pomiedzy polozeniami }
   WHILE ( Tmp2 <> NIL ) AND ( KoniecTu - StartTu + 1 < length( Zdanie2 ) ) DO
     BEGIN
       Tmp2 := Tmp2^.nastepny ;
       IF Tmp2 <> NIL THEN KoniecTu := Tmp2^.adres ;
     END ;

   { jesli zgadza sie, to sprawdzenie, czy wyraz pasuje do wzorca }
   IF ( KoniecTu - StartTu + 1 ) = length( Zdanie2 ) THEN
     BEGIN
       { skopiuj fragment z tablicy }
       wzorzec2 := '' ;
       FOR b := StartTu TO KoniecTu DO
         wzorzec2 := wzorzec2 + dane[b] ;
       IF wzorzec2 = zdanie2 THEN znaleziony := TRUE
       ELSE Tmp1 := Tmp1^.nastepny ; { nie pasuje }
     END
   ELSE Tmp1 := Tmp1^.nastepny ; { dlugosc sie nie zgadza }
 END ;

 kasuj_adres ; { zwolnij pamiec dynamiczna }

W 9 Mb tablicy przegląd trwa około 8 sekund.