Größe dynamischer zweidimensionaler Arrays ändern



  • In meinem Programm soll die Größe eines zweidimensionalen Arrays im laufenden Programm geändert und mit neuen Zufallswerten belegt werden. Dazu habe ich folgende Schleife geschrieben:

    L = (double**)realloc(L,n*sizeof(double*));
    	for (j=0; j<n; j++)
    	{
    		L[j] = (double*)realloc(L[j],(j+1)*sizeof(double));
    		for (i=0; i<=j; i++)
    		{
    			x=-4096+rand()%8192;
    			L[j][i]=x/4096;
    		}
    	}
    

    Im weiteren Programm soll mit der Matrix gerechnet werden. Ich brauche für verschiedene Matrixgrößen die Programmlaufzeit, daher steht alles in einer Schleife welche die Matrixgröße n steigert. Für n=1 funktioniert alles, aber für n=2 stürzt das Programm bei j=1 ab, also wenn die zweite Zeile der Matrix erstellt werden soll.

    Kann mir jemand sagen, woran das liegt?

    Grüße



  • Der an realloc übergebene Zeiger muss entweder NULL, oder den Rückgabewert von malloc/calloc/realloc enthalten.
    Btw. hast du in deinem Code potentielle memory leaks.
    Realloc kann auch NULL liefern und der Speicher, auf den L/L[j] zeigt, wäre dann nicht mehr zugänglich.



  • Ich bin Leider noch nicht so fortgeschritten was das Programmieren angeht. Könntest du mir das bitte genauer erklären?

    Soweit ich das bisher verstanden habe ist der Rückgabewert von malloc/calloc/realloc doch jeweils der beginn des Arrays (sofern dieses angelegt wurde), also L für die Zeilen und L[j] für die Spalten. Und die übergebe ich an realloc.



  • Das sollte prinzpiell tun, was du vorhast.
    Eine n x n Matrix wächst dynamisch n -> n+1
    Inklusive potentieller memory leaks.
    http://ideone.com/XwERkw

    double** M = NULL;
    	const int nmax = 10;
    	int i, j, n;
    
    	for ( n = 1; n <= nmax; n++ )
    	{
    		M = realloc(M, n*sizeof(double*));
    		for ( i = 0; i < n - 1; i++ )
    		{
    			M[i] = realloc(M[i], n*sizeof(double));
    		}
    		M[n-1] = malloc(n*sizeof(double));
    
    		for ( j = 0; j < n; j++ )
    		{
    			// mach was mit deiner matrix
    		}
    	}
    
    	for ( i = 0; i < nmax; i++ )
    		free ( M[i] );
    	free ( M );
    

    Würd ich aber so nicht machen. 😃
    Eher sowas in der Richtung:
    http://ideone.com/dwLXio

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    {
    	double* M = NULL;
    	const int nmax = 10;
    	int x, y, n;
    
    	for ( n = 1; n <= nmax; n++ )
    	{
    		double* temp = realloc ( M, n * n * sizeof(double));
    		if ( temp == NULL )
    		{
    			// realloc liefert NULL -> Fehlerbehandlung
    			// Zugriff auf M möglich, um z.B. die Daten zu retten, etc.
    		}
    		else
    		{
    			M = temp; // Oki doki
    		}
    
    		for ( y = 0; y < n; y++ )
    		{
    			for ( x = 0; x < n; x++ )
    			{
    				// mach was mit der Matrix
    				// m [ y * n + x ] = ???
    			}
    		}
    	}
    
    	free ( M );
    	return 0;
    }
    

    Ein Block, adressiert per Index [ y * n + x ].
    Die double** Zeiger entfallen.

    .oO
    Fragt sich vllt. noch inwiefern es sinnvoll ist realloc zu benutzen.
    Eigentlich nur dann, wenn du die Werte für weitere Berechnungen brauchst.
    Dazu fällt mir gerade kein sinnvolles Anwendugsbeispiel ein.

    Ansonsten dürfte es billger sein, die komplette Matrix per free fallen zu lassen und eine neue zu erstellen.
    Also nur mit malloc/calloc free arbeiten.
    Die per realloc durchgeführten Kopiervorgänge entfallen dann nämlich.



  • Thorsten90 schrieb:

    Ich bin Leider noch nicht so fortgeschritten was das Programmieren angeht. Könntest du mir das bitte genauer erklären?

    Soweit ich das bisher verstanden habe ist der Rückgabewert von malloc/calloc/realloc doch jeweils der beginn des Arrays (sofern dieses angelegt wurde), also L für die Zeilen und L[j] für die Spalten. Und die übergebe ich an realloc.

    Ja, aber für L[0] hast du von keiner der genannten Funktionen Speicher bekommen.



  • Habe mein Programm jetzt so geändert dass der Speicher mit calloc immer neu reserviert und anschließend mit free wieder freigegeben wird. Ohne free funktioniert alles, mit free arbeitet das Programm einen Augenblick lang, stürzt dann allerdings ab (mit den momentanen Werten bei n=37). Woran könnte das liegen?



  • Vermutlich gibst du nicht alles frei, was freizugeben ist.



  • So sieht mein Programm aus, abzüglich der Ausgaben in der Konsole. Wird n zu groß, stürzt es ab. Dabei stürzt es früher ab, wenn ich es ohne Debugging starte. Es stürzt später ab, wenn ich free rausnehme. Auch die t-schleife (wiederholt alles mit dem selben n, damit ich mehrere Zeiten für gleiche Matrixgrößen erhalte) ändert den Punkt, an dem es abstürzt.

    Beim Debugging bekomme ich als Fehlermeldung ""Unbehandelte Ausnahme bei ... Zugriffsverletzung beim Lesen ...". Der Fehler tritt immer in Zeile 62 auf.

    Soweit ich es bisher verstanden habe gibt es irgendwo einen Fehler beim Zugriff auf die Matrix. Allerdings habe ich keine Ahnung, was falsch ist und auch nicht wirklich eine Ahnung davon, wie der Fehler aussehen könnte oder wo ich suchen muss.

    Den Allgorithmus habe ich für kleine Matrizen (n=3,4,5,6,7, MAX2=2,3) getestet, die Ergebnisse waren immer korrekt. Mit den neu erstellten dynamischen Matrizen wollte ich es für größere n testen, aber da gibt es immer diesen Fehler.

    int main ()
    {
    	double **L=NULL;
    	double **Y=NULL;
    	double **B=NULL;
    	int i=0,j=0,k=0,l=0;
    	double x=0,progtime=0;
    	clock_t start,end;
    	srand(time(NULL));
    	FILE *datei;
    	datei=fopen("E:/time.txt", "w+");
    
    	for (int n=1; n<=10000000; n++)
    	{
    		printf("\r%i",n);
    		for(int t=0; t<10; t++)
    		{
    			/*Matrix L erstellen*/
    			L = (double**)calloc(n,sizeof(*L));
    			for (j=0; j<n; j++)
    			{
    				L[j] = (double*)calloc(j+1,sizeof(**L));
    				for (i=0; i<=j; i++)
    				{
    					x=-4096+rand()%8192;
    					while (x==0 && i==j) x=-4096+rand()%8192;
    					L[j][i]=x/4096;
    				}
                }
    			/*Matrix B erstellen*/
    			B = (double**)calloc(n,sizeof(*B));
    			for (j=0; j<n; j++)
    			{
    				B[j] = (double*)calloc(MAX2,sizeof(**B));
    				for (i=0; i<MAX2; i++)
    				{
    					x=-4096+rand()%8192;
    					B[j][i]=x/4096;
    				}
    			}
    			/*Matrix Y erstellen*/
    			Y = (double**)calloc(n,sizeof(*Y));
    			for (j=0; j<n; j++)
    			{
    				Y[j] = (double*)calloc(MAX2,sizeof(**Y));
    			}
    
    			start=clock();
    
    			/*Matrix Invertierung und Multiplikation*/
    			for(j=0; j<n; j++)
    			{
    				for (k=j; k<n; k++)
    				{
    					x=L[k][k];
    					if (j==0) L[k][k]=1;
    
    					for (i=0; i<=k; i++)
    					{
    						if (j==0) L[k][i]=L[k][i]/x;
    						double y=L[k][j-1];
    						if (j>0 && j==i+1) L[k][i]=0-L[j-1][i]*y;
    						else if (j>0 && j!=i+1) L[k][i]=L[k][i]-L[j-1][i]*y;
    					}
    
    					/*Multiplikation*/
    					for(i=0; i<MAX2; i++)
    					{
    						if (k==n-1 && i<MAX2)
    						{
    							for (l=0; l<=j; l++)
    							{
    								Y[j][i]=Y[j][i]+L[j][l]*B[l][i];
    							}
    }}}}
    
    			end=clock();
    
    			for (i=0; i<n; i++) 
    			{
    				free(L[i]);
    				free(B[i]);
    				free(Y[i]);
    			}
    			free(L);
    			free(Y);
    			free(B);
    
    			fprintf(datei,"%i\t%.3f\n", n,(float)(end-start)/CLOCKS_PER_SEC);
    		}}}
    

    Das Programm soll übrigens eine n x n untere Dreiecksmatrix L und normale n x 100 Matrix B erstellen und danach Y=L^-1 * B berechnen.

    ps: Habe ein paar Sachen zusammengeschoben, um das Ganze etwas zu kürzen. Hoffe, es ist nicht zu lang, wusste nicht, welchen Teil ich posten sollte. Ist mein Programmierstil so eigentlich Ok/übersichtlich oder sollte ich daran was ändern?



  • Teil dein Programm in Funktionen auf, befreie dich vom Joch der Spaghetticodeforschleifenorgie.
    Eine Funktion für die Ezeugung der Matrizen a la

    double** matrix_new ( unsigned m, unsigned n );
    

    und entsprechend je eine Funktion für die Initialisierung/Invertierung/Multiplikation/Speicherfreigabe.

    Dann findest du den Fehler bestimmt selbst.
    Warum schreibst du jedes mal (double**) vor calloc, benutzt du einen C++ Compiler?



  • Thorsten90 schrieb:

    wollte ich es für größere n testen, aber da gibt es immer diesen Fehler.

    Hast du mal ausgerechnet, wieviel Speicher du mir deinen Einzel-calloc zusammen belegst?
    Hast du die *alloc Rückgabewerte geprüft?
    Hast du die dir hier gegebenen Hinweise beachtet?
    Wieso reservierst du überhaupt jedesmal?
    Erstelle dir eine (Dreiecks)Matrix, und die von max. Größe.
    Und damit arbeitest du dann ausschließlich.



  • Hi, habe meinen Quellcode überarbeitet und einzelne Funktionen erstellt. Es hat zwar eine ganze weile gedauert, aber dann hab ich den Fehler doch noch gefunden, die Indizes beim Invertieren waren falsch, es wurde immer auf Werte zugegriffen, die außerhalb der Matrix lagen. Ich nehme an, dass daher kleine Matrizen zu falschen Ergebnissen und größere dann irgendwann zum Programmabsturz geführt haben. Hoffe, dass es keine weiteren Fehler gibt, aber scheint jetzt alles zu stimmen.

    Der Compiler ist übrigens C++. Ich programmiere mit Visual Studio, weil wir das auch in der Hochschule benutzen und Aufgaben, die abgegeben werden sollen, darüber getestet werden.

    Warum lief das Programm mit Debugging länger als ohne? Werden dabei Probleme durch den nicht initialisierten Inhalt teilweise kompensiert oder so?

    Wie sieht mein Quellcode jetzt aus? Gibt es noch was, das ich verbessern kann/sollte?

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    /*Matrix erstellen*/
    double** create_matrix (double** M, unsigned zeilen, unsigned spalten)
    {
        unsigned i;
        M=(double**)calloc(zeilen, sizeof(*M));
        for (i=0; i<zeilen; i++) M[i]=(double*)calloc(spalten, sizeof(**M));
        return (M);
    }
    /*Untere Dreiecksmatrix erstellen*/
    double** create_l_matrix (double** M, unsigned zeilen)
    {
        unsigned i;
        M=(double**)calloc(zeilen, sizeof(*M));
        for (i=0; i<zeilen; i++) M[i]=(double*)calloc(i+1, sizeof(**M));
        return (M);
    }
    /*Untere Dreiecksmatrix mit Zufallszahlen initialisieren*/
    void init_l_matrix_rnd (double** M, unsigned zeilen)
    {
        unsigned i, j;
        double x;
        for (j=0; j<zeilen; j++)
    	{
    		for (i=0; i<=j; i++)
    		{
    			x=-16384+rand()%RAND_MAX ;
    			while (x==0 && i==j) x=-16384+rand()%RAND_MAX ;
    			M[j][i] =x/16384;
    		}
    	}
    }
    /*Matrix mit Zufallszahlen initialisieren*/
    void init_matrix_rnd (double** M, unsigned zeilen, unsigned spalten)
    {
        unsigned i, j;
        double x=0;
        for (j=0; j<zeilen; j++)
    	{
    		for (i=0; i<spalten; i++)
    		{
    			x=-16384+rand()%RAND_MAX;
    			while (x==0 && i==j) x=-16384+rand()%RAND_MAX;
    			M[j][i]=x/16384;
    		}
    	}
    }
    /*Untere Dreiecksmatrix invertieren und mit zweiter Matrix multiplizieren - Berechnung der Challenge SS2013*/
    void calc_challenge_ss2013 (double** M1, double** M2, double** M3, unsigned zeilenM1, unsigned spaltenM2)
    {
        unsigned i,j,k,l;
        double x,y;
        for(j=0; j<zeilenM1; j++)
    	{
    		for (k=j; k<zeilenM1; k++)
    		{
    			x=M1[k][k];
    			if (j==0) M1[k][k]=1;
                for (i=0; i<=k; i++)
    			{
                    if (j==0) M1[k][i]=M1[k][i]/x;
    			}
    
    			for (i=0; i<j; i++)
    			{
    				y=M1[k][j-1];
    				if (j>0 && j==i+1) M1[k][i]=0-M1[j-1][i]*y;
    				else if (j>0 && j!=i+1) M1[k][i]=M1[k][i]-M1[j-1][i]*y;
    			}
    
    			for(i=0; i<spaltenM2; i++)
    			{
    				if (k==zeilenM1-1 && i<spaltenM2)
    				{
    					for (l=0; l<=j; l++)
    					{
    						M3[j][i]=M3[j][i]+M1[j][l]*M2[l][i];
    					}
    				}
    			}
    		}
    
    	}
    }
    /*Matrix freigeben*/
    void free_matrix (double** M, unsigned zeilen)
    {
        unsigned i;
        for (i=0; i<zeilen; i++) free(M[i]);
        free(M);
    }
    
    int main()
    {
        double **L=NULL;
        double **B=NULL;
        double **Y=NULL;
        int n,m,t;
        m=5;
        clock_t start,end;
        srand(time(NULL));
    
        FILE *datei;
        datei=fopen("E:/time.txt", "w+");
    
        for (n=1; n<1000; n++)
    	{
            printf("\r%i", n);
            for (t=0; t<10; t++)
    		{
                L=create_l_matrix(L, n);
                init_l_matrix_rnd(L, n);
                B=create_matrix(B, n, m);
                init_matrix_rnd(B, n, m);
                Y=create_matrix(Y, n, m);
    
                start=clock();
    
    			calc_challenge_ss2013(L, B, Y, n, m);
    
                end=clock();
    
                free_matrix(L, n);
                free_matrix(B, n);
                free_matrix(Y, n);
    
                fprintf(datei,"%i\t%.3f\n", n,(float)(end-start)/CLOCKS_PER_SEC);
    
    		}
    	}
    
        fclose(datei);
        printf("\n");
    }
    


  • das sieht doch schon wesentlich bessser aus. 🙂

    double** create_matrix (double** M, unsigned zeilen, unsigned spalten)
    double** create_l_matrix (double** M, unsigned zeilen)

    hier ist der parameter M in der parameterliste jeweils sinnbefreit. den kannst du weglassen und stattdessen lokal in der funktion anlegen.

    in c braucht man den rückgabewert von malloc, calloc nicht zu casten.
    bei manchen c-programmieren ist so ein cast sogar verpönt.
    in c++ allerdings muss man casten.



  • die funtion calc_challenge_ss2013 würde ich in zwei separate funktionen aufteilen(inversion, multiplikation).

    den rückgabewert von calloc solltest du auf NULL checken und bei NULL entsprechend reagieren, um programmabstürze aufgrund speichermangel zu vermeiden.
    dann ließe sich das programm bei speichermangel noch sauber beenden, in deinem fall würde es lediglich kläglich abkacken.
    🙂


Log in to reply