Alternative zu PosEx

[himitsu]

Zitat:

wie

Als VAR-Parameter und drinnen ein SetLength.


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.

[Amateurprofi]

Zitat von himitsu:

Zitat:

wie

Als VAR-Parameter und drinnen ein SetLength.


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.

Hast Du auch einen Vorschlag wie man das in einer Assembler-Routine realisieren kann (32BitAsm und 64BitAsm)?
Ich hatte das vor langer Zeit mal versucht.
Weiß nicht mehr woran es scheiterte, hab aber die unangenehme Erinnerung, dass ich es nicht hingekriegt habe, was aber nicht wirklich der Grund für meine Vorgehensweise war.
Ich hab die Funktion ja im Zusammenhang mit Mersenne-Primzahlen und den daraus abgeleiteten Perfekten Zahlen geschrieben.
Die zZ längste Zahl "(2^136279841-1) * 2^(136279841-1)" hat 82,048,640 Ziffern.
Rein theoretisch müsste ich, um auf der sicheren Seite zu liegen, das Array auf eine Länge von 82,048,640 setzen = 330MB.
Es ist aber so, dass mein Programm, dann wenn eine Zahl geladen wird, zählt, welche Ziffer wie oft vorkommt.
Am häufigsten, bei der og Zahl die 7 (8,202,366 Mal).
Also muss ich das Array "nur" auf eine Länge von 8,202,366 setzen = 33MB.
In einer allgemeingültigen Funktion ist eine Abschätzung, wie lang das Array sein muss eher nicht möglich.
Wenn ich wiederholte Längenänderungen vermeiden will müsste ich also für eine Suche nach einzelnen Zeichen die Länge auf die Länge des zu durchsuchenden Strings setzen, ZZ 330MB, bei den nächsten Mersenne-Primzahlen sicherlich > 1GB, und dann wird es problematisch.
Unabhängig davon wüsste ich aber gern, wie man ein SetLength in Assembler realisieren kann.

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

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]