Alternative zu PosEx

[Maekkelrajter]

Zitat von Sinspin:

Ich habe auch schon die Erfahrung gemacht das FPC/Delphi schnelleren Code erzeugt hat als selbst geschriebener Assembler.

Das ging mir ähnlich. Aus 'maschinen-nahem' Pascal mit Delphi 4 compilierter Code war schneller als meine selbstgeschiebenen Assembler-Routinen, die unter TP6 bzw. BP7 noch für einen ordentlichen Performance-Schub gesorgt hatten.

Zitat von Stevie:

Einzig dein neuer 4. Parameter, um den Suchbereich zu limitieren, ist interessant und ggf eine Überlegung wert, diesen in der RTL auch unterzubringen.
Sollte sogar ziemlich einfach zu implementieren sein, da dieser der Länge des zu durchsuchenden Strings entspricht, die intern sowieso ermittelt wird.

Hier hatte ich mich vor ein paar Jahren schon mit dem Thema befasst und eine Variante von Pos() mit 4 Parametern entwickelt.

Gruß LP

[Stevie]

Ich hab mir mal System._UStrPos in Delphi 12 angeschaut und wenn ich nicht komplett auf dem Holzweg bin, dann ist die Erweiterung mit einigen wenigen Anpassungen erledigt. Defaultwert von Count ist MaxInt

Hier mal der relevante Ausschnitt

Delphi-Quellcode:

begin
-  if (Str = nil) or (SubStr = nil) or (Offset < 1) then
+  if (Str = nil) or (SubStr = nil) or (Offset < 1) or (Count < 1) then
    goto Exit0;

  // fast access to length - did the nil check already
  lenSub := PInteger(SubStr)[-1];
  Dec(lenSub);
  len := PInteger(Str)[-1];
+  Dec(Offset);
+  Cardinal(Count) := Cardinal(Count) + Cardinal(Offset);
+  if Cardinal(len) > Cardinal(Count) then len := Count;
-  if (len < lenSub + Offset) then
+  if (len <= lenSub + Offset) then
    goto Exit0;

  Stop := @Str[len];
  Str := @Str[lenSub];
  SubStr := @SubStr[lenSub];
  Start := Str;
-  Str := @Str[Offset + 3];
+  Str := @Str[Offset + 4];

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