Meine Explode-Funktion optimieren

[TheMiller]

Hallo,

ich habe selbst eine Explode-Funktion geschrieben, bei der der Separator beliebig lang sein darf.
Nur ich weiß nicht, ob die so das non-plus-ultra ist, ob man sie so lassen kann, oder unbedingt überarbeiten muss.

Die aus der CodeLib kenne ich, aber ich brauche (wollte) meine eigene haben. Bitte um Tipps / Kritik. Danke!

Delphi-Quellcode:

function TForm1.Explode(p, Separator: PChar): String;
var
  i, j, seplen, strlen: Integer;
  sl,sl2:TStringList;
begin
  sl:=TStringList.Create;
  sl2:=TStringList.Create;
  strlen:=Length(Edit1.Text)-1;
  SepLen:=Length(Separator)-1;
  sl2.Add(IntToStr(0));
  for i:=0 to strlen do
  begin
    if (p[i] = separator[0]) and (p[i+seplen] = separator[seplen]) then
    begin
      sl.add(IntToStr(i));
      sl2.add(IntToStr(i+seplen+1));
    end;
  end;

  for i:=0 to sl.Count-1 do
  begin
    for j:=StrToInt(sl2.Strings[i]) to StrToInt(sl.Strings[i])-1 do
    begin
      result:=result+p[j];
    end;
    result:=result+' ';
  end;

  for i:=strtoint(sl2.Strings[sl2.Count-1]) to strlen do
  begin
    result:=result+p[i];
  end;
  sl.Free;
  sl2.Free;

  result:=result;
end;

Danke nochmals!

[MStoll]

Hallo,

ich fasse mal grad ein paar Punkte zusammen, die mir aufgefallen sind:

1.

Delphi-Quellcode:

if (p[i] = separator[0]) and (p[i+seplen] = separator[seplen]) then

Du scheinst hier nur den Anfang und das Ende des Separators zu überprüfen.
Was passiert denn, wenn man "das wandern ist des müllers lust" an Hand von "des" "explodet"?
Du solltest deine PChars vll besser in Strings verwandeln und dann mittels Copy auf das Vorkommen des ganzen Separators prüfen.

2. Result := Result sollte überflüssig sein

3. Ist das überhaupt ne explode-Fkt? Normalerweise gibt die doch ein Array zurück, oder verwechsel ich da was?

Gruß
Michael

[TheMiller]

Ja, eigentlich ich das schon eine Explode-Funktion. Hatte nur Probleme damit, den ganzen Separator zu prüfen. Und da diese für mich ist und meine Separatoren immer so aussehen [...irgendwassinnvolles...], habe ich nur Anfang und Ende geprüft. Das Array bae ich zum Schluss ein.

Achso, wenn der Code so ok ist, dann kann ich ihn ja so lassen. Wenn er allerdings speicherfressend etc ist, überarbeite ich ihn gerne.

Ich würde aber gerne wissen, wie ich einen ganzen Separator prüfen kann.

[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.

[SubData]

Wäre es nicht sinnvoll die StringListe durch ein DynArray zu ersetzen?


Edit:

Delphi-Quellcode:

function Explode(const Separator, Str: String; const Limit: Integer = 0): TStringDynArray;
var 
  SepLen: Integer; 
  F, P: PChar; 
  ALen, Index: Integer; 
begin 
  SetLength(Result, 0); 
  if (Str = '') or (Limit < 0) then Exit; 
  if Separator = '' then 
  begin 
    SetLength(Result, 1); 
    Result[0] := Str; 
    Exit; 
  end; 
  SepLen := Length(Separator); 
  ALen := Limit; 
  SetLength(Result, ALen); 
  Index := 0; 
  P := PChar(Str); 
  while P^ <> #0 do 
  begin 
    F := P; 
    P := AnsiStrPos(P, PChar(Separator)); 
    if (P = nil) or ((Limit > 0) and (Index = Limit - 1)) then P := StrEnd(F); 
    if Index >= ALen then 
    begin 
      Inc(ALen, 5); 
      SetLength(Result, ALen); 
    end; 
    SetString(Result[Index], F, P - F); 
    Inc(Index); 
    if P^ <> #0 then Inc(P, SepLen); 
  end; 
  if Index < ALen then SetLength(Result, Index);
end;

[alzaimar]

@SubData: Natürlich ist es marginal performanter, und Ich bezweifle, das das irgendetwas Messbares bringt.

[edit]Wie ich sehe, arbeitest Du einfach mit Pos. Das ist wesentlich langsamer als mein Ansatz.[/edit]

[SubData]

Die Funktion is nich von mir...
Und ja, da magst du gut recht haben...

[marabu]

Hi folks,

für Minimalisten reicht manchmal schon das hier:

Delphi-Quellcode:

procedure Explode(const s, delimiter: String; items: TStrings);
begin
  items.CommaText := StringReplace(AnsiQuotedStr(s, '"'), delimiter, '","', [rfReplaceAll]);
end;

Freundliche Grüße vom marabu

[TheMiller]

Hallo,

@SubData: Die Funktion ist wohl aus der CodeLib. Wie ich im ersten Post gesagt habe, kenne ich sie, brauche aber meine eigene.

Kann ich also davon ausgehen, dass es auch eine recht gebräuchliche Funktion ist (von der Performance etc). 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.

[MStoll]

@DJ-SPM: Deine explode-Fkt ist angenehm schnell (< 1 Sek für die angehängte Datei), hab ich grad mal getestet, im Gegensatz zu der aus der CodeLib (siehe unten)

[Off]
@SubData: Die Funktion aus der CodeLib braucht bei mir (2 Gigahertz) >4 Min um die angehängte Datei an Hand von #10 zu splitten. Ist das normal?
[/Off]

[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).