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