Problem mit rekursion bei determinantenberechnung

zeusosc

Hi,
ich habe einen algorithmus zur berechnung von determinanten geschrieben.
Für kleinere Matrizen funktioniert der algo einwandfrei.
Bei einer symmetrischen 21x21 Matrix kommt jedoch (irgendwann) diese Meldung:

This application has requested the Runtime to terminate it in an unusal way.

Hier der Code:

double det(int x, int y)
        {
         double summe=0;
         twoDimArr copy(*this);

         if((copy.Cols==1)&&(copy.Rows==1))
         { return copy[0][0];};

         if(copy.Cols==2){
         summe=(copy[0][0]*copy[1][1] - copy[0][1]*copy[1][0]);
         return summe;};

         for(int i=0;i<copy.Cols;i++)
         {summe=summe+product_series(-1,i+2)*copy[x][i]*copy.minor(x,i);}

         return summe;
}

Hat jemand eine Idee??
gruß und dank

Hallo

twoDimArr copy(*this);

1. was ist twoDimArr für eine klasse ? was macht copy genau ?
2. einen this zeiger kannst du nur innerhalb einer klasse übergeben,
du bist jedoch in einer funktion. (wahrscheinlich gekürzt)

außerdem sehe ich da nirgens einen rekursiven aufruf.
poste auch die entschprechenden memberfunktionen, sonst können wir nur raten

zeusosc

ahh, sry. Ich hatte ein codefragment ausgelagert.

double minor(int x, int y)
        {
         double summe;
        twoDimArr *copy;
        copy=new twoDimArr(*this);
        copy->DelRow(x);
        copy->DelCol(y);
        summe=copy->det(0,0);
        delete copy;
	return summe;
}

twoDimArr ist eine Klasse, die eigentliche matrix klasse.
det eine methode dieser.

Was ich festgestellt habe ist das das prog immer nur dann terminiert wird, wenn der arbeitspeicher voll ist. Leider wird der bereich des Arbeitsspeichers auch nach aufruf von det nicht freigestellt.

BorisDieKlinge

wie tief geht die rekursion?

wie groß ist twoDimArr objekt?

due legst ja das twoDimArr auf dem stack an, der irgendwann voll ist..

debuggen

BorisDieKlinge

schau dir mal den callstack an... der wird ins unendliche gehen.. wenn deine matrizen zu groß werden

zeusosc

Ja, der geht ins unendliche.

Also das ganze funktioniert bis zur det von einer 10x10 Matrix. Bei einer 11x11 jagd dieser aber den po hoch. Also bei einer 11x11 Matrix werden 11 mal eine 10x10 Matrix aufgerufen. Daraus werden wieder 10 mal 9x9 Matrizen etc. Also rund 19958400 rekursive aufrufe.

class twoDimArr
{
    private:
        double* pArr;
        int Rows, Cols;
        double cutoff;
        bool use_cutoff;    
        double *diag;
    public:
twoDimArr(int Zeilen, int Spalten)
        {
            Rows = Zeilen;
            Cols = Spalten;
            use_cutoff=false;
            cutoff=0;
            // 2-Dimensionales Array auf 1-Dimensionales abbilden
            pArr=new double [Rows*Cols];
 		    diag=new double [Cols];
            for(int x=0;x<(Rows*Cols);x++){pArr[x]=0;};
        }

Das Problem was ich sehe ist das der allocierte speicher nicht wieder frei gegeben wird. Sonst würde die Berechnung klappen.

Als Beispiel:

twoDimArr a(10,10);
a.det(0,0);
a.~twoDimArr();
system("pause");

Der Taskmanager zeigt mir nach ausführung der berechnung noch 1.3G allocierten ram an. Dabei sollte doch beim destructor der speicher wieder freigegeben werden.

~twoDimArr()
{
delete [] pArr;
delete [] diag;
pArr=NULL;
diag=NULL;
}

könnt ihr mir da weiterhelfen wie ich den speicher wieder frei bekomme???
Selbst mit malloc und free ist der speicher irgendwie immer noch belegt.

gruß und dank

BorisDieKlinge

doch der speicher wir wieder freigegeben, aber es kommt durch die rekursion nie dazu...du legst eine kopie eines objekt im stack an.. bevor dieser kopie wieder freigegeben wird, springt er erst in die nächst rekurstion... und das so lange bis der staäck vollgelaufen ist...! Bei einer 10X10 matrix (wie du erläutert) ahst wird der stack wieder nach der letzen rekustion wieder rückwärts freigegeben.

void rek(){
  twoDimArr a(10,10); //objekt wird aufm stack angelgt
  a.det(0,0); //Berabeite 
  rek(); //nächste rekursion (objekt a wird aber noch nich gelöscht da rekursion)
} //objekt wird hier wieder gelöscht

du kannst die Stackgröße verändern... aber ich würde die ganze geschichte ohne rekursion machen, sonst ist immer die größe des stacks von der größe der amtrix abhängig;) geht das nich itereativ?

zeusosc

Ja das sollte es eigentlich, gerade bei der 11x11 matrix sollte der speicher der ersten 10x10 submatrix nach berechnung der subdeterminanten wieder freigegeben werden. Aber genau das geschieht leider nicht. Mir ist klar das (bei deinem beispiel) a noch nicht gelöscht wird, aber die untermatritzen sollten es jedenfalls.

Ich hatte schon ein Beispiel angegeben. Selbst da wird der Speicher nicht freigegeben (Nach Task Manager).

Ja es gibt noch eine alternitive berrechnungsmethode, und zwar nach Gauß in eine obere Dreiecksmatrix, dann einfach das Produkt der Elemente der Hauptdiagonalen.

Mich Interresiert aber noch mein Hauptproblem.
Ich probiers mal mit std::vector.

Woran kann das noch liegen?
gruß und dank

BorisDieKlinge

naja wieviel speicher belegt denn so ein twoDimArr objekt in bytes? bei einer 10 x10 matrix? so um die 440 Bytes? glaub nich das man das im taskmanger erkennt;)

Nach dem taskmanger kann schlecht gehen.. da du das ganze im debugger testest..
wenn er die rekurstion beginnt, sieht man dann wie die speicherbelegung steigt?

zeusosc

Ein twoDimArr objekt belegt 32 byte's. (sizeof).
Eine Matrix erkennt man nicht richtig. Aber beim Aufruf "sah" man wie der Speicherbedarf auf 1.3G stieg, welcher selbst nach vollendung nicht frei gegeben wurde.

Ich weiß nicht wieso, aber ich habe am source ein bissl rumgebastellt und die speicher allocation von new auf malloc gesetzt, auf einmal funzt es. (auch mit free () ).

Zu doof das der rechner für eine 15x15 Matrix ewig (knapp 1h) braucht.
Ich werde wohl auf die alternative berrechnung umstellen müssen.

Danke und gruß