Theorie: Rekursive Funktion Abbrechen und Fortsetzen

[Meflin]

Zitat:

Zitat von alzaimar

Ist der Algorithmus geheim? Vielleicht können wir ihn ja iterativ umformulieren?

nein: http://www.delphipraxis.net/internal...ct.php?t=62161

Delphi-Quellcode:

procedure BruteForceFunc(const init, str: string);
  var i: integer;
      npw: string;
  begin
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then BruteForceFunc (npw, str);
    end;
  end;

ist das herzstück

[alzaimar]

Na, super, fast eine Endrekursion.
Einfach einen Stack, bestehend aus 2 Strings erzeugen (Ich hab das als TStringlist gemacht, nicht perfekt, reicht aber).

Am Anfang schiebst Du 'init' und 'str' auf rauf. Anstatt rekursiv aufzurufen, schiebst Du die Parameter, mit der Du dich sonst rekursiv aufrufen würdest, einfach auf den Stack. Ich gehe mal davon aus, das Du das Ergebnis des rekursiven Aufrufes in der For-Schleife nicht benötigst. Ich sehe auch einige globale Variablen, aber das checkst Du bestimmt selbst.

Delphi-Quellcode:

procedure IterativeBruteForceFunc(const init, str: string);
var i: integer;
    npw: string;
    StackedInit, StackedStr : TStringlist;

begin
  StackedInit := TStringList.Create;
  StackedStr := TStringlist.Create;
  StackedInit.Add (init);
  StackedStr.Add (Str);
  While StackedInit.Count > 0 do begin
(****************************************)
    Init := StackedInit [StackedInit.Count -1];
    Str := StackedStr[StackedStr.count - 1];
    StackedInit.Delete (StackedInit.Count - 1);
    StackedStr.Delete (StackedStr.Count - 1);
(****************************************)
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then Begin
(*****************************************)
        StackedInit.Add (Npw); //      BruteForceFunc (npw, str);
        StackedStr.Add (Str);  
(*****************************************)
      end;
    end;
  End;
End;

[dimo]

PS: Habe gerade gesehen, dass diesen Vorschlag schon existiert.

Der Prozeduraufruf wird mit Stack implementiert.
Dies kannst Du auch selber nachmachen - dafür steht die Klasse TStack zur Verfügung. Natürlich ist normalerweise eine rekursive Funktion kürzer und einfacher zu programieren.
Ein schematischer Beispiel, der alle Dateien rekursiv (d.h. auch in Unterverzeichnisse) anzeigt:

Delphi-Quellcode:

procedure recurse_dirs(path : string);
var   sr : TSearchRec;
begin
   if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
      repeat
         if (sr.Attr and faDirectory) = faDirectory then begin
            if (sr.Name <> '.') and (sr.Name<>'..') then
               recurse_dirs(path+PathDelim+sr.Name);
         end else begin
            showmessage(path+PathDelim+sr.Name);
         end;
      until FindNext(sr) <> 0;
      FindClose(sr);
   end;
end;

Kann folgendermassen ohne Rekursion geändert werden:

Delphi-Quellcode:

procedure iterate_dirs(startpath : string);
var   sr : TSearchRec;
   stack : TStack;
   path : PAnsiChar;
   subdir : PAnsiChar;
begin
   stack:= TStack.Create;

   path:= StrAlloc(length(startpath)+1);
   StrPCopy(path, startpath);
   stack.Push(path);

   while stack.Count>0 do begin
      path:= stack.pop;
      if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
         repeat
            if ((sr.Attr and faDirectory) = faDirectory) then begin
               if (sr.Name <> '.') and (sr.Name<>'..') then begin
                  subdir:= StrAlloc(Length(path+PathDelim+sr.Name)+1);
                  StrPCopy(subdir, (path+PathDelim+sr.Name));
                  stack.push(subdir);
               end;
            end else begin
               showmessage(path+PathDelim+sr.Name);
            end;
         until FindNext(sr) <> 0;
         FindClose(sr);
      end;
      StrDispose(path);
   end;
   stack.Free;
end;

Natürlich ist die Ausgabereihenfolge unterschiedlich, die ist aber bei vielen Aufgaben egal. Hört sich an wie Breiten vs. Tiefensuche ;) Ist es auch dasselbe in dem Fall.

Zustand speichern in diesem Fall wäre einfach den Stack speichern... Das ist das Gute an dieser Methode.
Grüße,
Dimo