4. Overflow ? Programm stürzt ab

Overflow ? Programm stürzt ab

  • R

    Hallo,
    ich hab ein Programm geschrieben, daß die Laufzeit von verschiedenen Sortier-Algorithmen vergleichen soll, hier mal der Code soweit :

    #include <stdio.h>
#include <time.h>
#define MAX 500000
#define INFINITE 2147483647

/*============================================================================*/

void insert_sort( int nums[], int size );
void merge_sort ( int nums[], int low, int high );
void merge ( int* nums, int low, int m, int high );

/*============================================================================*/

void insert_sort( int nums[], int size ) {
   int j,k,key;
   for ( j=1; j<size; j++ ) {
       key = nums[j];
       k = j-1;
       while ( (k >= 0) && (nums[k] > key) ) {
          nums[k+1] = nums[k];
          --k;
       }
       nums[k+1] = key;
   }
}

/*============================================================================*/

void merge_sort ( int nums[], int low, int high ){
     int m;
     if ( low < high ) {
        m = (low+high) / 2;
        merge_sort (nums,low,m);
        merge_sort (nums,m+1,high);
        merge (nums,low,m,high);
     }
}

/*============================================================================*/

void merge ( int* nums, int low, int m, int high ) {
     int i, j, k, size_l=m-low+1, size_r=high-m;

     int* left = (int*) malloc((size_l+1) * sizeof(int));
     int* right = (int*) malloc((size_r+1) * sizeof(int));

     for (i=0; i<=size_l-1; i++)
         left[i] = nums[low+i];
     for (j=0; j<=size_r-1; j++)
         right[j] = nums[m+j+1];

     left[size_l] = INFINITE;
     right[size_r] = INFINITE;
     i = j = 0;

     for (k=low; k<=high; k++) {
         if ( left[i] <= right[j] ) {
            nums[k] = left[i]; i++;
         }
         else {
            nums[k] = right[j]; j++;
         }
     }
}

/*============================================================================*/

int main () {

    int i;
    float zeit;
    clock_t start, ende;
    int nums[MAX];

    for ( i=0; i<MAX; i++)  // Zufallszahlen werden in das Feld geschrieben
        nums[i] = rand();

    // Laufzeitbestimmung des Insertion-Sort
    start = clock();
    insert_sort (nums,MAX);
    ende = clock ();
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Laufzeit des Insertion-Sort bei %d Zahlen = %2.2f Sekunden \n", MAX, zeit);

    for ( i=0; i<MAX; i++)  // Das bereits sortierte Feld wird wieder mit neuen Zahlen belegt
        nums[i] = rand();

    // Laufzeitbestimmung des Merge-Sort
    start = clock();
    merge_sort (nums,0,MAX-1);
    ende = clock();
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Laufzeit des Merge-Sort bei %d Zahlen = %2.2f Sekunden \n", MAX, zeit);

    system("PAUSE");
    return 0;
}

    Wenn ich für MAX Zahlen größer als 1.000.000 eingebe, stürzt das Programm ab (Hab den Insertion-Sort nur bis 200.000 mitlaufen lassen, da warens schon 70 Sekunden). Ich soll später noch eine Funktion dazuschreiben, die den Merge-Sort benutzt, aber zum Insertion-Sort überspringt sobald die Hilfsfelder weniger als 7 Elemente haben (und diese dann sortiert). Und um die Laufzeit dann vergleichen zu können muß ich weit über 1 Million (sind bei 500.000 knapp eine Sekunde beim Merge Sort). Jemand ne Idee worans liegt, und ob/wie ichs beheben kann ?

    0
  • R

    wahrscheinlich ist der Stack zu klein für 1000000*sizeof(int) Elemente. Da bleibt dir nur Heap allokierung (mit malloc/free). Wenn du nicht weisst wie das geht, siehe dein lieblings C Buch oder die FAQ

    0
  • R

    😕

    versteh ich jetzt nicht ganz 🙂 eigentlich wird doch dynamisch immer genug Speicher für die Hilfs-Stacks bereitgestellt. Liegts am Arbeitsspeicher ?

    0
  • M

    raffnix schrieb:

    eigentlich wird doch dynamisch immer genug Speicher für die Hilfs-Stacks bereitgestellt.

    Das mag sein. Aber dein Ausgangs-Array nums liegt auf dem Stack. Und da ist der Platz begrenzt.

    Liegts am Arbeitsspeicher ?

    Nein, die Stackgröße hängt i.d.R. nicht von der Größe des Arbeitsspeichers ab.

    0
  • R

    Mhhhh, OK.
    Wie könnt ich das in diesem speziellen Falle lösen ? Hab in der FAQ nichts darüber gefunden. Wenn die Implementierung zu kompliziert sein sollte, dann spart euch bitte die Mühe 🙂 So immens wichtig ist es auch nicht, könnte ja als alternative einfach das Feld 100mal durcheinanderwürfeln und wieder neu sortieren, und dann die Zeit messen *g*

    0
  • M

    Du ersetzt einfach

    int nums[MAX];

    durch

    int* nums = malloc(MAX * sizeof(int));

    und änderst den ersten Parameter von insert_sort und merge_sort in int* nums.

    Am Ende aber free nicht vergessen... 😉

    0
  • R

    OK, soweit funktioniert es jetzt 😉 danke
    Aber die Ergebnisse verwundern mich doch jetzt schon sehr:
    Schon bei nem Feld der Größe 3.000.000 dauert der merge/insert-sort deutlich länger als der normale merge-sort 😮 . Ich war eigentlich der Überzeugung, daß der Mix aus Merge- und Insert-Sort bei größeren Feldern ne kleinere Laufzeit hat 🙂 Hab ich da vielleicht nen entscheidenden Denkfehler bei der Funktion gemacht ? Ist eigentlich so gedacht, dass Hilfs-Felder mit weniger als 7 Elementen mit dem insert-sort sortiert, und wieder eingefügt werden. Ich poste einfach nochmal den Code...

    #include <stdio.h>
#include <time.h>
#define MAX 3000000
#define INFINITE 2147483647

/*============================================================================*/

void insert_sort( int nums[], int size );
void merge_sort ( int nums[], int low, int high );
void merge ( int* nums, int low, int m, int high );
void merge_insert ( int nums[], int low, int high );

/*============================================================================*/

void insert_sort( int* nums, int size ) {
   int j,k,key;
   for ( j=1; j<size; j++ ) {
       key = nums[j];
       k = j-1;
       while ( (k >= 0) && (nums[k] > key) ) {
          nums[k+1] = nums[k];
          --k;
       }
       nums[k+1] = key;
   }
}

/*============================================================================*/

void merge_sort ( int* nums, int low, int high ){
     int m;
     if ( low < high ) {
        m = (low+high) / 2;
        merge_sort (nums,low,m);
        merge_sort (nums,m+1,high);
        merge (nums,low,m,high);
     }
}

/*============================================================================*/

void merge ( int* nums, int low, int m, int high ) {
     int i, j, k, size_l=m-low+1, size_r=high-m;

     int* left = (int*) malloc((size_l+1) * sizeof(int));
     int* right = (int*) malloc((size_r+1) * sizeof(int));

     for (i=0; i<=size_l-1; i++)
         left[i] = nums[low+i];
     for (j=0; j<=size_r-1; j++)
         right[j] = nums[m+j+1];

     left[size_l] = INFINITE;
     right[size_r] = INFINITE;
     i = j = 0;

     for (k=low; k<=high; k++) {
         if ( left[i] <= right[j] ) {
            nums[k] = left[i]; i++;
         }
         else {
            nums[k] = right[j]; j++;
         }
     }
}

/*============================================================================*/

void merge_insert ( int* nums, int low, int high ) {
     int m;
     if ( low < high && high-low > 6 ) {
        m = (low+high) / 2;
        merge_sort (nums,low,m);
        merge_sort (nums,m+1,high);
        merge (nums,low,m,high);
     }
     else insert_sort ( nums, high-low);
}

/*============================================================================*/

int main () {

    int i;
    float zeit;
    clock_t start, ende;
    int* nums = malloc(MAX * sizeof(int));

    for ( i=0; i<MAX; i++)  // Zufallszahlen werden in das Feld geschrieben
        nums[i] = rand();
    /*

    // Laufzeitbestimmung des Insertion-Sort
    start = clock();
    insert_sort (nums,MAX);
    ende = clock ();
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Laufzeit des Insertion-Sort bei %d Zahlen = %2.2f Sekunden \n", MAX, zeit);

    for ( i=0; i<MAX; i++)  // Das bereits sortierte Feld wird wieder mit neuen Zahlen belegt
        nums[i] = rand();

    */

    // Laufzeitbestimmung des Merge-Sort
    start = clock();
    merge_sort (nums,0,MAX-1);
    ende = clock();
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Laufzeit des Merge-Sort bei %d Zahlen = %2.2f Sekunden \n", MAX, zeit);

    for ( i=0; i<MAX; i++)  // Das bereits sortierte Feld wird wieder mit neuen Zahlen belegt
        nums[i] = rand();

    // Laufzeitbestimmung des Merge-Insert-Sort
    start = clock();
    merge_insert (nums,0,MAX-1);
    ende = clock();
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Laufzeit des Merge-Insert-Sort bei %d Zahlen = %2.2f Sekunden \n", MAX, zeit);

    free(nums);

    system("PAUSE");
    return 0;
}
    0
  • C

    Ich sehe 2 Fehler in Deinem Programm:

    1. In der Funktion merge hast Du 2-mal malloc drin, aber nie ein free. Bei 3 Millionen zu sortierenden Zahlen erzeugst Du damit riesige memory-leaks, so dass Dein RAM voll ist, wenn der Test von merge_insert beginnt. Dein OS beginnt Speicher auszulagern, wodurch alles langsamer wird.

    2. Die Funktion merge_insert ruft nicht sich selbst rekursiv auf, sondern die Funktion merge_sort.

    Gruss Chris

    0
  • R

    lol, das hab ich jetzt davon, daß ich copy/paste gemacht und die funktion nur ein bissl verändert hab... und jetzt belegt das Programm auch keine 1,5GB virtuellen Speicher mehr 😃
    danke für all die Hilfe

    0
Anmelden zum Antworten