Alternative zu PosEx

[Blup]

Zitat von himitsu:

Per se ist OUT hier falsch, jedenfalls in Bezug auf Managed-Types, wie z.B. dynamische Arrays.
Zum Glück macht Delphi hier heimlich, und ohne was zu sagen, ein VAR daraus.

Bei OUT ist es möglich auch die Referenz zu ändern, was hier "eigentlich" zu einem Speicherleck führen würde, wenn vor dem Aufruf das Array einen Inhalt hätte.

Da Managed-Types immer initialisisert sind, wäre OUT nach deiner Auffassung für diese immer falsch.
OUT intern für Managed-Types als VAR zu behandeln macht Delphi schon richtig, beide übergeben einen Zeiger auf die Variable.

Was meiner Meinung nach fehlt ist eine Warnung auch für Managed-Types.
- VAR-Parameter: Warnung wenn vorher keine Zuweisung auf die Variable erfolgt (kann auch leer sein, aber automatische Initialisierung zählt nicht)
- OUT-Parameter: Warnung wenn vorher eine Zuweisung auf die Variable erfolgt, diese Variable aber nicht mehr vor dem Aufruf als OUT-Parameter ausgewertet wird.

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

Zitat von Amateurprofi:

Und wo ist da der Fehler?
"PaPa" wird in "PaPaPa" an Position 1 gefunden.
Dann wird geprüft, ob ab hinter der Fundstelle, also ab Position 1+Length("PaPa") der Text "PaPa" noch einmal gefunden wird.
Das ist nicht der Fall, also wird korrekt 1 zurückgegeben.

Das ist Ansichtssache. Bei einer Funktion die Sucht und Ersetzt wäre dies auch sicherlich richtig.
Bei einer Funktion die alle Fundstellen zurückgibt, erwarte ich alle, auch wenn die gefundenen Zeichenketten sich überschneiden.
Welche davon ignoriert werden, kann man beim Verarbeiten des Ergebnis der Suche entscheiden.

Zu "Bei einer Funktion die Sucht und Ersetzt wäre dies auch sicherlich richtig."
Ja, und meine Ansicht ist, dass eine Suche genau die Fundstellen finden soll, die im Zweifelsfall auch ersetzt würden.

Aber, wie du sagtest: Ist Ansichtssache.
Ich bin zum Beispiel der Ansicht, dass 2 * 2 = 5 ergeben sollte, wenn in 2024 der 31te eines Monats auf einen Montag fällt.

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