wyszukiwanie ciągu w pliku binarnym - optymalizacja

0

Napisałem sobie wyszukiwanie ciągu w pliku binarnym. Ciąg mam w TMemoryStream, plik w TFileStream, ale procedurę napisałem po prostu dla TStreamów. Ciekaw jestem, czy można jakoś zoptymalizować szybkość. Z góry dziękuję za porady. Oto procedura:

procedure TForm3.FindInStream
     (const Start:Integer;
      const SeekStream, AStream:TStream; out Result:TIntArray;
      Progressbar:TProgressBar;
      ALabel:TLabel;
      First:Boolean=False);
var
 i:integer;
 Identical:Boolean;
 Temp,seek:Byte;

begin
 Stop:=False;   //global

 if ProgressBar<>nil then
 begin
    ProgressBar.Min:=Start;
    ProgressBar.Max:= AStream.Size-SeekStream.Size;
    ProgressBar.Position:=0;
 end;

 SetLength(Result,0);
 ResultIndex:=-1;

 for i:=Start to AStream.Size-SeekStream.Size-1 do
 begin

   if ((i and 2047)=0) then
   begin
     if (ProgressBar<>nil) then Progressbar.Position:=i;
     if (ALabel<>nil) then  ALabel.Caption:=IntToStr(i);
     Application.ProcessMessages;
   end;

   AStream.Position:=i;

   Identical:=True;

   SeekStream.Position:=0;
   repeat
     AStream.ReadBuffer(Temp,1);
     SeekStream.ReadBuffer(Seek,1);
     if Seek<>Temp then
        begin
          Identical:=False;
          Break;
        end;
   until SeekStream.Position=SeekStream.Size;


   if Identical then
   begin
     Inc(ResultIndex);
     if ResultIndex>High(Result) then SetLength(Result, Length(Result)+100);
     Result[ResultIndex]:=i;
     if First then Break;
   end;

   if Stop then Break;
 end;

 if (ProgressBar<>nil) then ProgressBar.Position:=i;
 if (ALabel<>nil) then ALabel.Caption:=IntToStr(i);

 SetLength(Result,Succ(ResultIndex));
end;
0

Najprościej, zastosować algorytm wyszukiwania wzorca KMP (popatrz np. na www.algorytm.org ). Twój algorytm (naiwny) ma pesymistyczną złożoność O(n*m) (gdzie n,m to długość obu strumieni), a KMP działa w złożoności O(n+m).

0

Dzieki, o taki link mi chodziło. Niestety mojej knigi o algorytmach nie mam pod ręka. Wkrótce wpisze i zobaczę, czy jest różnica :-)

1 użytkowników online, w tym zalogowanych: 0, gości: 1