Suche effizienter machen

[alzaimar]

Das kann man noch einkürzen:

Delphi-Quellcode:

Procedure TForm1.HighlightText;
Var
  ii,i2 : Integer;
  sLwcLine : String;

  Procedure _HighlightWord (Const aWord : String; aColor : TColor);
  Var
    p : Integer;

  Begin
    If aWord='' Then Exit;
    p := Pos (aWord, sLwcLine);
    If p>0 Then Begin
      mmoLines.SelStart := p + i2 - 1;
      mmoLines.SelLength := Length(aWord);
      mmoLines.SelAttributes.Color := aColor ;
      mmoLInes.SelAttributes.Style := [fsBold];
      mmoLines.SelLength := 0;
   End;
  End;

Begin
  if (text<>'') OR (text2<>'') OR (text3<>'') then begin
    i2 := 0; // Variable i2 muss initialisiert werden !
    text := LowerCase(text);
    text2 := LowerCase(text2);
    text3 := LowerCase(text3);
    mmoLines.Lines.BeginUpdate;
    Try
      for ii := 0 to FSelect.Count-1 do begin
        sLwcLine := LowerCase(FSelect[ii]);
        If sLwcLine<>'' Then Begin
          _HighLightWord (text, c);
          _HighLightWord (text2, c2);
          _HighLightWord (text3, c3);
        End;
        i2 := i2 + Length(FSelect.Strings[ii]) + 2;
      End;
    Finally
      mmoLines.Lines.EndUpdate;
    End
  End;
End;

Das 'highlighten' habe ich in eine lokale Prozedure ausgelagert, das Begin/Endupdate in Resourcenschutzblöcke gepackt, das LowerCase(FSelect[ii]) herausgezogen und die Variable 'i2' initialisiert (wieso heißt 'i2' eigentlich 'i2' und nicht z.B. 'iLineIndex'?).

Jetzt ist es etwas übersichtlicher.

@jfHeins: Bei deiner Lösung ist der große Pferdefuß die Generierung des 'Textes'. Ich vermute, Du meinst 'MyRichEdit.Lines.Text'. Das ist Speicher- und Zeitverschwendung, denn der 'Text' wird aus den Zeilen durch Stringkonkatenation gebildet. Ich denke, der Code ist schon ganz ok, die POS-Funktion könnte man noch durch eine schnellere Variante ersetzen (z.B. eine von FastCode oder FastStrings). Wenn man den Textpuffer direkt ansprechen könnte, wäre deine Variante aber sicherlich viel performanter.

[guidok]

Hier ist meine Variante:

Delphi-Quellcode:

var SuchPos: Integer;
begin
  if OpenDialog.Execute then
  begin
    if Length(edSuchwort.Text) > 0 then
    begin
      RichEdit.Lines.LoadFromFile(OpenDialog.FileName);
      SuchPos := 0;
      repeat
        SuchPos := RichEdit.FindText(edSuchwort.Text,SuchPos,Length(RichEdit.Lines.Text),[stWholeWord]);
        if SuchPos > -1 then
        begin
          RichEdit.SelStart := SuchPos;
          RichEdit.SelLength := Length(edSuchwort.Text);
          RichEdit.SelAttributes.Color := clRed;
          SuchPos := SuchPos + Length(edSuchwort.Text);
        end;
      until SuchPos = -1;
    end;
  end;
end;

Ich habe keinen Vergleich, wie schnell sie ist, aber sie funktioniert, wenn auch nur mit einem Suchwort. Für weitere Wörter muss man halt erweitern. Ein paar Kleinigkeiten könnte man auch noch optimieren, z.B. SuchLaenge := Length(edSuchwort.Text); im Voraus zuweisen.

EDIT

Der Aufruf von Length scheint viel Zeit zu benötigen. Ich habe das jetzt noch einmal so probiert und der Geschwindigkeitsunterschied ist immens.

Delphi-Quellcode:

var SuchPos, SuchLaenge, RichEditLaenge: Integer;
    STime, ETime: Integer;
begin
  if OpenDialog.Execute then
  begin
    SuchLaenge := Length(edSuchwort.Text);
    if SuchLaenge > 0 then
    begin
      RichEdit.Lines.LoadFromFile(OpenDialog.FileName);
      RichEditLaenge := Length(RichEdit.Lines.Text);

      STime := GetTickCount();

      SuchPos := 0;
      repeat
        SuchPos := RichEdit.FindText(edSuchwort.Text,SuchPos,RichEditLaenge,[stWholeWord]);
        if SuchPos > -1 then
        begin
          RichEdit.SelStart := SuchPos;
          RichEdit.SelLength := SuchLaenge;
          RichEdit.SelAttributes.Color := clRed;
          SuchPos := SuchPos + SuchLaenge;
        end;
      until SuchPos = -1;

      ETime := GetTickCount();
      lbZeit.Caption := IntToStr(ETime - STime);
      lbZeit.Visible := True;

    end;
  end;
end;

[p80286]

Hallo zusammen,

Warum ersetzt Ihr pos/posex/findtext nicht durch
Search_BMH_Unrolled oder einen anderen Boyer_Moore-Abkömling? Die sind wirklich schnell!

Der Lösungsvorschlag aus #13 (Hashmap) scheint mir vor allem interessant, wenn mehrere Worte gesucht werden sollen.

Gruß
K-H

P.S. ich hab einmal Pos und Search_BMH_Unrolled gegeneinander laufen lassen und das Laufzeitverhältnis (50MB Text) war ungefähr 5:1

[alzaimar]

Zitat von alzaimar:

...die POS-Funktion könnte man noch durch eine schnellere Variante ersetzen (z.B. eine von FastCode oder FastStrings).

Zitat von p80286:

Warum ersetzt Ihr pos/posex/findtext nicht durch...

*trommel* Auch das Kleingedruckte lesen

Boyer-Moore ist nicht automatisch schneller, denn es muss zunächst der Suchtext analysiert werden, das erzeugt einen gewissen Overhead. Man müsste für jeden Suchtext eine eigene BM-Engine erzeugen, dann wäre das schneller. Allerdings dürften hier andere Kandidaten (QuickSearch, HorSpool) noch besser sein. In der (FastStrings-Unit ist ein vereinfachter BM (QS, denke ich) implementiert.

Boyer-Moore eignet sich zudem erst für längere Suchtexte, der Overhead ist einfach zu groß.