Meine Explode-Funktion optimieren

[bernau]

Zitat:

Zitat von marabu

für Minimalisten reicht manchmal schon das hier:

Hi Marabu,


der Ansatz ist ja klasse. Den merke ich mir. Manchmal kann das Leben so einfach sein;-)

Aber! Vorher sollte geprüft werden, ob nicht zufällig das Komma im Text vorhanden ist. Da hätte man ja sonst eine falsche Teilung.

Gerd

[marabu]

Hallo Gerd,

hat denn meine Funktion bei dir einen Fehler produziert, wenn Kommata Textbestandteil sind?

Freundliche Grüße

[alzaimar]

Zitat:

Zitat von DJ-SPM

... Ein Nachteil ist leider, dass ich bis jetzt nur Anfang und Ende des Separators prüfe. Nur weiß ich nicht, wie ich den ganzen Separator prüfen kann. Daran bin ich immer und immer wieder gescheitert.

Gefällt Dir mein Ansatz nicht? :gruebel: Vergleiche ihn doch mal von der Performance her mit Deinem.

[bernau]

Zitat:

Zitat von marabu

hat denn meine Funktion bei dir einen Fehler produziert, wenn Kommata Textbestandteil sind?

Oh Mann, wird Zeit für'n Urlaub. Habe den Code schnell überflogen und natürlich nicht getestet. Beim Überfliegen habe ich den Elementaren Befehl "AnsiQuotedStr" übesehen. (Und anscheinend noch ein paar Kleinigkeiten) :-)

Dein Code bringt tatsächlich in keiner Situation einen Fehler. Perfekt.


Gerd

[SirThornberry]

mir fällt auf dass, das Ergebnis mit
String = String + Irgendwas
in einer Schleife zusammengesetzt wird. Es ist bedeutend schneller die größe des benötigten Speichers einmal zu setzen und den Speicher in einem rutsch zu kopieren als in vielen kleinen happen.

[alzaimar]

Hier mal eine Version (eben schnell geschrieben), die auf einem stark vereinfachten String-Matching-Algorithmus von Boyer-Moore basiert. Anstatt die gefundene Position zurückzuliefern, wird der Text extrahiert und in eine TStringlist geschrieben

Delphi-Quellcode:

Procedure AlzExplode(Const aText, aPattern: String; aItems: TStrings);
(*-----------------------------------------------------------------------------
 * Spaltet Textteile in aText, die durch aPattern getrennt sind auf, und 
 * füllt die einzelnen Texte in aItems.
 * <del>abc<del>xyz => ('abc','xyz')
 * Basiert auf der QuickSearch-Implementierung von 
 * Christian Charras und Thierry Lecroq, Université de Rouen, 
 * 76821 Mont-Saint-Aignan Cedex
 * Frankreich
 *)
Var
  i0, i, k, n, m: Cardinal;
  c: Char;
  Skip: Array[Char] Of Integer;

Begin
  aitems.clear;
  m := Length(aPattern);
  If m = 0 Then Exit;
// Sprungtabelle für nicht übereinstimmende Zeichen erstellen
  For c := Low(Char) To High(Char) Do
    Skip[c] := m + 1;

  For i := 1 To m Do
    Skip[aPattern[i]] := m - i + 1;

  i := 1;
  i0 := 1;
  n := Length(aText);
  k := n - m + 1;
  While i <= k Do Begin
    If (aPattern[1] = aText[i]) And (aPattern[m] = aText[i + m - 1]) Then // <<--- von DJ-SPM 
      If CompareMem(@aText[i], @aPattern[1], m) Then Begin
        aItems.Add(Copy(aText, i0, i - i0));
        inc(i, m);
        i0 := i;
        Continue;
      End;
    inc(i, Skip[aText[i + m]]);
  End;

  If i0 <= n Then
    aItems.Add(Copy(aText, i0, n - i0 + 1));

End;

Interessant ist, das hier nicht jedes Zeichen des Textes geprüft wird. Wenn man z.B. nach 'ABC' sucht, und der 3.Buchstabe ist kein 'C', kann man ja gleich um 3 Zeichen nach vorne gehen. Je länger der Suchtext ist, desto besser die Performance. Natürlich kann man ihn reinlegen (aPattern = 'aaaaaaaa').

Sicherlich gibt es noch bessere Algorithmen (Boyer-Moore, Raita, etc.) aber der o.g. ist schön kompakt und wirklich flott.

Die Abfrage nach dem ersten und letzten Buchstaben des Patterns, vor dem eigentlichen CompareMem, ist von DJ-SPM übernommen. Das scheint enorm viel zu bringen.

Diese Version ist nochmal 50% schneller als die von DJ-SPM. Allerdings hatte ich nicht seine Original-Version genommen (die ja nicht ganz korrekt ist), sondern noch ein 'CompareMem' eingebaut.

Wer hat Lust, hier weiter zu optimieren? Derzeit ist es ja schon eine echte Gemeinschaftsarbeit von DJ-SPM und den Franzosen (ok, ein wenig auch von mir). Das wäre dann die ultimative Explode-Funktion...

Kleiner Nachtrag: Die Version schlägt die CodeLib-Version um den Faktor 1,5-16. Die CodeLib-Version degeneriert zudem bei kurzen SuchStrings (Delimiter bzw. Pattern).