Meine Explode-Funktion optimieren

[alzaimar]

Ich musste mal eine 20MB XNL-Datei schnell parsen, und da ist es ja ähnlich. Nach einigen Versuchen bin ich hier gelandet:

Delphi-Quellcode:

Procedure Explode (Const aMessage, aSeparator : String; aItems : TStringList);
Var
  i,n,i0,k : Integer;

Begin
  k := Length (aSeparator);
  n := Length (aMessage);
  i0 := 1;
  i := 1;
  While i<= n do Begin
    If aMessage[i] = aSeparator[1] Then    // Das ist trifft nicht sehr oft zu und wenn, ist es zu 99% ein Treffer
      If Copy (aMessage,i,k) = aSeparator Then Begin                           // Separator ist an der Position #i
        aItems.Add (Copy (aMessage,i0, i-i0);                    // String zwischen i0 und i in die Items kopieren
        inc (i,n);                                                             // i hinter den Separator plazieren
        i0 := i;                                                            // Hier fängt auch das nächste Wort an
        Continue; 
      End;
    inc(i); 
  End
End;

Ungetestet, sollte aber in etwa funktionieren. Das Laufzeitverhalten ist grauenvoll, nämlich O(n*k), aber in Deinem Anwendungsfall ist es fast O(n), weil eben das erste Zeichen des Separators fast nie im Text vorkommt. Ich habe bei meinem Frickel-XML-Parser ja ähnliche Voraussetzungen und da war diese Variante schnell genug.

Wenn man es richtig anstellen möchte, würde ich einen schnellen String-Pos-Algorithmus verwenden. Der bricht ja ab, sobald ein Suchstring (der Separator) gefunden wurde. Hier greift man ein, speichert das Wort in den Items und sucht weiter.

Ich würde das mit einem DEA versuchen. Der Knuth-Morris-Pratt(KMP)-Algorithmus verwendet einen solchen DEA und ist recht einfach. Den könnte man etwas aufbohren, und als Explode umfunktionieren. Aber auch Boyer-Moore wäre ein guter Ausgangspunkt, BM verwendet Lookuplisten anstelle eines DEA. BM lohnt sich aber erst, wenn dein Separator immer gleich und verhältnismäßig lang ist (>ein paar Zeichen).

Beide Algorithmen dürfte es zuhauf auch in Delphi irgendwo geben, vielleicht bei FastCode.