RichEdit.FindText beschleunigen

[marabu]

Nein, Laufzeit-Fehler treten bei mir nicht auf.

Ich habe mir den Code jetzt genauer angesehen. Die von mir verlinkte Funktion FindTextAll() enthält genau die Bremse, vor der ich dich warnen wollte. Hier die korrigierte Fassung:

Delphi-Quellcode:

function FindTextAll(re: TRichEdit; const sText: string;
    options: TSearchTypes): TIntegerDynArray;
var
  iStart, iFound, iLength: Integer;
begin
  SetLength(Result, 0);
  iStart := 0;
  iLength := Length(re.Text);  // re.Lines.Text war fatal
  while iStart < (iLength - Length(sText)) do
  begin
    iFound := re.FindText(sText, iStart, iLength - iStart, options);
    if iFound = -1 then Break;
    SetLength(Result, Succ(Length(Result)));
    Result[High(Result)] := iFound;
    iStart := iFound + Length(sText);
  end;
end;

Den Geschwindigkeitsvorteil ziehst du in deinem Code aus zwei fiesen Tricks: Du suchst immer nur nach dem ersten Treffer, weitere ignorierst du, und du verkleinerst den Suchbereich mit jedem Treffer. Wird ein Suchwort am Ende des Textes gefunden, dann beginnst du mit der Suche nach dem nächsten Suchwort direkt hinter dem vorigen Treffer. Dein Text enthält 34.630 Zeichen, insgesamt durchsucht werden bei dir 35.037 Zeichen. Bei etwa gleichmäßig im Text verteilten Suchwörtern müsstest du aber pro einfachem Treffer etwa 17.315 Zeichen untersuchen, bei 410 Durchläufen sind das etwa 7MB. Mein Code findet übrigens 483 Treffer.

Der Vergleich der beiden Lösungen hinkt ein wenig, meinst du nicht auch?

[Franzelchen]

Hallo Marabu!

Zitat:

Zitat von marabu

Du suchst immer nur nach dem ersten Treffer, weitere ignorierst du, und du verkleinerst den Suchbereich mit jedem Treffer. Wird ein Suchwort am Ende des Textes gefunden, dann beginnst du mit der Suche nach dem nächsten Suchwort direkt hinter dem vorigen Treffer.

Und genau so ist es ja auch gemeint.

Diese Prozedur ist trotz des beschriebenen Geschwindigkeitsvorteils für meinen Rechner der langsamste Teil im Gesamtprogramms. Deswegen frage ich ja nach einer Beschleunigungsmöglichkeit von RE.FindText .

Ich probiere mal Deinen Source aus und bedanke mich für deine bisherige Hilfe.

[marabu]

Hallo,

dass du nur die jeweils erste Fundstelle markieren willst, ist für mich unverständlich. Die sukzessive Einschränkung des Suchbereiches wird in der Informatik nur bei der Feststellung einer bestimmten Ordnung angewandt - diese Aufgabenstellung geht aber weder aus deiner Beschreibung noch aus den Daten hervor, aberseisdrum ...

Eine drastische Beschleunigung der Textsuche könntest du durch den Einsatz eines Directed Acyclic Word Graph (DAWG) erreichen. Dabei werden die Buchstaben der Suchbegriffe in einen Baum eingetragen und jedes Suchwort entspricht einem Pfad im Baum. Deine Suche geschieht dann eigentlich anders herum: Du prüfst deinen zu durchsuchenden Text anhand des Baums auf existierende Pfade.

Es gibt noch andere Ansätze für eine beschleunigte Suche, die alle effizienter sind als die Methode FindText, aber der DAWG ist leicht zu implementieren und hat einen sehr großen Kosten-Nutzen-Effekt.

Freundliche Grüße

[Franzelchen]

Hallo!

Zitat:

Zitat von marabu

Hallo,

Eine drastische Beschleunigung der Textsuche könntest du durch den Einsatz eines Directed Acyclic Word Graph (DAWG) erreichen. Dabei werden die Buchstaben der Suchbegriffe in einen Baum eingetragen und jedes Suchwort entspricht einem Pfad im Baum. Deine Suche geschieht dann eigentlich anders herum: Du prüfst deinen zu durchsuchenden Text anhand des Baums auf existierende Pfade.

Es gibt noch andere Ansätze für eine beschleunigte Suche, die alle effizienter sind als die Methode FindText, aber der DAWG ist leicht zu implementieren und hat einen sehr großen Kosten-Nutzen-Effekt.

Freundliche Grüße

Die Implementation fällt mir nicht ganz so einfach wie Marabu es schreibt.
Ich habe den RE.Text in ein Dawg geschrieben. Das geht sehr leicht.
Das Durchsuchen des RE.dawg mit den Einträgen der Listbox fällt mir schon wesentlich schwerer.
Es erscheinen Variant Fehler. In der Schleife die ich eingefügt habe um die Listbox abzuarbeiten sind offensichtlich auch noch Fehler.
An das Hauptproblem : die Markierung der Listbox Einträge im Dawg , traue ich mich gar nicht erst heran.

Hilfe!!