0*C00000FD Stack overflow

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