[gelöst] Maximale Rekursionstiefe?

[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

[macman]

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.

[solarix]

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

[gelignite]

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.

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

[Christian81]

Dein Stack ist einfach zu klein - da gibts nichts zu korrigieren...

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

[gelignite]

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

[solarix]

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

Ich hätte dann allerdings etwas Aussagekräftigeres als "Segmenation fault" erwartet.

Dein Programm verwendet den zugewiesenen virtuellen Speicher falsch... das passt doch haargenau....