rekursive Programmierung - record als parameter

[mcmichael]

Hallo Experten,

ich möchte eine rekursive Funktion programmieren und als Parameter den augenblicklichen Zustand
einer "Keksverteilung" übergeben.

Delphi-Quellcode:

function verteil_kekse(plan:plan_rec):boolean;

plan_rec ist so definiert:

Delphi-Quellcode:

  plan_rec=record
    dose:Array [0..maxQ] of integer;
    keks:Array [1..maxMA,0..maxQ] of byte;
  end;

Ich ging davon aus, daß wenn die Funktion sich noch einmal aufruft

Delphi-Quellcode:

i:=0;
  repeat
    inc(i);
    if (i<maxMA) and (score[i,2]>0) then
      begin
      if i>1 then plan.keks[score[i-1,1],kp]:=0; //vorherigen zurücksetzen
      plan.keks[score[i,1],kp]:=1; //keks aktivieren
      Form1.ListBox1.items.add('ma '+inttostr(i));
      end;
  until (i>maxMA) or (score[i,2]=0) or verteil_kekse(plan);

das record auf dem Stack noch einmal neu angelegt wird. Wirds aber nicht.
Es wird immer frisch und leer übergeben.

Dabei stellt sich mir auch eine grundsätzliche Frage:
Wie organisiere ich beim verzweigen durch alle Möglichkeiten die augenblickliche
Verteilung am besten (optimale Geschwindigkeit und Speichernutzung)

Ideen dazu?

[Gargoyl]

Hm, also entweder musst du zu Beginn deiner Funktion den Inhalt von plan in eine lokale Variable kopieren und mit dieser lokalen Variable in der Funktion weiterarbeiten, oder du benutzt Call by reference und änderst deinen Funktionsdeklaration wie folgt ab:

Delphi-Quellcode:

function verteil_kekse(var plan:plan_rec):boolean;

Das kommt halt drauf an was du genau damit machen willst. Im letzteren Fall würde 'plan' nach dem Funktionsaufruf einen anderen Wert enthalten als vorher. Falls du nicht willst musst du eben den ersten Weg versuchen und den Inhalt von 'plan' in eine lokale variable zu kopieren und mit diesere Variable weiterarbeiten.

Nur mal so ins blaue getippt.

Gargoyl

[himitsu]

also, bei mir legt Delphi, bei soeiner Funktionsdefinition,

Delphi-Quellcode:

function verteil_kekse(plan:plan_rec):boolean;

beim Funktionsaufruf eine Kopie der Variable (hier plan) an.

und diese sieht inhaltlich genauso aus, wie die der Funktion übergebene Variable aus.

bist du sicher, daß vorher was in die zu übergebende Variable ein eingetragen wurde?

Zitat:

Ich ging davon aus, daß wenn die Funktion sich noch einmal aufruft das record auf dem Stack noch einmal neu angelegt wird. Wirds aber nicht. Es wird immer frisch und leer übergeben.

also dem ist auch so.


aber dennoch ....
- welche Delphiversion nutzt du?
- wie groß sind maxQ und maxMA?
- und die Array's in plan_rec sind wirklich statische Arrays?
(also das in den []-Klammern ist nicht nur zur Veranschaulichung des Aufbaues nur im Post so einhalten)

Delphi-Quellcode:

(optimale Geschwindigkeit und Speichernutzung)

optimal ist es nicht gerade, wenn ein "größeres" Array/Record bei jedem Funktionsaufruf angelegt/kopiert werden muß

ich sag's mal so ... in meinem himXML hatte ich die Performance einer oft genutzten Prozedur nur dadurch um über 900% raufgesetzt, indem ich in der Funktion einen lokalen Record mit 1025 Strings und einigem anderem hatte ... oder anders gesagt, nur durch Auslagerung des Arrays sank die Laufzeit der Prozedur auf 10% der vorherigen Zeit.

und nur weil Delphi beim Aufruf de Funktion eine schöne Schleife aus unzähligen "PUSH 0" durchführte, um das Array zu initialisieren.

Tipp: falls plan_rec etwas größer ist:
leg ein "globlales" Array[..] of plan_rec an, übergib der Funktion verteil_kekse nur den Index des zugehörigen plan_rec's und übernimm das kopieren selber

Delphi-Quellcode:

type plan_array = array[0..{100}] of plan_rec;

function verteil_kekse(var plan:plan_array; index:integer):boolean;
begin

  if index >= high(plan) then {fehler};
  MoveMemory(@plan[index + 1], @plan[index], sizeof(plan_rec));
  verteil_kekse(index + 1);

end;

// start
verteil_kekse(plan, 0);

[edit] ups, sizeof(plan) ist natürlich falsch ... sizeof(plan_rec) müßte es sein

[Gargoyl]

Vielleicht solltest du auch mal deine komplette Funktion 'verteil_kekse' zu posten, vielleicht stellst du ja noch was anderes mit der Variable 'plan' an was dein Problem verursacht.

[mcmichael]

Vielen Dank erstmal vorweg - im besonderen himitsu. Da habe ich viele Ansätze gefunden.

Zitat:

Tipp: falls plan_rec etwas größer ist:
leg ein "globlales" Array[..] of plan_rec an

Das Array wird wohl 50 (maxMA) * 96 (maxQ) + 384 = 5184 byte groß werden und in der Tiefe sollten
maximal 4800 Schritte erreicht werden. Mit 30MB dürfte ich also hinkommen.
(Wie schön, daß die alten Schranken aus Delphi 1 Zeiten nicht mehr existieren)

Was die Übergabe eines frisch angelegten Array angeht - da habe ich einen Fehler in meinem Code
gefunden - das Array wird nun richtig übergeben. Jetzt muß ich an den Regeln der Keksverteilung
etwas feilen. maxQ stellt übrigens 96 Viertelstunden dar (einen Tag) und maxMA die maximale
Anzahl von Keksempfängern die über den Tag verteilt nach bestimmten Regeln Kekse bekommen.
Wer errät, was letztlich real dahintersteckt, bekommt einen Keks... :wink:

Mit der Strategie wie die Kekse verteilt werden wird das ganze wohl auch stehen und fallen.
Wenn die Berechnung sehr schnell ist würde ich auch überlegen mehr als eine Lösung zu ermitteln,
aber momentan suche ich erstmal nur nach einer Lösung und breche dann ab. Deshalb ist
Performance ziemlich wichtig.

Danke an alle,
McMichael

[himitsu]

[info]
hatte oben einen kleinen Fehler:
die eine Zeile müßte natürlich so sein (plan_rec statt plan, da ja ein Record davon kopiert werden soll)

Delphi-Quellcode:

MoveMemory(@plan[index + 1], @plan[index], sizeof(plan_rec));

[/info]

[mcmichael]

Zitat:

MoveMemory(@plan[index + 1], @plan[index], sizeof(plan_rec));

Danke, es ging noch etwas einfacher:

Delphi-Quellcode:

Matrix[index+1]:=Matrix[index]

Delphi führt den Move-Befehl dann wohl selbst durch.
(sollte ich mir vielleich mal ansehen.. wie geht das?)

[himitsu]

Zitat:

Zitat von mcmichael

Delphi-Quellcode:

Matrix[index+1]:=Matrix[index];

Delphi führt den Move-Befehl dann wohl selbst durch.
(sollte ich mir vielleich mal ansehen.. wie geht das?)

joar, ist wohl auch besser so ... vorallen wenn mal Strings und Co. im Array drin sind :angel:

[Hawkeye219]

Hallo,

Zitat:

Zitat von mcmichael

Das Array wird wohl 50 (maxMA) * 96 (maxQ) + 384 = 5184 byte groß werden und in der Tiefe sollten maximal 4800 Schritte erreicht werden. Mit 30MB dürfte ich also hinkommen.
(Wie schön, daß die alten Schranken aus Delphi 1 Zeiten nicht mehr existieren)

Du solltest aber beachten, dass der Defaultwert für die maximale Stackgröße bei 1 MByte liegt. Bei einer geplanten Rekursionstiefe von bis zu 4800 stehen somit pro Aufruf nur wenig mehr als 200 Byte zur Verfügung. Die Übergabe einer etwas größeren Datenstruktur ohne CONST oder VAR könnte deshalb schon zu einem Stacküberlauf führen.

Wenn du bei dem Werteparameter bleiben möchtest, dann wirst du in den Linkeroptionen die Stackgröße anpassen müssen. Allerdings lässt sich mit dem maximal möglichen Wert von 16 MByte und dem gegebenen Array die gewünschte Rekursionstiefe von 4800 nicht erreichen.

Gruß Hawkeye