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.

[Christian Seehase]

Moin Assarbad,

Zitat:

Zitat von Assarbad

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.

ähhh... eine iterative Routine hat doch aber keine Rekursionstiefe, alldieweil sie ja eben nicht rekursiv ist. ;-)

[Assarbad]

:oops: ... :lol:

Mein Fehler, sorry.

[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).

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

Damit hat sich dann auch erledigt, oder :wink:

[Assarbad]

Jupp ... ich ersetze gleich Iteration duch Rekursion ... war wie gesagt mein Fehler. Hätte mir ja nur den Code näher anschauen müssen ... irgendwie war bei mir noch so im Hinterkopf, es ginge um Dateisuche :-/

[stoxx]

Hallo zusammen,

also es war nach meiner Änderung im Quelltext doch nicht behoben.
Es lag letztendlich daran, dass ich die search Methode einfach so deklariert habe.
Jetzt habe ich sie als Methode vom Object declariert, und der Stackoverflow kommt nicht mehr.
Jetzt kommt aber eine neue Exceptionn, dass ich zu wenig Arbeitsspeicher hätte.
Das ist aber Quark !

Denn wenn ich folgende Funktion starte, wird meine Exe 399 MB groß !!
ohne Probleme.
Aber bei meiner Berechnung nur 52 MB .. trotzdem kommt diese dämliche Fehlermeldung ?
Weiss nicht mehr weiter ...

Delphi-Quellcode:

procedure TForm5.Button58Click(Sender: TObject);
var ar : array of integer;
   i : longint;
begin

i := 100000000;
setlength(ar,i);

for i := 0 to length(ar) -1 do ar[i] := 5;
showmessage('warte');
end;

[Assarbad]

sizeof(Integer) = 4
4 * 100000000 ~~ 400MB

Außerdem würde man das nie so machen, sondern immer den Speicher direkt DWORD-weise überschreiben ... Zumindest wird deine Variante sehr langsam.

Vielleicht sagst du einfach nochmal, was du eigentlich vorhast. Hier sollte man wohl stärker optimieren :-/

[stoxx]

Zitat:

Zitat von Assarbad

sizeof(Integer) = 4
4 * 100000000 ~~ 400MB

Außerdem würde man das nie so machen, sondern immer den Speicher direkt DWORD-weise überschreiben ... Zumindest wird deine Variante sehr langsam.

Vielleicht sagst du einfach nochmal, was du eigentlich vorhast. Hier sollte man wohl stärker optimieren :-/

Hi .. dieses Array mit 100000000 Elementen war ja nur zum testen, ob es an der Größe des Arrays liegt und mein Speicher zu klei ist, und ob ein array am ende einer Procedure wieder automatisch freigegeben wird, ohne setlength(ar,0) zu setzen. Das wird gemacht


Wie meinst Du das mit DWORD Weise ?

Ich bekomm die Fehlermeldung nicht weg ..
es tritt immer die Fehlermeldung auf, dass ich zu wenig Arbeitsspeicher hätte .. versteh das nicht

[stoxx]

Hi,


habt vielen Dank für Eure Hilfe, das Problem hat sich jetzt erledigt,
hab von arrays auf TList umgestellt.
Da funktioniert das wunderbar und geht auch viel viel schneller .. und die Daten sind auch viel viel kleiner alles.
(wenn man in Tlist list.insert(i) benutzt und somit nur pointer umkopiert, geht das schneller als wenn man grosse Datenstrukturen in einem Array umkopieren muss)
Irgendwie muss Delphi arrays mehrfach anlegen (bei procedure Übergaben oder was weiss ich)

ist jedenfalls irgendwie nicht normal ...
aber egal ..