Wie ist das mit der Rekursion und dem Stack?

[choose]

Zitat:

Zitat von neolithos

Delphi-Quellcode:

BinSearch(apData : PIntegerArray; aiLo, aiHi : Integer)

Die Arbeit mit Pointern ist eine häufige Fehlerursache, wenn man nicht genau weiß, was man macht. Sollen die Daten in der aufrufenden Routine verändert werden, empfiehlt sich stattdessen das Attribut var, sollen die Daten nie verändert werden stattdessen const. Technisch gesehen, entspricht dies vollständig Deiner Lösung, neolithos, allerdings bewegst Du Dich in der "sicheren Pascal-Umgebung", typenstrenge, (ohne Tricks) kein nil möglich, bei const (ohne Tricks) auch wirklich keine Veränderungen möglich, ...

Zitat:

Zitat von neolithos

Wie oft schachtelt sich die Rekursion, brauch ich dann überhaupt den Aufwand treiben.

Bzw verwende wann immer möglich, auch um sprechenderen Code zu schreiben, die Schlüsseworte const, var und out.

Zitat:

Zitat von neolithos

Trotzdem noch auf Eins am Ende geschafft!

Glück gehabt, es gibt mit Sicherheit auch nachtragendere Menschen ;)

[neolithos]

@choose

Danke für die Wertvollen Ergänzungen! (Mit den floats hab ich selbst noch nicht gewußt)
Mit den var, const und out ist ein guter Hinweis. Stimm ich generell zu, dass das sicherere ist und auf des selbe wie ich Def. habe hinaus läuft. Dummerweise bin ich noch DOS-Pascal belasstet und da hat sich so manches eingeschlichen was man nur schwehr rausgriegt.

[NeoXpert]

ich weiß kommt en bisserl spät.. aber wir durften im LK die Türme von Babylon, das Springerporblem (übern schabrett mit nem springer, jedes feld nur einmal berühren) und den quicksort iterativ schreiben.... gar nicht lustig und da ichs net verstanden habe, bzw. mir kopiert habe kann ichs euch leider net geben :( aber sagen wir es sind ein paar mehr zeilen ^^

[Matze]

OK, ich danke euch allen! :)
Jetzt müsst ich's kappiert haben ;)

[negaH]

Zitat:

Sofern möglich, werden die ersten drei Parameter über die Register EAX, EDX und ECX, also ohne Verwendung des Stacks übergeben. Zu beachten ist an dieser Stelle, dass der zuvor erwähnte "unsichtbare Parameter" ebenfalls zu diesen drei zu zählen ist, also bei Methoden im besten Fall nur die ersten beiden Parameter auf diese Weise übergeben werden können.

Das ist insofern richtig, für den realen Stackverbrauch ist dies aber leider NICHT relevant. Denn selbst wenn die Parameter über Register und NICHT dem Stack übergeben werden, so sind die meisten rekursiven Funktionen denoch komplexer Natur. Somit werden diese Register-Parameter nach dem Eintritt in die rekursive Funktion wiederum auf dem Stack gesichert, oder aber in den Registern ESI,EDI,EBX gesichert NACHDEM jeweils EDI,ESI,EBX auf dem Stack gesichert wurden. Somit verbraucht eine rekursive Funktion die EAX,EDX,ECX als Register-Parameter benutzt denoch 3 Integer Stack Variablen intern. Es macht also fast keinen Unterschied im Stackverbrauch.

Zitat:

Und wenn ich mich nicht täusche, braucht Quicksort ca. n*log(n) rekursive Schritte (log = 2er-Logarithmus)

Dies ist richtig für die durchschnittliche Anzahl an rekursiven Aufrufen dergleichen QuickSort Funktion, definiert aber NICHT die maximale Rekursionstiefe. Die maximale Verschachtelungsanzahl beträgt dann nämlich nur Ln2(n) = Log(N) wenn Log() der 2er Logarithmus ist. D.h. bei N = 1024 wird die max. Tiefe nur 10 betragen, da 2^10 = 1024. Nur diese Rekursionstiefe bestimmt den Stackverbrauch und würde bei N = 2^32 eben nur maximal 32 sein. Mit N=2^32 stösst man aber schon an die Speichergrenzen heutiger Rechner. QuickSort() ist somit in Punkto Stackverbrauch absolut unkritisch.

Auf dem Stack speichern die Programme ihre Temporären Lokalen Variablen was somit vergleichbar zum normalen Borland Speicher Manager funktioniert. Der Stack arbeitet also für diese lokalen Variablen wie ein sehr schneller Speichermanager. Den Unterschied zwischen solchen Lokalen Variablen und Borland Speichermanager Variablen bezeichnet man auch öffters als den Unterschied zwischen Dynamischen und Statischen Variablen.

Desweiteren wird ganz transparent der Programmfluß der Anwendung suf dem Stack gespeichert. D.h. bei jedem Funktionsaufruf wird der Programpointer an dem das Programm NACH der aufgerufenen Funktion fortsetzen soll auf dem Stack gespeichert. Ausgehend vom Stack könnte man also in Erfahrung bringen auf welchem WEG die derzeitige Funktion aufgerufen wurde. Zu dieser "Programmflußsteuerung" des Stack kann man auch die geschützten Codebereiche zählen. Dies sind also alle lokalen Variablen die das Programm benötigt um die try finally end. und try except end. Konstrukte umzusetzen.

Gruß Hagen