Autor Beitrag
JayAy
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Mi 07.04.10 16:30 
Hey Leute,

hier im Forum gibt es zwar viele Fragen, warum es in einem spezifischen Programm zum Stackoverflow kommt, jedoch hab ich ein anderes Problem:

In meinem Programm (Vergleich von Sortieralgorithmen) kommt es zwar auch zum Stackoverflow, allerdings erst, wenn ich ihn 100.000 Zahlen sortieren lasse oder noch einen vierten Algorithmus zum Vergleich mit reinschreibe, davor ist alles okay...

Wie gesagt: An Endlosschleifen und der gleichen liegt es nicht... scheinbar ist der Grenze bei manchen Dingen einfach begrenzt.

Meine Frage nun: Kennt ihr vielleicht irgendwelche Tricks oder Tipps, wie man aus dem begrenzten Speicher "ausbrechen" kann?

Vielen Dank!
Xion
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Mi 07.04.10 16:40 
Wenns bei dir um Sortierung geht und es entsteht ein Stack Overflow wohl bei etwas rekursivem.

Ist ja auch klar, stell dir mal vor du solltest das rekursiv dir alles merken ^^

Ich hatte da auch mal jemanden gefragt (finds nicht) aber der hat mir die geniale Technik gesagt, einfach die Anfragen in ein array zu packen. In dem Beispielcode gehts um einen Floodfill, d.h. jeder Pixel färbt alle seine Nachbarn, und die wieder die Nachbarn usw.. Das ganze wird nicht rekursiv gemacht, sondern in ein array zwischengespeichert. Das Array liegt im RAM und nicht im Stack (sry falls ich da jetzt möglicherweise meine unwissenheit zeige, ich vermute mal, dass es so ist ;) ), und RAM ist genug da.

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
{converts an area of white pixels in one color}
procedure TForm1.Convert(X,Y,Color: integer);
var Queue: TConvArray; //queue used to avoid a stack overflow
begin
 SetLength(Queue,1);
 Queue[0].X:=X;
 Queue[0].Y:=Y;

 while Length(Queue)>0 do
   begin

      X:=Queue[High(Queue)].X;
      Y:=Queue[High(Queue)].Y;
      SetLength(Queue,Length(Queue)-1);

       if (Pix[X,Y]=clWhite)then
         begin
          Pix[X,Y]:=Color;

          if (X+1>=0)and(Y>=0)and(X+1<=High(Pix))and(Y<=High(Pix[0]))then
            if Pix[X+1,Y]=clWhite then
              begin
                SetLength(Queue,Length(Queue)+1);
                Queue[High(Queue)].X:=X+1;
                Queue[High(Queue)].Y:=Y;
              end;

          if (X>=0)and(Y+1>=0)and(X<=High(Pix))and(Y+1<=High(Pix[0]))then
            if Pix[X,Y+1]=clWhite then
              begin
                SetLength(Queue,Length(Queue)+1);
                Queue[High(Queue)].X:=X;
                Queue[High(Queue)].Y:=Y+1;
              end;

          if (X-1>=0)and(Y>=0)and(X-1<=High(Pix))and(Y<=High(Pix[0]))then
            if Pix[X-1,Y]=clWhite then
              begin
                SetLength(Queue,Length(Queue)+1);
                Queue[High(Queue)].X:=X-1;
                Queue[High(Queue)].Y:=Y;
              end;

          if (X>=0)and(Y-1>=0)and(X<=High(Pix))and(Y-1<=High(Pix[0]))then
            if Pix[X,Y-1]=clWhite then

              begin
                SetLength(Queue,Length(Queue)+1);
                Queue[High(Queue)].X:=X;
                Queue[High(Queue)].Y:=Y-1;
              end;
        end;
   end;
end;


Edit:
www.delphi-forum.de/viewtopic.php?p=432683
Das war wohl die Originalseite dazu. Interessant, dass ich schon vor 2 Jahren die Lösung für ein Problem im Forum gefunden hab, wozu man heute keine Lösung mehr findet... :mrgreen:

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)


Zuletzt bearbeitet von Xion am Mi 07.04.10 20:17, insgesamt 2-mal bearbeitet
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10183
Erhaltene Danke: 1256

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Mi 07.04.10 17:01 
Moin!

user profile iconXion hat folgendes geschrieben Zum zitierten Posting springen:
Wenns bei dir um Sortierung geht und es entsteht ein Stack Overflow wohl bei etwas rekursivem.
Das würde ich auch so sehen. ;) Klassische Lösung: nicht so exzessiv Rekursion einsetzen. :D Oder: den Stack-Bereich etwas vergrößern. Das ist aber keine pauschale Lösung für einen StackOverflow!

user profile iconXion hat folgendes geschrieben Zum zitierten Posting springen:
Das Array liegt im RAM und nicht im Stack (sry falls ich da jetzt möglicherweise meine unwissenheit zeige, ich vermute mal, dass es so ist ;) ), und RAM ist genug da.
Um das aufzuklären: beides liegt im RAM, aber die dynamischen Arrays liegen in einem anderen Bereich (auf dem sog. Heap), und da ist normalerweise mehr "Platz", als auf dem Stack. :idea: ;)

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.
Xion
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Mi 07.04.10 17:26 
user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Um das aufzuklären: beides liegt im RAM, aber die dynamischen Arrays liegen in einem anderen Bereich (auf dem sog. Heap), und da ist normalerweise mehr "Platz", als auf dem Stack. :idea: ;)

Dafür habe ich eigentlich das Informatik-Studium angefangen...da wir aber ne TU sind hab ich die Befürchtung, sowas lernen wir hier nie :cry: (naja, bin ja erst 2.Semester)

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
elundril
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3747
Erhaltene Danke: 123

Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
BeitragVerfasst: Mi 07.04.10 22:58 
user profile iconXion hat folgendes geschrieben Zum zitierten Posting springen:
Dafür habe ich eigentlich das Informatik-Studium angefangen...da wir aber ne TU sind hab ich die Befürchtung, sowas lernen wir hier nie :cry: (naja, bin ja erst 2.Semester)


Sorry für OT: aber warum sollte das daran liegen das du auf ner TU bist? Ich hoff das is nicht das selbe blöde Gschichtl wie: "Realgymnasiasten sind dumme Kinder, weil die ins Realgymnasium gehen und das normale Gymnasium ned schaffen!"

lg elundril

_________________
This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.