Alternative zu PosEx

[Blup]

Zum Vergleich mit Pos() und SetLength() für das Ergebnis:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string): TIntegerDynArray;

  function Search(var Index: Integer): Boolean;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Length(Result) < Count then
      SetLength(Result, Count * 4);

    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Code:

sRandomString := RandomString(MaxInt div 8 - 6) + 'PaPaPa'
0:00:01.327

SetLength(Positions, 3)
StrPosEx('PaPa', 'sRandomString', Positions)
0:00:00.081
Result = 1
Positions = [268435450,0,0]

Result := MyStrPosEx('PaPa', 'sRandomString')
0:00:00.075
Result = [268435450,268435452]

[Amateurprofi]

Zitat von Blup:

Zum Vergleich mit Pos() und SetLength() für das Ergebnis:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string): TIntegerDynArray;

  function Search(var Index: Integer): Boolean;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Length(Result) < Count then
      SetLength(Result, Count * 4);

    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Code:

sRandomString := RandomString(MaxInt div 8 - 6) + 'PaPaPa'
0:00:01.327

SetLength(Positions, 3)
StrPosEx('PaPa', 'sRandomString', Positions)
0:00:00.081
Result = 1
Positions = [268435450,0,0]

Result := MyStrPosEx('PaPa', 'sRandomString')
0:00:00.075
Result = [268435450,268435452]

Und jetzt das Ganze noch einmal, wenn der zu durchsuchende Text 80 Mio Zeichen hat, nur aus "0" .. "9" besteht und Du die Fundstellen für die "7" haben möchtest.

[Blup]

Ich habe den Faktor bei "SetLength(Result, Count * 2)" auf 2 geändert. Das bringt noch ein par Millisekunden.

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string): TIntegerDynArray;

  function Search(var Index: Integer): Boolean;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Length(Result) < Count then
      SetLength(Result, Count * 2);

    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Trotzdem ist natürlich jedes "SetLength()" potentiell mit dem Umkopieren des Inhalts verbunden und benötigt Zeit.
Wenn man die Menge der Ergebnisse abschätzen kann, ist es sinnvoll das Array gleich in der entsprechenden Größe zu reservieren und zum Schluss zu kürzen.

Code:

sRandomString := RandomString(8000000)
0:00:00.402

SetLength(Positions, 10000000)
StrPosEx('7', 'sRandomString', Positions)
0:00:00.102
Result = 7999774
Positions = [15,19,45,63,98,113,122,127,132,133, ... ,0,0,0,0,0,0,0,0,0,0]

Result := MyStrPosEx('7', 'sRandomString')
0:00:00.217
Length = 7999774
Result = [15,19,45,63,98,113,122,127,132,133, ... ,79999929,79999936,79999958,79999963,79999969,79999970,79999975,79999976,79999990,79999995]

Die Unterschiede im Ergebnis liegen hier daran, dass "777" bei mir zwei Fundstellen bedeuten:

Code:

sRandomString := RandomString(8000000)
0:00:00.407

SetLength(Positions, 1000000)
StrPosEx('77', 'sRandomString', Positions)
0:00:00.091
Result = 727065
Positions = [322,351,413,526,563,800,807,828,854,1113, ... ,0,0,0,0,0,0,0,0,0,0]

Result := MyStrPosEx('77', 'sRandomString')
0:00:00.108
Length = 799271
Result = [322,351,352,413,526,563,800,807,828,854, ... ,79999371,79999406,79999515,79999730,79999819,79999827,79999843,79999868,79999931,79999954]

[himitsu]

Wenn es möglich ist, das Resize "inplace" zu machen, dann geht es schnell.
Wenn dahinter noch freier Speicher liegt und dieser genutzt werden kann ...


Bzw. vorher bereits mehr/genug reservieren, anstatt mittendrin immer wieder neu.

[Blup]

Das anfängliche "SetLength()" bewirkt weniger als erwartet, dafür bingt "inline" deutlich mehr Zeitersparnis:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string; Estimated: Integer = 0): TIntegerDynArray;

  function Search(const SearchFor, SearchIn: string; var Index: Integer): Boolean; inline;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  SetLength(Result, Estimated);
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(SearchFor, SearchIn, Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Estimated < Count then
    begin
      Estimated := Count * 2;
      SetLength(Result, Estimated);
    end;
    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Code:

StrPosEx('7', sRandomString, Positions)
0:00:00.102

Result := MyStrPosEx('7', sRandomString, 0)
0:00:00.168

Result := MyStrPosEx('7', sRandomString, 10000000)
0:00:00.157

[Blup]

Hab mich überzeugen lassen, "MyStrPosEx('77', '777')" liefert jetzt nur noch eine Fundstelle an Position 1.
Die Ergebnisse stimmen mit StrPosEx('77', '777', Positions) überein.

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string; Estimated: Integer = 0): TIntegerDynArray;

  function Search(const SearchFor, SearchIn: string; var Index: Integer): Boolean; inline;
  begin
    Index := Pos(SearchFor, SearchIn, Index);
    Result := (Index > 0);
  end;

begin
  SetLength(Result, Estimated);
  var Count: Integer := 0;
  var Index: Integer := 1;
  var SearchForLength := Length(SearchFor);
  while Search(SearchFor, SearchIn, Index) do
  begin
    Inc(Count);
    if Estimated < Count then
    begin
      Estimated := Count * 2;
      SetLength(Result, Estimated);
    end;
    Result[Count - 1] := Index;
    Inc(Index, SearchForLength);
  end;
  SetLength(Result, Count);
end;

[Amateurprofi]

Zitat von Blup:

Das anfängliche "SetLength()" bewirkt weniger als erwartet, dafür bingt "inline" deutlich mehr Zeitersparnis:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string; Estimated: Integer = 0): TIntegerDynArray;

  function Search(const SearchFor, SearchIn: string; var Index: Integer): Boolean; inline;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  SetLength(Result, Estimated);
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(SearchFor, SearchIn, Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Estimated < Count then
    begin
      Estimated := Count * 2;
      SetLength(Result, Estimated);
    end;
    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Code:

StrPosEx('7', sRandomString, Positions)
0:00:00.102

Result := MyStrPosEx('7', sRandomString, 0)
0:00:00.168

Result := MyStrPosEx('7', sRandomString, 10000000)
0:00:00.157

Sorry, aber ich kann die Ergebnisse Deiner Zeitmessungen nicht nachvollziehen.
Ich habe SRandomString auf eine Länge von 80 Mio gesetzt und mit Zufallszeichen im Bereich "0".."9" gefüllt.
In Deiner Funktion "Search" habe ich "Pos" durch "PosEx" (aus System.StrUtils) ersetzt, weil bei mir (Delphi XE2) "Pos" keinen Offset unterstützt.
Ergebnisse im Anhang.
Meine Test-Prozedur:

Delphi-Quellcode:

PROCEDURE TMain.Test;
resourcestring
   sFmt='F:%S, R:%D, T:%S ms';
var
  I,R1,R2,R3:Integer;
  T1,T2,T3:Int64;
  DT:TDateTime;
  S1,S2,SRandomString:String;
  Positions:TIntegerDynArray;
begin
   SetLength(SRandomString,80000000);
   for I:=1 to Length(SRandomString) do
      SRandomString[I]:=Char(Random(10)+Ord('0'));
   // Zeitmessung auf Basis TimeStampCounter
   //    StrPosEx
   T1:=TimeStamp;
   SetLength(Positions,8100000);
   R1:=StrPosEx('7',sRandomString,Positions);
   SetLength(Positions,R1);
   T1:=TimeStamp-T1;
   //    MyStrPosEx mit Esrimated=0
   Positions:=Nil;
   T2:=TimeStamp;
   Positions:=MyStrPosEx('7',sRandomString,0);
   R2:=Length(Positions);
   T2:=TimeStamp-T2;
   //    MyStrPosEx mit Esrimated=8100000
   Positions:=Nil;
   T3:=TimeStamp;
   Positions:=MyStrPosEx('7',sRandomString,8100000);
   R3:=Length(Positions);
   T3:=TimeStamp-T3;
   S1:='Zeitmessung auf Basis TimeStampCounter'#13+
       Format(sFmt,['StrPosEx',R1,TicksToStr(T1)])+#13+
       Format(sFmt,['MyStrPosEx 0',R2,TicksToStr(T2)])+#13+
       Format(sFmt,['MyStrPosEx 8100000',R3,TicksToStr(T3)]);
   // Zeitmessung auf Basis TDateTime
   //    StrPosEx
   DT:=Now;
   SetLength(Positions,8100000);
   R1:=StrPosEx('7',sRandomString,Positions);
   SetLength(Positions,R1);
   T1:=MilliSecondsBetween(DT,Now);
   //    MyStrPosEx mit Esrimated=0
   Positions:=Nil;
   DT:=Now;
   Positions:=MyStrPosEx('7',sRandomString,0);
   R2:=Length(Positions);
   T2:=MilliSecondsBetween(DT,Now);
   //    MyStrPosEx mit Esrimated=8100000
   Positions:=Nil;
   DT:=Now;
   Positions:=MyStrPosEx('7',sRandomString,8100000);
   R3:=Length(Positions);
   T3:=MilliSecondsBetween(DT,Now);
   S2:='Zeitmessung auf Basis TDateTime'#13+
       Format(sFmt,['StrPosEx',R1,IntToStr(T1)])+#13+
       Format(sFmt,['MyStrPosEx 0',R2,IntToStr(T2)])+#13+
       Format(sFmt,['MyStrPosEx 8100000',R3,IntToStr(T3)]);
  ShowMessage(S1+#13#13+S2);
end;

[Stevie]

Ich find das ja putzig, wenn Leute Messergebnisse auf höchstwahrscheinlich sehr unterschiedlicher Hardware und Delphi Versionen vergleichen, die mind 10 Jahre auseinander liegen.

[Blup]

Bei mir Delphi 12.
Der Zeitunterschied verschindet bei mir praktisch, wenn statt '7' nach "77" gesucht wird.
Da in beiden Fällen der gesamte String durchsucht wird, meine Vermutung:
Die vielen Aufrufe von Pos bremsen (sind ja nicht inline).
Die Suche selbst innerhalb von Pos scheint optimal (zumindest in Delphi 12).

Eigentlich wollte ich nur die Verwendung von SetLength demonstrieren, damit man die Anzahl der Ergebnisse nicht vorher raten muss.

[Amateurprofi]

Zitat von Stevie:

Ich find das ja putzig, wenn Leute Messergebnisse auf höchstwahrscheinlich sehr unterschiedlicher Hardware und Delphi Versionen vergleichen, die mind 10 Jahre auseinander liegen.

Du könntest Recht haben, wenn mir um die Zeiten selbst ginge.
Mir geht es aber um folgendes:
Meine "StrPosEx" ist, ich erwähnte es in #1, von "PosEx" aus "System.StrUtils" abgeleitet.
Der Teil, mit dem gesucht wird, ist im Prinzip identisch mit "PosEx".
Unterschied:
Bei der Prüfung, ob die aktuelle Position noch innerhalb des zu durchsuchenden Teil des Strings ist vergleicht "PosEx" mit einem Wert, der auf dem Stack liegt, bei meiner "StrPosEx" mit einem Register, was deutlich schneller ist.
Deshalb erstaunt es mich dass eine Funktion, die wiederholt "Pos" bzw "PosEx" aufruft, deutlich schneller sein soll.
Nun kenne ich die "Pos" aus Delphi 12 nicht, habe aber mal irgendwo gelesen, dass die Identisch ist mit "PosEx" aus Delphi XE2.
Aber selbst wenn das nicht so ist, habe ich Zweifel, dass das etwas Neues ist, das deutlich schneller arbeitet.
Vielleicht kann mal jemand den Code der "Pos" aus Delphi 12 posten.