Seite 1 von 1
[gelöst] Maximale Rekursionstiefe?
Verfasst: 16. September 2008 04:08
von gelignite
Hallo,
ich habe eine Methode, die sich (für die Ausübung ihres Zwecks) rekursiv aufruft. Ich durchlaufe damit Bilder (Typ: QImage). Es wird beim Bildmittelpunkt begonnen. Sind die Bilder klein genug, so verläuft alles wie gewünscht. Um die Funktion aber auf ihr "Können" zu prüfen, habe ich ein Bild im Format 800x600 genommen. Dieses Bild ist komplett weiß und soll einfach schwarz gemacht werden. Dabei schmiert mir das Programm mit einem Segmentation fault ab. Ich habe daraufhin einen Zähler hinzugenommen. Mit diesem limitiere ich die Rekursionstiefe auf einen festen Wert. Ergebnis: Kein Segmentation fault, das Programm läuft.
Ich habe dunkel in Erinnerung, dass bei der Rekursion so einiges zwischengeparkt wird, um es zum geeigneten Zeitpunkt wieder weiterzuverwenden. Ich nehme an, es liegt derweil auf dem Stack. Da der von System zu System meines Wissens nach unterschiedlich ist, denke ich, dass ich mit meinem fixen Limit auf dem einen System mehr Glück habe als auf einem anderen.
Welche Möglichkeiten gibt es hierzu keinen konstanten Wert zu nehmen?
Gruß,
gelignite
Re: Maximale Rekursionstiefe?
Verfasst: 16. September 2008 07:13
von macman
gelignite hat geschrieben:Dabei schmiert mir das Programm mit einem Segmentation fault ab.
Dann fehlt irgendwo eine Pointerüberprüfung. Die max. Rekursionstiefe ist natürlich auf jedem Rechner unterschiedlich, deshalb nutzt ein statischer Wert hier gar nichts. Nimm lieber einen Debugger und schau wo der Absturz stattfindet.
Re: Maximale Rekursionstiefe?
Verfasst: 16. September 2008 09:06
von solarix
gelignite hat geschrieben:
Welche Möglichkeiten gibt es hierzu keinen konstanten Wert zu nehmen?
Deine Erinnerung täuscht dich nicht.. die Limite ist compilerabhängig.. also entweder steuerst du die Limite (stack-size) per Compiler-Flag (schlechte Variante) oder du löst das Problem iterativ anstatt rekursiv (gute Variante).
Re: Maximale Rekursionstiefe?
Verfasst: 16. September 2008 15:17
von gelignite
macman hat geschrieben:gelignite hat geschrieben:Dabei schmiert mir das Programm mit einem Segmentation fault ab.
Dann fehlt irgendwo eine Pointerüberprüfung.
An welcher Stelle genau? Ich scheine den Wald vor lauter Bäumen nicht zu sehen. Das ist die Methode:
Code: Alles auswählen
void BLOB::fill( QImage & image, const int & width, const int & height,
int x, int y, uchar & newval, int & depth )
{
// Don't decend too deep
if ( depth > 100000 ) // So klappt es. Wird der Teil aber auskommentiert, kommt es zum SegFault.
return;
// Change color to not to touch a pixel twice
image.setPixel( x, y, newval );
// Upwards
if ( y > 0 )
if ( qGray( image.pixel( x, y - 1 ) ) == _white )
{
depth++;
this->fill( image, width, height, x, y - 1, newval, depth );
depth--;
}
// Rightwards
if ( x < width - 1 )
if ( qGray( image.pixel( x + 1, y ) ) == _white )
{
depth++;
this->fill( image, width, height, x + 1, y, newval, depth );
depth--;
}
// Downwards
if ( y < height - 1 )
if ( qGray( image.pixel( x, y + 1 ) ) == _white )
{
depth++;
this->fill( image, width, height, x, y + 1, newval, depth );
depth--;
}
// Leftwards
if ( x > 0 )
if ( qGray( image.pixel( x - 1, y ) ) == _white )
{
depth++;
this->fill( image, width, height, x - 1, y, newval, depth );
depth--;
}
}
Ich bin der Meinung nur Referenzen auf Objekte weiterzureichen. Zeiger sind da nirgends angelegt. Vor dem Aufruf dieser Methode befindet sich ein qDebug("Now filling ..."); und nach dem Aufruf ein qDebug("...done filling."); In der Anwendungs-Konsole steht dann:
Now filling ...
*** Process aborted. Segmentation fault ***
Es funktioniert wie erwähnt aber, wenn ich die Rekursionstiefe limitiere.
solarix hat geschrieben:oder du löst das Problem iterativ anstatt rekursiv (gute Variante)
Die iterative Lösung würde mir auch besser gefallen, aber eine iterative Lösung dazu (siehe Code oben) kenne ich nicht.
Das Bild soll nicht pixelweise durchlaufen werden, sondern zusammenhängende Teile sollen damit befüllt werden. (Quasi, wie die Tintenfass-Funktionalität aus Zeichenprogrammen).
Gruß,
gelignite
Verfasst: 16. September 2008 15:25
von Christian81
Dein Stack ist einfach zu klein - da gibts nichts zu korrigieren...
Verfasst: 16. September 2008 17:25
von upsala
Startposition in QQueue.
while (QQueue not empty) {
Position aus QQueue holen.
if (!Wurde die Position bereits bearbeitet) {
Position bearbeiten
if (Wurde die Position links davon bereits bearbeitet) {
Linken Punkt in die QQueue
}
if (Wurde die Position rechts davon bereits bearbeitet) {
Rechten Punkt in die QQueue
}
// dito rechts und links...
}
}
Verfasst: 16. September 2008 20:37
von gelignite
Christian81 hat geschrieben:Dein Stack ist einfach zu klein - da gibts nichts zu korrigieren...
... und da heißt es immer, auf die Größe käme es nicht an.
Da hab ich wohl Pech.
@upsala:
Das hieße aber - wenn ich das richtig interpretiere - alle Startpositionen bereits in der Queue zu haben. Ich kenne aber zu Beginn keine, sondern diese "ergeben sich im Laufe der Zeit".
Der Pseudocode für das, wozu ich die Funktion verwende, lautet:
Code: Alles auswählen
Füllfarbe = 1; // Nicht schwarz
Durchlaufe das Ausgangsbild // im PGM Format, enthält zu Beginn der Funktion nur schwarze und weiße Pixel
{
Wenn das aktuelle Pixel weiß ist
{
startPosition = aktuellesPixel;
FülleBereich( Ausgangsbild, startPosition, Füllfarbe );
}
Füllfarbe++;
Wenn Füllfarbe = weiß
{
Füllfarbe = 1;
}
}
Nunja, es wird langsam Off topic. Mir war es eigentlich wichtig herauszufinden, ob der Segmentation Fault wegen einer möglichen Überschreitung der maximalen Rekursiontiefe herrührt. Das scheint mir der Fall zu sein, wenn es heißt, der Stack sei zu klein. Ich hätte dann allerdings etwas Aussagekräftigeres als "Segmenation fault" erwartet.
Gruß,
gelignite
Verfasst: 16. September 2008 22:16
von solarix
gelignite hat geschrieben:
Die iterative Lösung würde mir auch besser gefallen, aber eine iterative Lösung dazu (siehe Code oben) kenne ich nicht.
...
das hieße aber - wenn ich das richtig interpretiere - alle Startpositionen bereits in der Queue zu haben. Ich kenne aber zu Beginn keine, sondern diese "ergeben sich im Laufe der Zeit".
sei kreativ.. für dein Problem gibt es ne Menge Lösungen (rekursive als auch iterative). Eine häufige iterative Strategie ist (wie upsala mit dem Pseudocode demonstriert), eine "Datenbank" zu halten welche die gleichen Informationen umfasst, welche bei der Rekursion auf dem Stack landen würden (also die neuen Koordinaten).
gelignite hat geschrieben:
Ich hätte dann allerdings etwas Aussagekräftigeres als "Segmenation fault" erwartet.
Dein Programm verwendet den zugewiesenen virtuellen Speicher falsch... das passt doch haargenau....
