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

[API]

Version 1.1 enthält einen Bug in TStringDivider.Prepare

Falls Length(fPattern)= 1 ist erbigt fPatternLength2 = -1 was zu einem "Integer overflow" führt,
da fPatternLength2 als Cardinal deklariert ist.

Bugfix: Überprüfen, ob fPattern > 1

Delphi-Quellcode:

  If length(fPattern) > 1 Then
    fPatternLength2 := fPatternLength - 2;

Delphi-Quellcode:

Procedure TStringDivider.Prepare;
//..
Begin
  fPatternLength := Length(fPattern);
  fPatternLength1 := fPatternLength - 1;
  fPatternLength2 := fPatternLength - 2;
  cPatternFirstChar := fPattern[1];
  cPatternLastChar := fPattern[fPatternLength];
  pPattern := @fPattern[2];

[alzaimar]

API: Dieser Fehler ist zwar irrelevant, aber ein Bug ist ein Bug, und nun isser weg. Neue Version ist im ersten Post.

Elvis: Die Sache mit den finals wusste ich nicht. Mal sehen, was das bringt. Zur potentiellen ASM-Optimierung: Da es sich um eine Art 'Pos' auf Char-Ebene handelt, könnte ich mir schon vorstellen, das man hier etwas drehen könnte. Leider hab ich von Intel-ASM keinen Schimmer.

Hier gibt es die FastStrings-Toolsammlung, die Stringfunktionen in ASM implementiert, vielleicht kann man sich hier etwas abkupfern.

[alzaimar]

Soo, nächste Version oben reingestellt.

[mimi]

sag mal ist die Funktion jetzt Fertig ?
Würde sie gerne in meinem Lazarus Projekt unter Linux einsetzten.
(So Fern das geht).

kann die Funktion dann auch mit sowas umgehen:
testStr:='Hallo "Dies ist ein Text" hallo2'
Wenn ich jetzt z.b. hallo2 aufspielten wollte müsste ich ja vohrer alle Leerzeichen zählen.
Und nicht einfach sagen 1 weil nach dem ersten index würde ja jetzt hallo2 kommen.
Wegen den "".

[alzaimar]

Ich denke, das die Klasse funktionsfähig ist. Ich verstehe nur nicht genau, was Du mit deinem Beispiel meinst.

[mimi]

Ich habe jetzt folgenden String:

Hallo1 "Test1 Test2 Test3" Hallo2 Hallo3

Hallo1 ist jetzt der erste Index
"Test1 Test2 Test3" ist jetzt der zweite Index
Hallo2 ist der Dritte Index.
Hallo3 ist der Vierte Index.

sowas meinte .

[alzaimar]

Dazu ist diese Explode-Funktion nicht gedacht.

[hitzi]

@mimi: Das solltest du mit einer Stringlist lösen können.

Delphi-Quellcode:

var sl : TStringlist;
begin
  sl := TStringlist.Create();
  try
    sl.Delimiter := #32;
    sl.DelimitedText := 'Hallo1 "Test1 Test2 Test3" Hallo2 Hallo3';
    // sl[0] ist jetzt Hallo1
    //sl[1] ist Test1 Test2 Test3
    //sl[2] ist Hallo2
    //sl[3] ist Hallo3
  finally
    FreeAndNil(sl);
  end;
end;

Der Code ist aber ungetestet!

[C.Schoch]

Hi,
Ich hab gerade bei der einen Fehler in der Procedure QSExplode endeckt,
und zwar kommt es manchmal zu einem "Fehler bei Bereichsprüfung"

Delphi-Quellcode:

Procedure TStringDivider.QSExplode(Const aText: String; aItems: TStrings);
// ...
  While i <= k Do Begin
    If (fPatternFirstChar = aText[i]) And (fPatternLastChar = aText[i + fPatternLength1]) Then
      If (fPatternLength < 3) Or CompareMem(@aText[i + 1],fPatternPtr,fPatternLength2) Then Begin
        aItems.Add(Copy(aText,iTextStart,i - iTextStart));
        inc(i,fPatternLength);
        iTextStart := i;
        Continue;
      End;
    inc(i,fSkip[aText[i + fPatternLength]]); //<-- Hier Tritt der Fehler auf
  End;
// ...

Ich hab mal ein Beispielprojekt gemacht den Fehler zu veranschaulichen.

[alzaimar]

Hallo, das Problem ist bekannt und beseitigt. Ich lade mal die aktuelle Version hoch. Nebenbei tritt der Fehler nicht auf, wenn Du die Bereichsprüfung ausschaltest. Korrekt ist das aber nicht.

[MStoll]

Hallo,

coole Sache, dass ihr mit vielen Leuten das Projekt angegangen seid, ne Funktion zu optimieren. :dp:
Ich wollte sie auch mal testen, um sie ggf. einzusetzen. Allerdings hab ich dabei (jedenfalls in meinem Fall) festgestellt, dass ich bereits ne schnellere Variante hatte (was mich angesichts eures Engagements bzgl. des Projekts etwas verwundert hatte).
Aber ehe ich hier irgendwie falsch liege, möchte ich euch bitten, meine Variante doch auch mal zu testen (sie arbeitet allerdings auf array of string und nicht mit einer StringList). Je nach Ergebnis eurer Tests könnt ihr mich sehr gerne korrigieren oder eben meine Variante einbauen.

Das soll jetzt nicht irgendwie eure Arbeit in Frage stellen, bitte nicht falsch verstehen. Ich wundere mich ja selbst über das Ergebnis meines Tests. :gruebel:

Delphi-Quellcode:

function explode(const n,s : string) : TStringDynArray;
var temp : array of integer;
    Len : integer;
    x, count, laenge : integer;

    function follows(const s,n : string; pos1 : integer) : boolean;
    var x : integer;
    begin
         {if pos1 + length(n) > length(s)+1 then
         begin
              result := false;
              exit;
         end;}

         for x := 0 to length(n)-1 do
             if n[x+1] <> s[pos1 + x] then
             begin
                  result := false;
                  exit;
             end;

         result := true;
    end;

begin
     x := 1;
     //SetLength(temp, 1);
     SetLength(temp, 20);
     count   := 1;
     temp[0] := 1;

     laenge := Length(s) - Length(n) + 1;

     while x <= laenge do
     begin
          if follows(s,n,x) then
          begin
               inc(x, length(n));
               //SetLength(temp, length(temp)+1);
               inc(count);
               if length(temp) < count then
                  SetLength(temp, count + 20);
               //temp[high(temp)] := x;
               temp[count-1] := x;
               continue;
          end;
          inc(x);
     end;
     SetLength(temp, count);

     SetLength(result, length(temp));
     for x := 0 to High(temp)-1 do
     begin
          Len := temp[x+1]-temp[x]-length(n);

          result[x] := copy(s, temp[x], Len);
     end;

     Len := length(s)-temp[high(temp)]+1;
     result[high(temp)] := copy(s, temp[high(temp)], Len);
end;

n ist das Pattern, s der große String.

Ich hab das getestet mit folgender Datei im Anhang, hab sie 8x hintereinander in einen String reingetan (damit es auch wirklich viele Daten sind) und dann mit verschiedenen Patterns (#10, ' ', '0') getestet.

Gruß
Michael

[C.Schoch]

Super vielen Dank alzaimar!

Bin aber selbst nicht ganz durchgestiegen warum der Fehler überhaupt auftritt, wäre nett wenn mir das mal einer erklären könnte, weil eigentlich bin ich ja mit dem Index noch im Breich des Arrays :gruebel:

[alzaimar]

@MStoll:
In der Testumgebung aus dem 1.Post schneidet Deine Version zwischen 1.2 und 4x langsamer ab, als die vorgestellte Variante mit QuickSearch. Das ist aber auch nicht weiter verwunderlich.

Der Quicksearch-Algorithmus spielt seine Stärken um so deutlicher aus, je länger der Suchtext und/oder Trenntext ist. Wenn der Trenntext aus genau einem Zeichen besteht, wird eine triviale Suche per Schleife aufgerufen. Du hast in deinen Tests ja nur nach diesem einen Zeichen gesucht und da wäre es denkbar, das Deine Variante aufgrund des geringeren Overheads besser abschneidet.

In einem anderen Thread wird die Basis, also das Suchen nach dem nächsten Vorkommen des 'Delimiters' optimiert. Ich hatte bisher noch keine Zeit, das in den TStringDivider einzubauen, es sollten sich jedoch bei kürzeren Delimitern noch drastische Geschwindigkeitsvorteile ergeben.

@C.Schoch:
Sei 'i' die aktuelle Position im Text T, p der zu suchende Text und Lp dessen Länge. Der Trick besteht darin, das Zeichen T[i+Lp] zu analysieren. Und dieser Wert T[i+Lp] kann eben leider auch Length(T)+1 sein. Das spielt unter C keine Rolle, denn dann ist T[i+Lp]=#0, aber bei Delphi ist das undefiniert, oder eben 'out of range'. Ich hatte immer den 'RangeCheck' ausgeschaltet, aber bei sehr großen Strings liegt dieser Wert dann trotzdem in der Pampa. Also muss man für den einen Fall (i=Length(T)-Lp+1) einen Sonderfall einbauen.

Beispiel:
Sei T='ABCDEFG', p= 'XYZ' und i=1. Da nun T[i+Lp]='D' nicht im Suchtext vorkommt, können wir gleich an die Stelle 5 springen und da unser Glück nochmal versuchen. Nun prüfen wir wieder das Zeichen T[i+Lp=5+3=8]. Hups, das gibts ja nicht, denn T ist ja nur 7 Zeichen lang=>Peng

[MStoll]

@alzaimar:
Ok, das kann gut sein. :thumb: Hab es nicht mit mehr als einem Zeichen im Delimiter probiert.

[stoxx]

30%- 75% Prozent Performancegewinn gewinnst Du bei einem Seperator der Länge 1, wenn Du die lokale Funktion in der Explode Procedure weglässt.
(ein Zeichen als Seperator braucht man ja häufig für CSV Files)
Schon wenn die _AddString Procedure nur drin steht, und gar nicht aufgerufen wird, bricht die Performance durch den Aufruf-Stack massiv ein.
TStrings ist auch ein sehr schwieriges Nadelöhr. Vielleicht besser doch ein Dynarray als Ergebnistyp verwenden, neuerdings kann man ja auch Records Definieren, die einen String beinhalten können, obwohl nicht als Shortstring deklariert.
SetString könnte man noch durch die beste ASM Fastmove Funktion ersetzen. Dann wirds sogar noch schneller...
Wenn man dann noch mit CSV Dateien arbeitet, und weiß, dass eine Spalte wahrscheinlich nie länger als 255 Zeichen wird, dann ist shortstring noch etwas
schneller.
Dann schafft man es auch, eine 100 MB CSV-Datei in 1,5 sec komplett zu durchforsten :-)

die funktion muss also raus:

Delphi-Quellcode:

  Procedure _AddString;
  Var
    sTmp: String;

  Begin
    SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
    aItems.Add(sTmp)
  End;

neue Variante:

Delphi-Quellcode:

Procedure TStringDivider.Explode(Const aText: String; aItems: TStrings);
Var
  ptrSubStr,ptrText,ptrTextEnd: PChar;
  sTmp: String;
Begin
  If length(fPattern) > 1 Then
    QSExplode(aText,aItems)
  Else Begin
    aItems.clear;
    ptrText := PChar(@aText[1]);
    ptrSubStr := ptrText;
    ptrTextEnd := PChar(@aText[Length(aText)]);
    inc(ptrTextEnd);
    Repeat
      If ptrText^ = fPatternFirstChar Then Begin

        SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
        aItems.Add(sTmp);

        inc(ptrText);
        ptrSubStr := ptrText;
      End
      Else
        inc(ptrText);
    Until Integer(ptrText) = Integer(ptrTextEnd);

    SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
    aItems.Add(sTmp);


  End;
End;

Hier mal ein Performancevergleich:
Alte Variante:
-------------------
Using TStringDivider in TStringList
100 chars per line: 1000000 lines in 2907 tics, 343997 lines per sec, 33,6 mb/s (del = ";")
100 chars per line: 1000000 lines in 1297 tics, 771010 lines per sec, 75,3 mb/s (del = "<Foobar>")
100 chars per line: 1000000 lines in 2187 tics, 457247 lines per sec, 44,7 mb/s (del = "ABCDE")
10000 chars per line: 50000 lines in 3781 tics, 13224 lines per sec, 129,1 mb/s (del = ";")
10000 chars per line: 50000 lines in 1422 tics, 35162 lines per sec, 343,4 mb/s (del = "<Foobar>")
10000 chars per line: 50000 lines in 2188 tics, 22852 lines per sec, 223,2 mb/s (del = "ABCDE")
1000000 chars per line: 500 lines in 3281 tics, 152 lines per sec, 148,8 mb/s (del = ";")
1000000 chars per line: 500 lines in 1047 tics, 478 lines per sec, 466,4 mb/s (del = "<Foobar>")
1000000 chars per line: 500 lines in 1718 tics, 291 lines per sec, 284,2 mb/s (del = "ABCDE")

Neue Variante:
-----------------
100 chars per line: 1000000 lines in 2219 tics, 450653 lines per sec, 44,0 mb/s (del = ";")
100 chars per line: 1000000 lines in 1359 tics, 735835 lines per sec, 71,9 mb/s (del = "<Foobar>")
100 chars per line: 1000000 lines in 2172 tics, 460405 lines per sec, 45,0 mb/s (del = "ABCDE")
10000 chars per line: 50000 lines in 2234 tics, 22381 lines per sec, 218,6 mb/s (del = ";")
10000 chars per line: 50000 lines in 1438 tics, 34771 lines per sec, 339,6 mb/s (del = "<Foobar>")
10000 chars per line: 50000 lines in 2219 tics, 22533 lines per sec, 220,0 mb/s (del = "ABCDE")
1000000 chars per line: 500 lines in 1875 tics, 267 lines per sec, 260,4 mb/s (del = ";")
1000000 chars per line: 500 lines in 984 tics, 508 lines per sec, 496,2 mb/s (del = "<Foobar>")
1000000 chars per line: 500 lines in 1735 tics, 288 lines per sec, 281,4 mb/s (del = "ABCDE")



30% Performancezuwachs (del = ";") - 100 chars per line: 1000000 lines
70% Performancezuwachs (del = ";") - 10000 chars per line: 50000 lines
75% Performancezuwachs (del = ";") - 1000000 chars per line: 500 lines

[alzaimar]

Hi Stoxx,

Danke für die Tipps. Ich habe mittlerweile eine Version, die die FastCode-Gewinner mit einbezieht. Bei Trennern der Länge 1 ist die neue Version um ein vielfaches schneller.
Hier in der Delphi-Praxis habe ich den Suchalgorithmus zur Optimierung vorgestellt. Letztendlich habe ich eine Kombination aus FastCode und QSearch als bisherigen Outperformer implementiert.

Meine Pos-Version ist im Anhang, wenn Du magst, kannst Du das ja in die Explode-Routine einbauen. Ganz speziell das sehr schnelle 'CharPos' dürfte interessant sein.

In einer QSearch-Version war der Fehlerteufel drin. Ich hoffe, das das bei der hier nicht der Fall ist. Wenn der Trenner ganz am Ende steht, hat die ursprüngliche QSearch-Variante versagt. Die Version im Anhang arbeitet korrekt.

[edit] Was hab ich bloß für ungetesteten Müll auf meinem Laptop? Da war doch glatt ein Fehler drin [/edit]

Kurz getestet (CharPos und FastMove): Geschwindigkeitszuwachs 7-50%

[grenzgaenger]

Zitat:

Zitat von stoxx

(ein Zeichen als Seperator braucht man ja häufig für CSV Files)

in CSV files hat man aber auch(sehr häufig) eingeklammerte zeichenketten. wie

Zitat:

1, 23, "hier wollen wir mal was schreiben, und hier gehts weiter", und 'n neuer string, auch das geht, 45 223

dabei müsste die folgende zerlegung herhauskommen bei 'n quote von " und 'n delemiter von ,

• 1
• 23
• hier wollen wir mal was schreiben, und hier gehts weiter
• und 'n neuer string
• auch das geht
• 45 223

aber dafür ist ja explode nicht gedacht, oder doch?

einen schönen guten morgen
GG

[alzaimar]

Nein.

[stoxx]

Zitat:

in CSV files hat man aber auch(sehr häufig) eingeklammerte zeichenketten. wie

na die müsste man halt getrennt rauslöschen, wir haben solche CSV Files nicht :-) .. oder damit keine so häufigen Stringkopien gemacht werden, das Setstring so verändern, dass hochkommas nicht mit reingesetzt werden .. man müsste die Explodefunktion nur kurz umschreiben ...

[stoxx]

Zitat:

In einer QSearch-Version war der Fehlerteufel drin. Ich hoffe, das das bei der hier nicht der Fall ist. Wenn der Trenner ganz am Ende steht, hat die ursprüngliche QSearch-Variante versagt. Die Version im Anhang arbeitet korrekt.

hättest Du vielleicht die korriegierte Variante von QSearch bitte noch in Pascal Roh-Text? Ich hab immer gern beide Variante implementiert, falls mal irgendwas nicht funktioniert und der Code auf 128 Bit Windows nicht mehr laufen sollte :-)
Das wäre ganz nett von Dir!!

Zitat:

Kurz getestet (CharPos und FastMove): Geschwindigkeitszuwachs 7-50%

hast Du jetzt FastPos in die Explodefunktion schon eingebaut?
Vielleicht magst die ja noch in den ersten Post dranhängen? ... nicht ersetzen, das wäre nicht gar so schön ...

Die kritischste Zeit in Deiner Implementierung ist eigentlich das zweimal "harte" kopierens des Strings einmal in einem Tempstring und dann nochmal in eine Tstringlist (TStrings) ..
Und zusätzlich glaube ich nicht, dass man die Dividerklasse so verwenden möchte, dass als Endprodukt eine Tstringliste der getrennten Strings haben möchte, sondern man möchte ja eher per Index auf die einzelnen Elemente zugreifen können. Man würde also Deine Rückgabe TStrings nochmal durchlaufen, und erst dann verarbeiten. Besser ist es also wenn man die reine Explodefunktion ohne Kapslung intelligent in seine eigene Klasse einbaut, die dann noch einen Indexzugriff hat, auf die einzelnen elemente per property hat, wo eine Stringkopie erst im allerletzten Moment zum beispiel an eine StrToFloatDef() Funktion geleitet wird...

[grenzgaenger]

Zitat:

Zitat von stoxx

wir haben solche CSV Files nicht :-)

tja, wenn du nicht viel mit CSV arbeitest... dann tut es wohl die funktion auch für dich...

[stoxx]

Zitat:

tja, wenn du nicht viel mit CSV arbeitest... dann tut es wohl die funktion auch für dich..

tss .. immer diese, "ich bin wichtiger Mentalität"
man, man ... nein, unsere CSV Files sind sogar größer als Deine. (mehrere 100 MB und ingsesammt soviele dass mehrere Gigabyte verarbeitet werden müssen)

Und der CSV Reader, den wir nun gebastelt haben, ist sehr schick uns wahnsinnig schnell.
Es steht Dir doch frei, die Funktion so zu verändern, wie Du möchtest. Wo liegt Dein Problem?

[Elvis]

Zitat:

Zitat von stoxx

Zitat:

tja, wenn du nicht viel mit CSV arbeitest... dann tut es wohl die funktion auch für dich..

tss .. immer diese, "ich bin wichtiger Mentalität"
...
Wo liegt Dein Problem?

Sein Problem ist wohl das von sehr vielen anderen auch: Er wird wohl des öfteren mit (MSFT-) Software zu tun gehabt haben, die behauptet CSV lesen oder schreiben zu können, in Wirklichkeit aber etwas total anderes macht...
Das was du da hast ist nämlich keine Funktion zum Lesen von CSV-Dateien, da diese ein Standard sind, zu dem nunmal auch die Quotes gehören.
Das mag für dich speziell keinen Unterschied machen ( :) ), da du da vllt nur Zahlen hast.
Aber vllt kannst du das verkniffene Murren von Bernhard nun nachvollziehen?

[stoxx]

Delphi-Quellcode:

Aber vllt kannst du das verkniffene Murren von Bernhard nun nachvollziehen?

Im Moment noch nicht. Wie ich ihn verstanden habe, sind doch die störenden Zeichen nur Hochkommas am Anfang und Ende eines Strings.
Man würde also einfach mit if prüfen, ob das der Fall ist und ändert die SetString Funktion noch ein bisschen, dann eignet sich die explode Funktion auch zum einlesen solcher CSV Files.

(Die Abkürzung CSV steht für Character Separated Values)

Wenn also noch Hochkommas oder anführungszeichen drin stehen .. und man die nicht haben will. Müssen sie also noch raus. Die CSV Datei kann ja nun nix dafür, dass sie (wahrscheinlich ohne Header) so komisch geschrieben wurde .....

[grenzgaenger]

Zitat:

Zitat von stoxx

Delphi-Quellcode:

Aber vllt kannst du das verkniffene Murren von Bernhard nun nachvollziehen?

Im Moment noch nicht. Wie ich ihn verstanden habe, sind doch die störenden Zeichen nur Hochkommas am Anfang und Ende eines Strings.
Man würde also einfach mit if prüfen, ob das der Fall ist und ändert die SetString Funktion noch ein bisschen, dann eignet sich die explode Funktion auch zum einlesen solcher CSV Files.

(Die Abkürzung CSV steht für Character Separated Values)

Wenn also noch Hochkommas oder anführungszeichen drin stehen .. und man die nicht haben will. Müssen sie also noch raus. Die CSV Datei kann ja nun nix dafür, dass sie (wahrscheinlich ohne Header) so komisch geschrieben wurde .....

tzzz, tzz. schicke funktion, für mich total unbrauchbar! deswegen halt ich mich auch mit dem teil nicht auf. BTW CSV steht für comma sepaprated file, im deutschsprachigen raum ist halt dsa comma meist ein semikolon.

die anführungszeichen stöhren mich nicht im geringsten. im gegenteil, die quoten einen textstring. in dessen keine interpretation des delimiters stattfinden darf. falls doch, ist die funktion falsch. der delimiter kann je nach land unterschiedlich sein, z. b. "", '', <>, ><, <<>>, >><<, ...

aber egal, noch 'n schönen tag.
GG

//EDIT: hier noch 'n link zum CSV Format link

[stoxx]

Zitat:

die anführungszeichen stöhren mich nicht im geringsten. im gegenteil, die quoten einen textstring. in dessen keine interpretation des delimiters stattfinden darf. falls doch, ist die funktion falsch. der delimiter kann je nach land unterschiedlich sein, z. b. "", '', <>, ><, <<>>, >><<, ...

aber egal, noch 'n schönen tag.

boah ... sowas aggressives .. wer ist Dir denn über die Schuhe gelaufen.
Nein, die Funktion ist natürlich nicht falsch, die macht genau das, was sie tun soll. Einen String trennen, der getrennt ist, durch ein oder mehrere Zeichen! Und wenn alles mit "bla" getrennt ist, tut sie das auch!
Anschauen und ausprobieren würde vielleicht helfen, anstatt rumzumeckern. In der Funktion gibt es überhaupt kein problem, außer dass sie noch um Faktor 2 beschleunigt werden kann, wenn man die rückgabe noch anders gestaltet ...
(mit derselben gewünschten Funktionalität)
Eventuell müsste man die Strings selber erzeugen und die TList hinter TStrings selber befüllen, dass nicht noch einmal speicher kopiert wird, wenn man denn unbedingt TStrings als Rückgabe braucht, geht aber auch anders ...

[Elvis]

Zitat:

Zitat von stoxx

boah ... sowas aggressives .. wer ist Dir denn über die Schuhe gelaufen.

Und er benutzt einfach den Avatar von Bernhard Geyer. :shock:
Er hat irgendwo schon recht, aber so tut das nicht Not... :roll:

[alzaimar]

Zitat:

Zitat von grenzgaenger

BTW CSV steht für comma sepaprated file, im deutschsprachigen raum ist halt dsa comma meist ein semikolon.

. Genauergesagt handelt es sich um das 'Listentrennzeichen' in den internationalen Systemeinstellungen.

Zitat:

Zitat von grenzgaenger

...falls doch, ist die funktion falsch. der delimiter kann je nach land unterschiedlich sein, z. b. "", '', <>, ><, <<>>, >><<, ...

Es handelt sich hier nicht um einen CSV-Parser, sondern um einen Ersatz für 'Explode'. Wenn Dir das nicht reicht, dann prüfe nach dem Erkennen des nächsten Strings einfach, ob das Zeichen ein '"' ist. Wenn ja, suchst Du mit meiner FastPos-Routine das nächste '"', stellst sicher, das es nicht escpaped ist (hua, was für ein Deutsch), und extrahierst dann.

Aber nochmal. Niemand hat behauptet, das die csExplode-Routine mit CSV klar kommt, also hört auf mit euren Zickereien. Man kommt sich ja vor wie auf einem Mädcheninternat. :mrgreen:

[stoxx]

Delphi-Quellcode:

In einer QSearch-Version war der Fehlerteufel drin. Ich hoffe, das das bei der hier nicht der Fall ist.

die korrigierte Variante von QPosEX in Pascal und nicht ASM würde mich äußerst stark interessieren :-)
Wäre das möglich? :-) .. Vielen Dank !


(Function QPosEx(SearchFor, SearchIn: String; Start: integer): integer;)

[mimi]

Zitat:

enn Dir das nicht reicht, dann prüfe nach dem Erkennen des nächsten Strings einfach, ob das Zeichen ein '"' ist

Es währe aber trozdem Toll wenn die Funktion das unterstützen könnte. Das muss ja nix mit CSV zu tun haben.
Sowas brauche ich gelegendlich mal. Darum habe ich mir eine eigne Funktion dafür geschrieben. Die aber wahrscheinlich viel langsamer ist als deine....

Evlt. teste ich mal deine Funktion unter Lazarus. Weil ich gerne Texte Parse die so aufgebaut sind:
<fg="wert">text</fg>
Im Moment mache ich das mit Pos und PosExt....

Aber wenn das deine Funktion schneller kann, könnte ich ja mal schauen ob ich darauf umsteigen kann.