mrks Geschrieben 8. Mai 2021 Teilen Geschrieben 8. Mai 2021 Hallo Zusammen, ich bin hier neu und möchte euch von meinen neusten Erfahrungen berichten. Gerade ist mein Versuch, eine Art Zeit-Messung für einen Counting-Sort-Algorithmus durchzuführen. Dass die Zeit bisher noch nicht in Sekunden ausgegeben wird, sei erstmal beiseite gestellt, denn sobald der maximale Wert, der sortiert werden soll auf 128.000.000 wechselt, dumpt der Core und ich nehme an, dass das was mit dem allokierten Speicherplatz zu tun hat, kann mir aber nach gut einer Woche Fehlersuche einfach nicht mehr weiterhelfen. Deshalb komme ich mit meiner Frage mal auf euch zu, in der Hoffnung, ihr könnt mir meinen Fehler aufzeigen. kurz zum Code: Es ist eine Programmieraufgabe - die Werte habe ich mir nicht selbst ausgesucht. Es werden automatisiert Zufallszahlen erzeugt, die dann vom Algorithmus nach Größe sortiert werden sollen. Nach dem Ausschlussverfahren habe ich festgestellt, dass der Fehler in: int* countingSort(int* values, int length, int maxval); stehen muss. Der BubbleSort, der auch zu der Aufgabe gehört funktioniert tadellos. Ich zeige euch dazu am besten mal den (aufs wichtigste gekürzten) Code. Er ist lauffähig, kann also kopiert und kompiliert werden Vielen herzlichen Dank schonmal, dass ihr euch die Mühe macht! P.S. Bitte seht es mir nach, wenn ich gegen einen Verhaltenskodex für Foren verstoßen habe, ich bin nicht so oft in Foren unterwegs. #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <math.h> #include <time.h> // Funktionsdeklarationen void doSortByCounting(); // Countingsort void testCountingsort(int valueCount, int minVal, int maxVal); int* countingSort(int* values, int length, int maxval); // Für Zufallszahl unsigned int rand32BitInt(); int* createRandomValues(int minval, int maxval, int length); // Main Funktion int main() { doSortByCounting(); } // Ausgabe im Terminal über die Laufzeiten des Sortieralgorithmus void doSortByCounting() { printf("\n\n\n\t| Countingsort |\n"); printf("\t|----------------------|\n\n"); int i; int j; int k; // Variablen für die Stoppuhr clock_t start_t; clock_t end_t, end[3]; // Arrays für den automatischen Ablauf int iAnzahl[6]; iAnzahl[0] = 1000000; iAnzahl[1] = 2000000; iAnzahl[2] = 4000000; iAnzahl[3] = 8000000; iAnzahl[4] = 16000000; iAnzahl[5] = 32000000; int iMaxVal[2]; iMaxVal[0] = 1000000; iMaxVal[1] = 128000000; printf(" length\t maxVal\t| Messung 1\tMessung 2\tMessung 3\n"); for (i = 0; i <2; i++) { for (k = 0; k<6; k++) { for (j = 0; j < 3; j++) { start_t = clock(); testCountingsort(iAnzahl[k], 0, iMaxVal[i]); end_t = clock(); end[j] = end_t - start_t; fflush(stdout); } printf("%10d \t %10d \t| %5ld \t %5ld \t %5ld\n", iAnzahl[k], iMaxVal[i], end[0], end[1], end[2]); } } } // testCountingsort void testCountingsort(int valueCount, int minVal, int maxVal) { int *pRandom; int *pSorted; pRandom = createRandomValues(minVal, maxVal, valueCount); pSorted = countingSort(pRandom, valueCount, maxVal); free(pRandom); free(pSorted); } // Countingsort int* countingSort(int* values, int length, int maxval) { // values sind die Zufallszahlen // length bezeichnet die Anzahl der Werte in values // maxval ist der größte Wert der Zufallswerte int i; int *pSort; int iCountArray[maxval+1]; // Speicher allokieren pSort = (int *) calloc (length, sizeof(int)); // CountArray leeren for (i = 0; i<=maxval; i++) { iCountArray[i] = 0; } // Werte im iCountArray zählen for (i = 0; i<length; i++) { iCountArray[values[i]]++; } // Werte im CountArray aufsummieren for (i = 1; i<=maxval; i++) { iCountArray[i] += iCountArray[i-1]; } // Werte aus dem CountArray sortieren und ins iSortedArray einfügen for (i = 0 ;i <length; i++) { pSort[iCountArray[values[i]]-1] = values[i]; iCountArray[values[i]]--; } return pSort; } // Zufällige Zahl an Bedingungen anpassen int* createRandomValues(int minval, int maxval, int length) { int *pValues; double dDouble; unsigned int uRand; // Übergangsvariable, bis die Berechnung hinhaut double dRand; // Übergangsvariable, die uRand zu einer double konvertiert double dUint = (double) UINT_MAX; // Speicherplatz Allokieren pValues = (int *) malloc(length * sizeof(int)); // Zufallszahl verrechnen und an die vorgegebenen Werte anpassen for (int i = 0; i <length; i++) { // Funktion Zufallsgenerator aufrufen uRand = rand32BitInt(); // Aus dem unsigned int eine double erzeugen dRand = (double) uRand; // Den double-Wert zu einem Wert zwischen 0 und 1 erzeugen dDouble = ( dRand / dUint ); // Die Zufallszahl an den gegebenen Wertebereich anpassen // Wert zu einem int konvertieren und den Pointer dorthin zeigen lassen. pValues[i] = ( (double) maxval+1 - (double) minval ) * dDouble + (double) minval; } return pValues; } // Zufällige 32-Bit-Zahl erzeugen unsigned int rand32BitInt() { // Variablen für Zufallszahlen int uCreated8Bit[4]; // 4x 8-Bit Zahl werden mit Bitshifting auf unsigned int uCreated32Bit = 0; // 1x 32-Bit Zahl addiert. unsigned int uMask = 255; // Bitmaske für das Reduzieren der Zahlen auf die 8 least significant Bits. unsigned int uRand; // Ausgabe zu Testzwecken //printf("for-Schleife rand32\n\n"); // 4 Zufallszahlen werden erzeugt. for(int i = 0; i<4; i++) { // Erzeuge eine Integer Zufallszahl uCreated8Bit[i] = rand(); // Reduziere die Zahl auf die 8 least significant Bits mithilfe einer UND-Verknüpfung mit der Bitmaske uRand = uCreated8Bit[i] & uMask; // Summation der 8-Bit-Zahlen auf die 32-Bit-Zahl uCreated32Bit += uRand; // Nach der Summation wird die Zahl 8 Bits nach links geschoben - außer bei der letzten. if(i<3) uCreated32Bit = (unsigned int) uCreated32Bit<<8; } return uCreated32Bit; } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Jana309 Geschrieben 8. Mai 2021 Teilen Geschrieben 8. Mai 2021 Hallo mrks, willkommen im Forum. Ich weiß nicht welchen compiler du benutzt, aber bei mir compiliert dein code so nicht, weil ein Array mit nicht konstaner Länge ("int iCountArray[maxval+1]") verwendet wird. Wenn ich die entsprechende Stelle auf dynamische Allokierung ändere, läuft dein Code und ich sehe den gleichen Fehler wie du. Ich gehe mal davon aus, dass dein compiler irgendwie automatisch dynamisch allokiert? zum Fehler: Der Versuch den Speicher für den Array iCountArray zu allokieren schlägt fehl (calloc liefert Null zurück) und die anschließende Verwendung des Array löst den Zugriffsfehler aus. Ich denke das liegt am Speicherlimit für x86-Anwendungen (unter Windows, auch 64bit-Windows sind das standardmäßig 2GB). An der Stelle, an der die 2GB überschritten werden, tritt der Fehler auf. Dass 2GB überschritten werden, liegt daran, dass der Speicher von iCountArray zwar allokiert aber nie wieder freigegeben wird. Wenn man auf x64 umstellt läuft das Programm ohne Fehler durch (benötigt am Ende ca. 10GB RAM, Das meiste davon sind Memoryleaks) Wenn man den Speicher von iCountArray jedes mal wieder freigibt, läuft das Programm auch als x86-Anwendung fehlerfrei. hoffe, das hilft dir weiter. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
mrks Geschrieben 8. Mai 2021 Autor Teilen Geschrieben 8. Mai 2021 Hallo Jana, vielen Dank für deine Antwort, sie war sehr hilfreich und ich habe mein Problem lösen können! ich habe aus dem "int iCountArray[a]" einen Pointer gemacht, speicher allokiert und ihn am Schluss wieder freigegeben und jetzt läuft es! Hab ein ganz wundervolles Wochenende! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.