Substrings Extract Delimited Values

[Sequitar]

Ich würde gerne aus einem bestehenden String mit einem Delimiter gekennzeichnete Substrings extrahieren und in eine liste (hier: zu Testzwecken Tstrings, später eine custom DB / Trie exportieren).
Nun habe ich folgende Methode zur Extraktion, die aber extrem langsam scheint. Fällt Euch etwas ein, um die EXtraktion hier zu beschleunigen? Macht es Sinn mit Pchar zu arbeiten?
Vielen Dank für Eure Ideen

Vollst. Testcode:

Delphi-Quellcode:

Program Extractsubstrings;

{$APPTYPE CONSOLE}
{$R *.res}

// {$define unittests}

Uses
  Classes,
  Generics.Collections,
  System.SysUtils

{$IFDEF unittests},
  Unittests{$ENDIF};

Const
  Charsize = 2;

Procedure Testextractsubstrings(Const Str: String; Delimiter: Char;
  Items: Tlist<String> { class to be replaced by custom list or tree class } );
Var
  I, J, Len: Integer;
  P, Q, Oldp: Pchar;
  Itemtoadd: Pchar;
  Newpos, Oldpos: Integer;
Begin
  Assert(Assigned(Items));
  I := 0;
  Len := Length(Str);
  P := Pchar(Str);
  J := 1;
  Oldp := P;
  Oldpos := 0;
  While P <> '' Do
  Begin
    Inc(I);
    If P^ = Delimiter
    Then
    Begin
      Q := Oldp - I + 1;
      Getmem(Itemtoadd, (I - 1) * Charsize);
      Strlcopy(Itemtoadd, Q, I - 1);
      Items.Add(Itemtoadd);
      Freemem(Itemtoadd);
      Oldpos := Length(Itemtoadd);
      I := 0;
    End;
    Oldp := P + 1;
    Inc(P);
  End;
  // add last item
  While P^ <> Delimiter Do
    Dec(P);
  Itemtoadd := P + 1;
  Items.Add(Itemtoadd);
  // Writeln(Itemtoadd);
End;

Var
  I: Integer;
  S: String;
  List: Tlist<String>;

Const
  _max = 100000;

Begin
  Writeln('Extracting comma-delimited substrings. Testprogram');
  Try
    S := '';
    For I := 1 To _max Do
      S := S + Inttostr(I) + ',';
    Delete(S, Length(S), 1);
    // Writeln(S);
    List := Tlist<String>.Create;

{$IFDEF unittests} Tester.Test_leakProc(
      Procedure {$ENDIF}

      Begin
        Writeln('Starting test. Please wait');
        Testextractsubstrings(S, ',', List);
        Assert(List.Count = _max);
        List.Free;
      End{$IFDEF unittests}){$ENDIF};
    Writeln('Test finished');
    { TODO -oUser -cConsole Main : Insert code here }
  Except
    On E: Exception Do
      Writeln(E.ClassName, ': ', E.Message);
  End;
  Writeln('Test finished. Press any key to quit');
  ReadlN;

End.

Ebenfalls beigefügt.

[himitsu]

Wozu das GetMem und FreeMem?
Einfach mit Copy diesen Teil aus dem String holen.

Erspart auch die von dir vergessenen Ressourcenschutzblöcke.


PS:
TStringList.DelimitedText (beachte TStringList.StrictDelimiter)
oder SplitString
oder string.Split (siehe TStringHelper.Split)
oder ...



Statt Listen (Objekten) verwende ich gern Arrays ([OH]TArray<string>[/OH], bzw. das uralte TStringDynArray), weil ich mir dort das Freigeben spare und deswegen dann auch keine Ressourcenschutzblöcke (von mir im Code) nötitg.

[mytbo]

Zitat von Sequitar:

Fällt Euch etwas ein, um die EXtraktion hier zu beschleunigen? Macht es Sinn mit Pchar zu arbeiten?

Laufzeit ca. 4 Millisekunden:

Delphi-Quellcode:

const
  MAX_COUNT = 100000;
  
  function GetNextItem(const pmcDelimiter: Char; pmSrcPos: PChar; out pmNextPos: PChar): String;
  var
    pStart: PChar;
  begin
    if pmSrcPos = Nil then
    begin
      pmNextPos := pmSrcPos;
      Exit(''); //=>
    end;

    while pmSrcPos^ in [#9, ' '] do Inc(pmSrcPos);  // Trim left
    pStart := pmSrcPos;
    repeat
      if pmSrcPos^ = #0 then
      begin
        pmNextPos := Nil;
        Break; //=>
      end
      else if pmSrcPos^ = pmcDelimiter then
      begin
        pmNextPos := pmSrcPos + 1;
        Break; //=>
      end
      else
        Inc(pmSrcPos);
    until False;
    while (pmSrcPos > pStart) and (pmSrcPos[-1] in [#9, ' ']) do Dec(pmSrcPos);  // Trim right
    SetString(Result, pStart, pmSrcPos - pStart);
  end;

var
  p: PChar;
  src: String;
  timer: TPrecisionTimer;
begin
  for var i: Integer := 1 to MAX_COUNT do
    src := src + i.ToString + ',';
  Delete(src, Length(src), 1);

  var sList := TStringList.Create;
  try
    timer.Start;
    p := PChar(src);
    while p <> Nil do
      sList.Add(GetNextItem(',', p, p));
    ShowMessage(Format('Count: %d, Time: %s', [sList.Count, timer.Stop]));
  finally
    sList.Free;
  end;

Ohne Gewähr!

Bis bald...
Thomas

[Olli73]

Warum nicht einfach:

Delphi-Quellcode:

var
  SL: TStringList;
begin
  SL := TStringList.Create;
  SL.Delimiter := ADelimiter;
  SL.StrictDelimieter := True;
  SL.DelimitedText := AText;
  ...

Oder habe ich etwas falsch verstanden?

[mytbo]

Zitat von Olli73:

Oder habe ich etwas falsch verstanden?

Grundsätzlich hast du nichts falsch verstanden. In der Anfrage ging es um Beschleunigung am Beispiel. Meine Lösung ist ca. 1/3 schneller als das TStrings Äquivalent. In der Praxis vermutlich irrelevant.

Bis bald...
Thomas

[Uwe Raabe]

Das Anfügen an die TStringList benötigt aber ja auch seine Zeit.

Einen wohl auch akzeptabel schnellen Ansatz bietet das bordeigene Split:
  var arr := src.Split([',']);

[mytbo]

Zitat von Uwe Raabe:

Einen wohl auch akzeptabel schnellen Ansatz bietet das bordeigene Split:
  var arr := src.Split([',']);

Richtig! Diese Lösung ist ca. 1/3 schneller als mein Vorschlag. Da der Fragesteller kein Neuling ist und wir nicht wissen, welche zusätzlichen Anforderungen es noch gibt, hat sich mein Vorschlag konkret auf die Frage des Posters und der Verbesserung am Beispiel bezogen. Ich persönlich hätte die mORMot Lösung genommen.

Bis bald...
Thomas

[himitsu]

Zitat von Uwe Raabe:

Das Anfügen an die TStringList benötigt aber ja auch seine Zeit.

Sie haben da schon etwas optimiert und ändern den Speichern nicht bei jedem einzelnen Add,
aber wenn es unbedingt sein muß, dann SL.Capacity := 1000000; vor dem Hinzufügen.

[freimatz]

Wenn Geschwindigkeit so eine Rolle spielt - was ich mir bei einer DB gar nicht so recht vorstellen kann - dann wäre es eine Idee den String nicht vorgängig aufzusplitten und das Ergebnis zu speichern sondern erst später die String zu extrahieren und gleich zu verwenden.
Und wenn es doch sein muss nicht die ganzen strings zu speichern sondern nur die Start- und End-Positionen im Ausgangsstring.

[Sequitar]

Danke Euch für Eure Vorschläge!
Die Lösung mit
s.split() macht bisher einen guten Eindruck. Die Lösung von Thomas / mytbo werde ich noch prüfen


Zu den spezifischen Anforderungen wäre nur noch zu sagen:
- ich lade zzt eine Liste mit min 50M, max 100M, kommaseparierten (CSV) Einträgen vorberechnteter / vordefinierter Strings aus einer *.zip- Resource
- Ziel: es ist im Anschluss zu prüfen ob ein bestimmter Wert in dieser/n Liste/n vorkommt. Daher (denke ich) müsste ich die Resource bei programmstart durchsuchbar laden
- ich hatte überlegt, zwecks Speicherreduktion die Werte in einem (Binary-)Trie zu speichern (hier werden nicht die kompletten Strings gespeichert) statt in einer Stringlist / Tlist<>. Allerdings muss ich da noch überprüfen, inwiefern da die Geschwindigkeitseinbüßen zum durchsuchen meines Tries relevant sind.
-Ggf hatte ich überlegt, direkt auf Datenbank umzusteigen

Die Resourcen sind derzeit in einem Zip archiv (einzelne *.txt files) hinterlegt, Gäbe es hier eine Möglichkeit, ggf direkt auf den Zipstream zuzugreifen und darin zu suchen - statt extraktion/ übertragung von dort, oder macht das eher keinen Sinn?

Weitere Anforderungen an Format / Speicherung gibt es vorerst keine.>
@himitsu, wahrscheinlich wird es nicht direkt ersichtlich, wie viele Einträge geladen werden. Das könnte ich allerdings hierzu noch anpassen, um die capacity zu setzen