Stack Overflow trotz iterativen Algorithmus

[stoxx]

Hi zusammen,

ich kapier das nicht, und mein Kopf raucht gerade.
Ich habe keine rekursiven Algorithmen .. alles iterativ.
Trotzdem kommt bei meinen Berechnungen ein Stack Overflow.
Wie ist das denn nun mit dem Stack ? ..
Auf was sollte ich achten, damit mein Algorithmus trotzdem läuft ?

[Chewie]

Vielleicht reservierst du in jedem Iterationsschritt Stack-Speicher, den du nicht wieder freigibst. Poste doch mal den Code.

[stoxx]

Zitat:

Zitat von Chewie

Vielleicht reservierst du in jedem Iterationsschritt Stack-Speicher, den du nicht wieder freigibst. Poste doch mal den Code.

eigentlich nicht.
Wie reserviert man Stack Speicher ?
Ich dachte bisher immer, dass wenn man eine variable in einer Funktion oder prodedure definiert, dass diese nach dem Aufruf dieser Procedure wieder freigegeben wird.
Der Code ist eigentlich nicht weiter kompliziert, es werden nur in einem Array elemente einsortiert.
Das Array wird immer sortiert gehalten ...

Delphi-Quellcode:

<pre>
function search1 (was : intx ; wo : array of TDatensatz; var position : longint) : boolean;
       var mi,le,ri : LongInt;

       begin
           le := 0;
           ri := High(wo);
           repeat
               mi := (le + ri) div 2;
               If was < wo[mi].key Then ri := mi - 1 Else le := mi + 1;
           Until (wo[mi].key = was) Or (le > ri);
           if wo[mi].key = was then
             begin
               search1 := true;
               position := mi;
             end else
             begin
               search1 := false;
               if ri = -1 then position := 0 else
                begin
                 while (  wo[mi].key < was ) do inc(mi);
                 position := mi;
                end;

             end;
       End;  // von search1

///////////////////////////////////////////////////////////////////////




procedure TStatistikFeld.increin(TD : TDatensatz);
var i : longint;
    position : longint;
    l : longint;



begin


if  search1(td.key,afeld, position) then
 begin
    inc(  afeld [position].anzahl  );
 end else // von gefunden
 begin

   l := length(afeld);
   l := l +1;
   setlength(afeld,  l  );


   for i := l-1 downto position + 1 do
   afeld[i] := afeld[i-1];

   td.anzahl := 1;
   afeld[position] := TD;


 end; // von nicht gefunden

end; // von increin
</pre>

[edit=Christian Seehase] Delphi-Tags gesetzt. Bitte künftig selber machen. Danke. Mfg, Christian Seehase[/edit]

[Chewie]

Setz das bitte mal in Delphi-Tags, ich hab keine Lust mir das so anzusehen.
Stackspeicher reservierst du durch das Deklarieren einer lokalen Variable, durch das manuelle Zuweisen oder durch das Instantiieren einer Klasse.

[Assarbad]

Für jede neue "Instanz" einer rekursiven Routine werden die lokalen Variablen neu auf dem Stack plaziert (denn jede hat ja ihre privaten lokalen Variablen).

Der Titel sollte also eher heißen: "Stack Overflow wegen rekursivem Algorithmus" ... denn das ist eine allgemeine Gefahr bei Rekursionen!

SORRY, HATTE ITERATION UND REKURSION DURCHEINANDER GEHAUEN. Vergiß meinen Beitrag einfach ;)

[Chewie]

Zitat:

Zitat von Assarbad

Für jede neue "Instanz" einer iterativen Routine werden die lokalen Variablen neu auf dem Stack plaziert (denn jede hat ja ihre privaten lokalen Variablen).

Was genau meinst du hier mit Instanz? Wenn ein Prozeduraufruf nach dem andern folgt, wird doch der reservierte Speicher nach dem Abarbeiten jeder Prozedur freigegeben. Oder etwa nicht?

[Christian Seehase]

Moin stoxx,

kleiner Tip am Rande:
Verwende für den Rückgabewert der Funktion statt des Funktionsnamens lieber die, bei jeder Funktion intern vorhandene, Variable Result.
Die ist flexibler zu handhaben (kann z.B. in der Funktion auch auf der rechten Seite einer Zuweisung stehen, oder als Parameter verwendet werden).

[stoxx]

Hallo,

die eine Ursache habe ich gefunden.
Lag an einer Procedure vor dem Auruf.

ich hatte eigentlich getestet, ob ein array nach einer procedure Beendigung wieder freigegeben wird ohne dass man es auf setlength(ar,0); setzen muss, und das ging.
Ich weise einer property dieses array zu, da funktioniert das wahrscheinlich nicht mehr.
Ich habe das array jetzt global gemacht, da gehts.

Jetzt hab ich aber 5 Min später (in der Berechnung - dauert so lange)
gleich wieder ein neues Problem.

diesmal kommt die Meldung "Zu wenig Arbeitsspeicher"
Obwohl noch Massen Platz ist ..
Meine Exe ist 52 MB im Speicher groß.
Habe 1 GB Hauptspeicher ..
komisch ?!? *grrr*

[Assarbad]

Zitat:

Zitat von Chewie

Was genau meinst du hier mit Instanz? Wenn ein Prozeduraufruf nach dem andern folgt, wird doch der reservierte Speicher nach dem Abarbeiten jeder Prozedur freigegeben. Oder etwa nicht?

Schwer zu erklären ... Instanz soll heißen "Kontext eines Aufrufes einer Routine ..." genauer kann ich es nicht ausdrücken.
Exakt Chewie ... der Speicher wird freigegeben ... ABER ERST nachdem alle aufgerufenen "Instanzen" der Routine beendet sind. Je nach Rekursionstiefe wird also die Menge und größe der lokalen Variablen (und natürlich auch der allozierten Heapbereiche auf den Speicherbedarf Einfuß nehmen.

[Chewie]

Genau, je nach Rekursiontiefe. Aber es geht hier um eine Iteration, also Rekursionstiefe = 1 = 1 "Instanz" gleichzeitig.