0*C00000FD Stack overflow

Artchi

Naja, die Abbruckbedingung kann schon richtig sein, auch für dich mag sie i.O. sein. Aber der Stack hat nunmla nur eine begrenzte Größe, und die ist nunmal manchmal schnell ausgreizt.

Wenn z.B. 1 Mio. Rekursionen zustande kommen und danach der Abruch erfolgen sollte, und der Stack aber nur 999.999 erlaubt, ist es Pech für dich und es gibt einen Stackoverflow.

Wirst du notfalls ohne Rekursion lösen müssen.

stick_thai

das problem tritt bei 8679 Rekursionen auf. das ist doch noch nicht zu viel, oder?

wie kriege ich raus, wieviel der stack erlaubt?

DANKE.

P.S.: mir ist gerade noch eingefallen, dass ich zuvor in der "NEIGHBOUR"-funktion einen kleinen fehler hatte, wodurch das programm zwar auch gelaufen ist, aber nicht alle werte mit der zahl 2 gefunden hat. bei dieser fehlerhaften version ist die funktion "NEIGHBOUR" bis zu 22.000 mal aufgerufen wurde, ohne einen STACK OVERFLOW. nun habe ich sie "berichtigt", aber das programm bricht eher ab. irgendwie komisch.

Artchi

8679 könnte zu viel sein, warum auch nicht? Weil es sind ja nicht nur 8679 Aufrufe (die würde er verkraften) aber du hast ja bei jedem Aufruf noch zus. Variablen auf dem Stack. Das summiert sich dann ganz schön.

Welches OS oder Compiler hast du? Beim VC++ kann man unter Projekt->Eigenschaften->Linker->System was an den Heap und Stack Werten drehen. Hab ich aber bisher nie gebraucht. Notfalls die MSDN-Hilfe zu Rate ziehen.

stick_thai

ja, ich habe jetzt wieder die alte fehlerhafte version getestet.

aus (richtige version):

if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])

wird (falsche version):

if (i+k>=0 && k+l>=0 && i+k<DIM[0] && j+l<DIM[1])

jetzt läuft das ganze 24407 mal durch ohne STACK OVERFLOW. das kann ich mir wirklich NICHT erklären.

STICK.

p.s.: ich benutze noch immer VC++ 6.0 sowie XP.

stick_thai

so wie es aussieht, hat niemand von euch noch eine vermutung, wie der LAYER STACK zustande kommt, oder?

also ich bin mit meiner weisheit auch ziemlich am ende

camper

stick_thai schrieb:

so wie es aussieht, hat niemand von euch noch eine vermutung, wie der LAYER STACK zustande kommt, oder?

also ich bin mit meiner weisheit auch ziemlich am ende

ich schätze eher, so geht es jedenfalls mir, dass sich nicht viele die mühe machen, hier etwas zu lösen. denn auch hier ist wieder das grundprinzip richtiger fragestellung missachtet worden. ohne ein (prinzipiell) ausführbares beispiel, kann hier keiner etwas nachvollziehen. wenn man etwas nicht nachvollziehen kann, kann man auch nicht diagnostizieren. im übrigen ist das, was du als richtige variante bezeichnest, identisch mit dem, das als falsche version bezeichnest wird.

stick_thai

@Camper:

1.) was ist als beispiel besser geeignet als der code, den ich bereits aufgeführt habe? des weiteren habe ich das problem dazu ebenfalls beschrieben. und die fehlermeldung ist auch da.
ich weis nicht, woran es an erklärung noch fehlen sollte. vielleicht kannst du mir ja sagen, was du noch dazu wissen musst? das photo, dass ich mit diesem code interpretieren möchte, kann man ja leider nicht anhängen.

2.) bei mir ist "j+l>=0" und "k+l>=0" nicht das gleiche.

stick_thai

HALLO.

ich habe nun den ratschlag von CAMPER umgesetzt und den code so extrahiert, dass er nur noch das prinzipiell auszuführende beispiel enthält. hier ist dazu der gesamte quellcode:

#include <conio.h>
#include <iostream>
#include <fstream>

using namespace std;

int **DATA,DIM[2]={480,544};
void NEIGHBOUR (int,int);

int main()
{
	int i,j,ZAHL;

	DATA = new int *[DIM[0]];
	for (i=0;i<DIM[0];i++)
		DATA[i] = new int [DIM[1]];

//zu untersuchende daten werden eingelesen
	std::ifstream myfile("data.txt");
	i=0;j=0;
	while (!myfile.eof())
	{	
		myfile >> ZAHL;
		DATA[i][j]=ZAHL;
		j++;
		if (DIM[1] == j)
		{
			j=0;
			i++;
		}
	}
	myfile.close();

//daten werden auf zusammenhänge bereiche mit der zahl 2 untersucht
	for (i=0;i<DIM[0];i++)
	{
		for (j=0;j<DIM[1];j++)
		{
			if (2 == DATA[i][j])
			{
				DATA[i][j]=3;
				NEIGHBOUR(i,j);
			}
		}
	}
    return 0;
}

void NEIGHBOUR (int i,int j)
{
	int k,l;

	for (k=-1;k<2;k++)
	{
		for (l=-1;l<2;l++)
		{
			if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])
			{
				if (2 == DATA[i+k][j+l])
				{
					DATA[i][j] = 3;
					NEIGHBOUR (i+k,j+l);
				}
			}
		}
	}
}

zu untersuchen ist, wieviele zusammenhängende elemente enthalten ZWEIEN. zusammenhängend heisst, dass eine 2 einem bereich zugeordnet wird, wenn eines der 8 nächsten nachbarn ebenfalls eine 2 ist. die 8 nachbarn sind, wenn man sich das ganze als bild vorstellt, die 8 pixel, die sich um das zu untersuchende pixel (i+k,j+l) befinden.
mit den zahlenwerten in "data.txt" bleibt der code bei i=69 && j=313 hängen. dass heisst, an der stelle "NEIGHBOUR (i+k,j+l);" kommt dann der verweis auf den LAYER OVERSTACK.
und das problem tritt nicht auf, wenn ich

if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])
mit 
if (i+k>=0 && k+l>=0 && i+k<DIM[0] && j+l<DIM[1])

austausche.

okay. ich hoffe, dass ich alle notwendigen informationen zusammengetragen habe.

DANKE NOCHMALS.
STICK.

MFK

stick_thai schrieb:

und das problem tritt nicht auf, wenn ich
if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])
mit 
if (i+k>=0 && k+l>=0 && i+k<DIM[0] && j+l<DIM[1])
austausche.

Das Problem tritt also nicht mehr auf, wenn du dein Programm so änderst, dass es nicht mehr funktioniert? Das ist nicht wirklich hilfreich.

Ich sehe da keine logischen Fehler. Je nachdem, wie viele Zweier in deiner Datei sind, sind es eben zu viele Rekursionen. Du kannst versuchen, den Stack zu vergrößern, aber das ist IMHO nur Schmerzverlagerungstherapie. Warum suchst du nicht nach einem iterativen Ansatz? Die Verwaltungsdaten dafür könntest du auf dem Heap anlegen, der wird dir nicht so schnell ausgehen.

stick_thai

@MFK:
danke für die antwort. ich habe leider diesmal nicht erwähnt, was die veränderung zeigen soll, weil ich das schon einmal geschrieben hatte.

bei der richtigen version, also mit i+k>=0 && j+l>=0, ist die anzahl der durchläufe der schleife so ca. 8000.
bei der falschen version, also mit i+k>=0 && k+l>=0, beträgt der maximale durchlauf der schleife ca 24.000, ohne einen LAYER STACK OVERFLOW.

darum ist meine vermutung, dass der LAYER STACK nicht zu klein ist, oder sehe ich das falsch?

MFK

darum ist meine vermutung, dass der LAYER STACK nicht zu klein ist, oder sehe ich das falsch?

Das siehst du falsch. Es ist egal, wie oft die Schleife durchlaufen wird. Entscheidend ist die Rekursionstiefe.

So kannst du Rekursionstiefe nachhalten:

int depth = 0;
int maxdepth = 0;

void NEIGHBOUR (int i,int j)
{
    ++depth;
    if(depth > maxdepth) maxdepth = depth;

    int k,l;

    for (k=-1;k<2;k++)
    {
        for (l=-1;l<2;l++)
        {
            if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])
            {
                if (2 == DATA[i+k][j+l])
                {
                    DATA[i][j] = 3;
                    NEIGHBOUR (i+k,j+l);
                }
            }
        }
    }
    --depth;
}

linux

.... musst Du Stackgrösse in den Compileroptionen der IDE erhöhen.

stick_thai

@MFK:
ich habe deine veränderungen im code angebracht und tatsächlich ist die maximale tiefe bei der "falschen version" gerade mal 1680, während bei der "richtigen version" der STACK OVERFLOW bei ca. 25800 eintritt.

muss ich das ganze wohl doch iterativ machen, schade.

camper

stick_thai schrieb:

@MFK:
ich habe deine veränderungen im code angebracht und tatsächlich ist die maximale tiefe bei der "falschen version" gerade mal 1680, während bei der "richtigen version" der STACK OVERFLOW bei ca. 25800 eintritt.

muss ich das ganze wohl doch iterativ machen, schade.

so wie ich das sehe, ist die potentielle rekursionstiefe gleich dem größe des feldes, also 480*544 = 261120. ein sicherer algorithmus muss damit zurechtkommen. eine iterative variante ist ja hier relativ leicht zu erstellen.

stick_thai

HALLO.

erstmal danke, dass ihr mich darauf aufmerksam gemacht habt, dass es auch mit einer iterativen funktion gehen muss. habe diese information nun umgesetzt in folgende NEIGHBOUR-funktion:

void NEIGHBOUR (int **data,int i, int j,int DIM[2],double MAX[2])
{
	int k,l;
	ENT[0]=0;
	vector <int> PKTE;
	vector <int>::iterator it;

	while (0==ENT[0])
	{
		if (MAX[0]!=1)
		{
			it = PKTE.end();
			PKTE.erase(--it);
			it = PKTE.end();
			PKTE.erase(--it);
		}
		for (k=-1;k<2;k++)
		{
			for (l=-1;l<2;l++)
			{
				if (i+k>=0 && j+l>=0 && i+k<DIM[0] && j+l<DIM[1])
				{
					if (2 == data[i+k][j+l])
					{
						data[i+k][j+l]= 3;
						MAX[0]++;
						PKTE.push_back(i+k);
						PKTE.push_back(j+l);
					}
				}
			}
		}
		if ((int)PKTE.size()>0)
		{
			i = PKTE[PKTE.size()-2];
			j = PKTE[PKTE.size()-1];
		}		
		else ENT[0]=1;
	}
	ENT[0]=0;
}

meine frage dazu wäre, ob man das noch irgendwie optimieren / beschleunigen kann, oder ist das jetzt schon gut so?

DANKE!
STICK.

Hallo stick_thai,

vielleicht kannst du in deiner rekursiven Variante das l (L) mal durch eine andere Variable ersetzen. Mit einer, die der 1 (eins) nicht so ähnlich ist. Vielleicht hast du dich da ja einmal vertippt.
Kann natürlich auch einfach nur die Schrift hier sein....

Nur eine Idee,
Jens

MFK

stick_thai schrieb:

meine frage dazu wäre, ob man das noch irgendwie optimieren / beschleunigen kann, oder ist das jetzt schon gut so?

Die Vorgehensweise ist so schon ganz gut. Ich würde die (i+k)-Bereichsprüfung aus der inneren Schleife in die äußere verlegen. Wenn i+k nicht passt, kannst du dir diesen Durchlauf der inneren Schleife komplett schenken.

Außerdem würde ich, statt immer paarweise ints abzulegen, lieber eine Struktur mit zwei int-Membern oder ein std::pair<int, int> ablegen. Das dient eher der Übersichtlichkeit als der Geschwindigkeit.

Statt erase mit dem dekrementierten end-Iterator aufzurufen, könntest du auch einfach std::vector::pop_back benutzen, und statt über den Index size() - 1 zu gehen, std::vector::back nehmen. Aber auch das hat vermutlich wenig Einfluss auf die Geschwindigkeit.

@MFK:
danke für die hinweise, wieder was dazugelernt