[Optimiert] Explode Prozedur - Reloaded (Ersatz für CodeLib)

[alzaimar]

Hi!
Ich hab mir mal die Mühe gemacht, und eine alternative Explode-Funktion implementiert, die wohl doch etwas schneller ist, als die hier in der Code-Library hinterlegte Version.

Ich möchte Euch bitten, den Code zu testen und auch zu optimieren. Wenn wir damit durch sind, sollte diese Version in die Code-Library übernommen werden, bzw die jetzige Version ersetzen.

Details über die Herleitung (na ja, Recherche und Kopieren :mrgreen: ) steht im Code.

[Edit] Unten genannte Tests sowie Zeitmessung eingearbeitet: Es ist ein komplettes Projekt mit Funktions- und Speed-Test. Bitte versucht, Teile davon zu optimieren (ASM, Pointer arithmetic etc.). [/edit]

History:
12.12. Version 1.1: Erste schwere Fehler ausgebaut: Strings am Ende wurden falsch bzw. gar nicht erkannt.
13.12. Version 1.2: Kleiner Fehler in der Prepare-Methode: (Hilfsvariable als Cardinal deklariert, bei Zuweisung <0 ignoriert), Facelifting auf Anregung von Elvis (Feld- und Variablennomenklatur). Ferner ist eine Test-Iterator-Basisklasse sowie ein Iterator für Char-Delimiter (z.B. für CSV) implementiert.
14.12 Version 1.3: Iterator für QS-Search implementier. Die Test-Routine wurde um Zeitmessungen für den Iterator sowie die Code-Library ergänzt.
23.12.07 Version 1.4: Beseitigt seltenen Bereichsüberlauf am Ende eines Strings.

Diese Version ist zwischen 4 und 1000x schneller als die Version aus der Code-Library.

[API]

Danke für den Code. Ist doch um einiges schneller als eine herkömmliche Explode Funktion.
Habe es getestet mit einigen einigen tausend Aufrufen der jeweiligen Funktion und mit Messen der Zeit.

[shmia]

Interessant!! :dp:
Gibt es auch einen Unittest, um die Funktionsfähigkeit zu weisen?
Gerade bei so einer komplexen Funktion sollte man diese Tests unbedingt ausführen
und bei jeder weiteren Optimierung erneut ausführen.

Delphi-Quellcode:

// ungetestet reingehackt
procedure TestTStringDivider;
var
   sd : TStringDivider;
   list : TStringList;
   s, delim : string;
begin
   sd := TStringDivider.Create;
   list := TStringList.Create;
   delim := 'abcd';
   // Test #1
   s := '';
   sd.Explode(s, delim, list);
   Assert(list.Count=0);
   // Test #2
   s := 'delphi'+delim+'Praxis';
   sd.Explode(s, delim, list);
   Assert(list.Count=2);
   Assert(list[0] = 'delphi');
   Assert(list[0] = 'Praxis');
   // Test #3
   s := 'delphi'+delim+'Praxis'+delim+delim+delim;
   sd.Explode(s, delim, list);
   Assert(list.Count=5);
   ...
end;

PS: Vielleicht sollte man den Boyer-Moore Algorithmus in eine eigene Klasse verlagern,
um so einen zusätzlichen Nutzen zu gewinnen.

[alzaimar]

Hallo!

Danke für das Feedback, Ich habe wirklich nur halbe Arbeit geleistet. Die Test-Unit ist natürlich klasse, auch eine standardisierte Zeitmessung sollte man in ein Testszenario aufnehmen.

Den Suchalgorithmus kann man natürlich auslagern, aber ich meine, man könnte einfach zu FastString greifen.

Ich arbeite gleich mal die beiden Vorschläge ein.

[Elvis]

Bug gefunden, Bug gefunden, Trallalla *drei-mal im Kreis hüpft* :mrgreen:

Ich habe mal die Unit etwas angepasst, da sie im Single Char modus gerne das letzte Zeichen geklaut hat.
Ich habe auch ctrl+shift+e benutzt um die etwas kurzen Name hoffentlich klarer zu machen.
Außerdem habe ich den Code mal in externe Iteratoren geworfen, für den Fall dass man die Ergebnisse a) nicht in einer Liste halten möchte und b) die VCL nicht referenzieren will.
Gibt ja leider keinen String Container in der Delphi RTL. (RTL <> VCL)
Und c) weil's so easy war :mrgreen:

• vars zu feldern
• Init code im Constructor
• und einfachimmer raushüpfen wenn man was gefunden hat

Die Iteratoren (oder .Net speak Enumeratoren) sind aber eher Copy'nPaste + Anpassung, also keineswegs auf die Verwendung als Iterator optimiert...
Den Fehler und die Verwendung der Iteratoren kann man hiermit sehen:

Delphi-Quellcode:

uses
  Classes,
  csExplode2,
  uExplodeEnumerators,
  csExplode;

type
  TOriginalStringDivider = csExplode.TStringDivider;
  TStringDivider         = csExplode2.TStringDivider;

procedure Original(const aPattern, aText : String);
var
  s  : string;
  sl : TStringList;
  sd : TOriginalStringDivider;
begin
  sl := TStringList.Create();
  sd := TOriginalStringDivider.Create();

  sd.Explode(aPattern, aText, sl);

  for s in  sl do
    Writeln(s);

  sd.Free();
  sl.Free();
end;

procedure UseSL(const aPattern, aText : String);
var
  s  : string;
  sl : TStringList;
begin
  sl := TStringList.Create();
  TStringDivider.Explode(aPattern, aText, sl);

  for s in  sl do
    Writeln(s);

  sl.Free();
end;

procedure UseEnum(const aPattern, aText : String);
var
  s : string;
begin
  for s in TStringDivider.Explode(aPattern, aText) do
    Writeln(s);
end;

procedure UseEnumDirectly(const aPattern, aText : String);
var
  enum : IExplodeEnumerator;
begin
  enum := TStringDivider.Explode(aPattern, aText) as IExplodeEnumerator;
  while enum.MoveNext() do
    Writeln(enum.Current);
end;

procedure RunAll(const aPattern, aText : String);
begin
  Original(aPattern, aText);
  Writeln('----------------------------');

  UseSL(aPattern, aText);
  Writeln('----------------------------');

  UseEnum(aPattern, aText);
  Writeln('----------------------------');

  UseEnumDirectly(aPattern, aText);
  Writeln('----------------------------');
end;

begin
  ReportMemoryLeaksOnShutdown := true;

  RunAll('abcxydefxyghixymmmxyx','y');
  RunAll('abcxydefxyghixymmmxyy','y');
end.

btw: Warum hast du hier Instanzmethoden gewählt obwohl du gar keinen State zwichen den Calls halten musst?
Klassenmethoden hätten ja auch gereicht, bzw. sogar statische methoden in Delphi2006, wodurch du dir den impliziten parameter auf die class reference sparst:

Delphi-Quellcode:

type
  TStringDivider = class
  private
    class procedure AddString(pStart, pEnd: PChar; aItems: TStrings); static;
    class procedure QSExplode(const aText, aPattern: String; aItems: TStrings); static;
  public
    class procedure Explode(const aText, aPattern: String; aItems: TStrings); overload; static;
    //class function Explode(const aText, aPattern: String) : IExplodeEnumerable; overload; static;
  end;

btw: Wer in den unteren Procs (UseEnum*) nach Free sucht, sucht vergebens, da ich mit Interfaces arbeite überlasse ich das dem Compiler und der Referenzzählung. ;)

[alzaimar]

Hi Elvis,

In der Test-Dpr dürften die Fehler behoben gewesen sein, nur in der isolierten csExplode.Pas-Unit waren sie es nicht. Ich schmeiss das Attachment mal raus.

Danke für das Bugfixing.

Zu deinen Anmerkungen:

Zitat:

Zitat von Elvis

Ich habe mal die Unit etwas angepasst, da sie im Single Char modus gerne das letzte Zeichen geklaut hat.

Hat sie auch im 'Multichar'-Modus :oops:. Durch den eingebauten Test wurde der Fehler sehr schnell ersichtlich. Leider ignoriert dein Fix leere Strings am Ende: Der Text '-1-2-3-' enhält 5 Teilstrings: <leer>, "1", "2", "3" und <leer>. Dein Fix erkennt nur die ersten 4.

Zitat:

Zitat von Elvis

Ich habe auch ctrl+shift+e benutzt um die etwas kurzen Name hoffentlich klarer zu machen.

Na ja, so wie i und j Zähler sind, sind bei mir p Pointer. Und wenn ich 'i' sage, muss ich auch 'p' sagen. Aber so ist es auch gut. Allerdings müsste man dann folgerichtig aus dem 'i' einen 'Counter' machen...

Zitat:

Zitat von Elvis

Außerdem habe ich den Code mal in externe Iteratoren geworfen, für den Fall dass man die Ergebnisse a) nicht in einer Liste halten möchte und b) die VCL nicht referenzieren will.

Äh... ok. Ich glaube, es wäre besser, die Explode-Methoden mit dynamischen String-Arrays zu überladen.

Zitat:

Zitat von Elvis

btw: Warum hast du hier Instanzmethoden gewählt obwohl du gar keinen State zwichen den Calls halten musst?
Klassenmethoden hätten ja auch gereicht, bzw. sogar statische methoden in Delphi2006, wodurch du dir den impliziten parameter auf die class reference sparst:

Das stimmt so nicht: Vor dem Suchen/Zerteilen wird aus dem Teiler-String (Eigenschaft 'Pattern') eine Sprungtabelle erzeugt. Wenn ich viele Zeilen bearbeiten will, setze ich einmalig die Eigenschaft 'Pattern': die Sprungtabelle wird aufgebaut. Beim sukkessiven Aufruf von Explode in der Variante ohne den 'Pattern'-Parameter muss die Sprungtabelle dann nicht jedesmal neu aufgebaut werden: Das spart ein paar Mikrosekunden.

Sollte sich Boyer-Moore (oder ein anderes Verfahren) doch als schneller erweisen, wird die Berechnung der Sprungtabelle(n) noch aufwändiger. Insofern ist es vorteilhaft, wenn nicht sogar zwingend, diese Berechung auszulagern und ggf. nur einmalig aufzurufen.

[Elvis]

Zitat:

Zitat von alzaimar

In der Test-Dpr dürften die Fehler behoben gewesen sein, nur in der isolierten csExplode.Pas-Unit waren sie es nicht. Ich schmeiss das Attachment mal raus.

Oh, ich hatte vorher gar nicht in das andere Ding reingekiekt... :oops:

Zitat:

Leider ignoriert dein Fix leere Strings am Ende: Der Text '-1-2-3-' enhält 5 Teilstrings: <leer>, "1", "2", "3" und <leer>. Dein Fix erkennt nur die ersten 4.

Dein Code sah so aus, als ob du das letzte Element ignorieren willst wenn nüschts drin steht. Kam mir auch komisch vor, aber ich dachte das sei so gewollt... :oops:
Einfach das "if" rausschmeißen und gut ist.

Zitat:

Na ja, so wie i und j Zähler sind, sind bei mir p Pointer. Und wenn ich 'i' sage, muss ich auch 'p' sagen. Aber so ist es auch gut. Allerdings müsste man dann folgerichtig aus dem 'i' einen 'Counter' machen...

i ist i und das ist eigentlich klar. Aber p, p0 und Konsorten sind beim Lesen nicht wirklich offensichtlich. ;)

Zitat:

Zitat:

Zitat von Elvis

Außerdem habe ich den Code mal in externe Iteratoren geworfen, für den Fall dass man die Ergebnisse a) nicht in einer Liste halten möchte und b) die VCL nicht referenzieren will.

Äh... ok. Ich glaube, es wäre besser, die Explode-Methoden mit dynamischen String-Arrays zu überladen.

Ich mag es eigentlich überhaupt nicht wenn mein Code Arrays an Stellen benutzt, die für den Konsumenten sichtbar oder schlimmer noch: Die bedeuten, dass er selbst Arrays nutzen muss.
Die Viecher lassen Code ziemlich schnell ziemlich ekelerregend aussehen, IMHO. ;)
Ausnahme sind open const arrays, die [1,2,3,] als Parameter ermöglichen.

Zitat:

Zitat:

Zitat von Elvis

btw: Warum hast du hier Instanzmethoden gewählt obwohl du gar keinen State zwichen den Calls halten musst?
Klassenmethoden hätten ja auch gereicht, bzw. sogar statische methoden in Delphi2006, wodurch du dir den impliziten parameter auf die class reference sparst:

Das stimmt so nicht: Vor dem Suchen/Zerteilen wird aus dem Teiler-String (Eigenschaft 'Pattern') eine Sprungtabelle erzeugt. Wenn ich viele Zeilen bearbeiten will, setze ich einmalig die Eigenschaft 'Pattern': die Sprungtabelle wird aufgebaut. Beim sukkessiven Aufruf von Explode in der Variante ohne den 'Pattern'-Parameter muss die Sprungtabelle dann nicht jedesmal neu aufgebaut werden: Das spart ein paar Mikrosekunden.

Hmmm... muss wohl ebenfalls nur in dem Archiv geändert worden sein... :oops:

Zitat:

Sollte sich Boyer-Moore (oder ein anderes Verfahren) doch als schneller erweisen, wird die Berechnung der Sprungtabelle(n) noch aufwändiger. Insofern ist es vorteilhaft, wenn nicht sogar zwingend, diese Berechung auszulagern und ggf. nur einmalig aufzurufen.

Keine Frage. ;)

[API]

Wie kann ich die Funktion Explode ändern, so dass aItems vom Typ "array of string" ist?

Delphi-Quellcode:

 Procedure Explode(Const aText, aPattern: String; aItems: TStrings);

also z.B

Delphi-Quellcode:

type
  TStrArray = array of string;

 Procedure Explode(Const aText, aPattern: String; aItems: TStrArray);

[alzaimar]

Hallo API, das kann man ohne Probleme einbauen. Ich wollte jedoch zunächst die notwendigen Optimierungen durchführen, eventuell den Quick-Search durch einen noch schnelleren ersetzen sowie die 'One-Char-Delimiter' Variante als ASM o.ä. implementieren (lassen).

Dann kann man eine zweite Klasse basteln, die Anstelle eines TStrings ein String-Array befüllt, oder einen Iterator, wie Elvis in beschreibt.

Zwei grundsätzliche Dinge:

Ein Iterator ist zwischen 1% und 30% langsamer, je nach Länge des zu suchenden Textes und Anzahl der Teilstrings. Da dieser Thread der Performanceoptimierung der Explode-Funktion dient, möchte ich den Iterator erst am Ende basteln. Grundsätzlich würde ich eine Implementierung der Explodefunktion auf Basis eines Iterators natürlich viel eleganter finden, aber die 30% Einbuße nehme ich nicht in Kauf, bloß um OO-konform zu sein.

Ich verstehe den Unterschied zwischen dynamischen Stringarrays und TStrings nicht (jedenfalls in diesem Fall): Beide müssen dynamisch angepasst werden und der Overhead einer TStringList ggü dem TStringArray dürfte minimal sein. Trotzdem könnte man eine TString-Array-Variante implementieren.

Lasst uns doch einfach weiter so an dem Teil basteln, das eine wirklich optimale Lösung entsteht. Wir können dann alle hier diskutierten Varianten (Iterator, TStringArray etc.) abschließend in die Code-Library packen. Elvis Ansatz des Iterators ist schon ziemlich elegant. Er hatte nur nicht die richtige Basisklasse, ansosnten wäre das Teil schon perfekt. :thumb:

[edit] Ich hab eben eine Boyer-Moore-Variante getestet, das derzeit beste Stringmatching-Verfahren... :gruebel: Kann ja sein, aber hier ist es ca. 40% langsamer :cry: [/edit]

[Elvis]

Zitat:

Zitat von alzaimar

Hallo API, das kann man ohne Probleme einbauen. Ich wollte jedoch zunächst die notwendigen Optimierungen durchführen, eventuell den Quick-Search durch einen noch schnelleren ersetzen sowie die 'One-Char-Delimiter' Variante als ASM o.ä. implementieren (lassen).

Ob ASM es wirklich bringt? das solte doch auch in normaler Hochsprache so auszudrücken sein, dass der Gewinn von ASM nicht mehr wirklich messbar bzw. sinnvoll wäre. (*sich da vage an den Doubletten-Thread erinnert* :mrgreen: )

Zitat:

Dann kann man eine zweite Klasse basteln, die Anstelle eines TStrings ein String-Array befüllt, oder einen Iterator, wie Elvis in beschreibt.

Man muss halt nur das Wachstum des Arrays kontrollieren. Das kann man von einer ollen Zählvariable, die die Anzahl der benutzten Elemente enthält über eine Klasse bis zu einem Record lösen.

Zitat:

Ein Iterator ist zwischen 1% und 30% langsamer, je nach Länge des zu suchenden Textes und Anzahl der Teilstrings. Da dieser Thread der Performanceoptimierung der Explode-Funktion dient, möchte ich den Iterator erst am Ende basteln. Grundsätzlich würde ich eine Implementierung der Explodefunktion auf Basis eines Iterators natürlich viel eleganter finden, aber die 30% Einbuße nehme ich nicht in Kauf, bloß um OO-konform zu sein.

War ja auch nur for fun und basierend auf der weniger optimierten Vorabversion deiner Explode-Implementierung. ;)
Wenn man die Dinge, die ihn wirklich kosten lassen, (Der Fieldoffset von zu vielen einzelnen Variablen an zu vielen Stellen zum Beispiel) minimiert, denke ich dass er nur 5-7% hinter einer wirklich krank optimierten Variante hängen wird. Solange er natürlich ähnlich stark optimiert ist.
Interessant wird sowas, wenn man möglichst wenig Speicher auf einmal reservieren will. Wenn der Input zum Beispiel ein Stream ist, der sich durch eine Datei bewegt und wirklich nur die gefundenen Schnipsel ausgespuckt werden sollen.
Das ist es zumindest wofür ich solche Iteratoren in meinen (Chrome/.Net) Programmen benutze. Wobei es ziemlich friemelig ist sowas selbst zu bastelt, im Gegensatz zum Chrome compiler, der dir autom. einen optimierten Iterator aus deinem Code generieren kann...

Zitat:

Ich verstehe den Unterschied zwischen dynamischen Stringarrays und TStrings nicht (jedenfalls in diesem Fall): Beide müssen dynamisch angepasst werden und der Overhead einer TStringList ggü dem TStringArray dürfte minimal sein. Trotzdem könnte man eine TString-Array-Variante implementieren.

Theoretisch wäre es für reine Zeitvergleiche besser eine Ableitung von TStringList zu nehmen, die alle Overrides durch "final" versiegelt hat, oder einen dyn. Array zu nehmen. TStrings als Typ für die Referenz zu nehmen bedeutet ja ständigen virtual Method dispatch, was ja nicht gerade förderlich für die Gesamtleistung ist. ;)

Zitat:

Lasst uns doch einfach weiter so an dem Teil basteln, das eine wirklich optimale Lösung entsteht. Wir können dann alle hier diskutierten Varianten (Iterator, TStringArray etc.) abschließend in die Code-Library packen.

Jupp, heute habe ich aber keine Lust mehr. Werde mir jetzt aber noch die Version von dir anschauen, die sich hinter dem Archiv verbirgt. :)

ediT: hui, da waren auch wieder ein paar Fipptehler drin :shock: