Dynamische Arrays "verketten"

[Dennis07]

Hallo, ich bins mal wieder.
Ich will folgende ein typisiertes dynamisches array von Integer-Werten an ein anderes anhängen.
Allerdings ist meine Funktion rekursiv. ("TIntegerArray" ist deklariert als "array of Integer")

Delphi-Quellcode:

//Diese Funktion soll mir alle Positionen eines SubStrings in einem String zurückliefern.
//Bitte nicht fragen, wieso ich nicht Gebrauch vom "Offset"-Parameter der
//"Pos(...)"-Funktion mache, ich brauche Abwärtskompatibilität bis einschl. D7.

function MultiPos(const SubStr, Str: String; Offset: Integer = 1): TIntegerArray;
var
  Temp: PChar;
  Position: Integer;
  Further: TIntegerArray;
begin
  SetLength(Result,0);
  if (Offset < 1) or (Offset > (Length(Str) - Length(SubStr))) then
  begin
    Exit;
  end;
  Temp := @Str[OffSet];
  Position := Pos(SubStr,String(Temp));
  if Position <> 0 then
  begin
    SetLength(Result,1);
    Result[0] := Position + Offset - 1;
    Inc(Temp,Position + Length(SubStr) - 1);
    Further := MultiPos(SubStr,Str,Offset + Position + Length(SubStr) - 1);
    if Length(Further) <> 0 then
    begin
      SetLength(Result,1 + Length(Further));
      Move(Further[0],Result[1],SizeOf(Further){Length(Further) - 1});
    end;
  end;
end;

Wenn ich die Funktion jetzt teste, gibt der mir für die ersten beiden Positionen richtige Werte aus. Für alle anderen jedoch erhalte ich nur noch Nullen. Ich vermute, dass es an relativer Adressierung von arrays liegen könnte, die durch "System.Move(...)" die folgenden Kettenglieder unbrauchbar macht, bin mir aber nicht ganz sicher. Und noch weniger weiß ich, wie ich es beheben sollte.

[Bjoerk]

Was soll hier die Verketterei? Delphi 7 hat auch schon eine PosEx (wenn ich mich recht erinnere). Ansonsten kann man sich schnell eine selbst schreiben bzw. hier im Forum.

Ungetestet:

Delphi-Quellcode:

procedure MultiPos(const SubStr, S: String;
  const Offset: Integer; var Positions: TIntegerArray);
var
  I, N: integer;
begin
  N := 0;
  SetLength(Positions, N);
  I := PosEx(SubStr, S, Offset);
  while I > 0 do
  begin
    Inc(N);
    SetLength(Positions, N);
    Positions[N - 1] := I;
    I := PosEx(SubStr, S, I + 1);
  end;
end;

[Dennis07]

Naja, darum geht es aber nicht.
Wenn du dir mal die Pos()-Funktion anschaust, wirst du sehen, dass diese in Maschinencode geschrieben ist und somit besonders bei längeren Texten (>50K Zeichen) auch um einiges schneller sein dürfte.
Außerdem will ich ja nicht das gesamte array nochmal durchlaufen, das wäre ja Zeit-und Ressourcenverschwendung.

Weiß jemand, wie man das mit Move (oder sonst wie, aber im selben Prinzip) hinbekommen könnte?

PS: Und außerdem sollen die Werte der Reihe nach sortiert sein (in-order), und ein nochmaliges Durchlaufen wäre vollkommen undenkbar.

[jaenicke]

Die Umwandlungen von PChar zu string, die Vergrößerung des Array usw. machen das ganze deutlich langsamer. So kannst du das kaum optimieren.
Schnell geht das nur, wenn du z.B. selbst mit Boyer Moore oder einem anderen Algorithmus suchst. Dann kannst du auch direkt auf den Pointern arbeiten. Wirklich einen Vorteil hat Boyer Moore aber nur bei längeren Texten.
Beispiele findest du viele, z.B.:
http://www.entwickler-ecke.de/viewto...=502137#502137
http://www.delphipraxis.net/175187-b...gorithmus.html
...

Und wenn man Assembler benutzt, gibt es auch noch Befehle wie repne scasb (bzw. repne scasw für Unicode), mit der man Strings schnell scannen kann.

[Dejan Vu]

Der Grundfehler ist der rekursive Aufruf. Hier hättest Du einfach eine Iteration durchführen können, da es sich um eine Tailrecursion handelt. Aber deine Frage war ja, wie man dynamische Arrays verketten kann bzw. wie man das Funktionsergebnis deiner Funktion an das Ergebnis des Aufrufers hängen kann.

http://www.delphipraxis.net/105562-f...entierung.html

Delphi 7 PosEx hat einen Bug, daher vielleicht doch o.g. Variante nehmen und zusammen mit Bjoerk's Routine hast Du dein ziemlich optimales Ergebnis.

[Dennis07]

Okay. Vielen Dank, schaue ich mir heute Abend mal an.
Also nur um es jetzt zu verstehen, war meine Annahme oben richtig oder was war der genaue Grund, weshalb das nicht funktioniert hat?

[jaenicke]

Further ist ein dynamisches Array, also ist die Variable Further ein Pointer auf dieses dynamische Array. Dementsprechend ist SizeOf(Further) immer 4 bzw. bei 64-Bit 8. Du bewegst also gar nicht das ganze Array. Das hätte dir im Debugger eigentlich auffallen müssen, wenn du das Move dort einzeln ausführst.

Was du möchtest ist aber das ganze Array kopieren und das ist in Byte die Länge des Arrays mal der Größe eines Elements:
SizeOf(Further[0]) * Length(Further)

[Dennis07]

Ah.. Danke! Naja, zwischen dem was man "hätte wissen können" und dem, worauf man dann am Ende kommt, sind manchmal Welten. Ich hatte den Fehler ganz woanders vermutet und deshalb gar nicht gedacht, dass es daran liegen könnte.

[BadenPower]

Um auf die eigentliche Frage zu antworten, habe ich Dir den Code berichtigt.

Delphi-Quellcode:

function MultiPos(const SubStr, Str: String; Offset: Integer = 1): TIntegerArray;
var
  Temp: PChar;
  Position: Integer;
  Further: TIntegerArray;
begin
  SetLength(Result,0);
  if (Offset < 1) or (Offset > (Length(Str) - Length(SubStr))) then
  begin
    Exit;
  end;
  Temp := @Str[OffSet];
  Position := Pos(SubStr,String(Temp));
  if Position <> 0 then
  begin
    SetLength(Result,1);
    Result[0] := Position + Offset - 1;
    Inc(Temp,Position + Length(SubStr) - 1);
    Further := MultiPos(SubStr,Str,Offset + Position + Length(SubStr) - 1);
    if Length(Further) <> 0 then
    begin
      SetLength(Result,1 + Length(Further));
      Move(Further[0],Result[1],Length(Further)*SizeOf(Further[0])); // hier änderen
    end;
  end;
end;

EDIT:
Funktioniert neuerdings die "rote Box" nicht mehr, wenn zwichendurch bereits Antworten gepostet wurden?

[Dennis07]

-GEÄNDERT-

Okay, habe deine Post nicht gesehen. Funktioniert bei mir doch, hatte nur noch irgendwo nen fehler gehabt.
Danke euch allen, werde mich mal in die fastpos-lib einlesen.

MfG