Merge sort stürzt ab, wenn die Eingabegröße ausreichend groß ist

Question

Ich habe eine Reihe von wachsenden Eingabewerten, die ich die Laufzeit von analysieren möchte.

int main(){ 
    srand(time(NULL)); //initialize random num generator with time(NULL) as seed 
    int size_arr[7] = {1000, 10000, 25000, 50000, 100000, 150000, 200000}; 
// int size_arr[6] = {1000, 10000, 25000, 50000, 100000, 129992}; 
    int size = (sizeof(size_arr)/sizeof(int)); 

Das Eingabe-Array int size_arr[7] Werke für meine Quicksort und Implementierungen Insertionsort wenn übergibt ein Array mit den folgenden erstellt:

for(int k = 0; k < size; k++){ 
      double sort_arr[size_arr[k]]; 
      for(unsigned int l = 0; l < (sizeof(sort_arr)/sizeof(double)); l++){ 
       sort_arr[l] = random_double(100.00, 1000.00); 
      } 
} 

Mit den hier produzierten Doppel Werte:

double random_double(double min, double max){ 
    return (max - min) * ((double)rand()/(double)RAND_MAX) + min; 
} 

jedoch , wenn ich das Array durch meine Merge-Sortierfunktion ausführen:

//merge sort algorithm 
void merge_sort(double *A, int p, int r){ 

    if(p < r){      //stopping condition 
     int mid = floor((p + r)/2); //find array midpoint 
     merge_sort(A, p, mid);  //recursively divide array 
     merge_sort(A, mid+1, r); 
//  merge(A, p, mid, r);  //merge (sort) sub-arrays 
     merge_sort_merge(A, p, mid, r); 
    } 
} 

void merge_sort_merge(double *A, int left, int mid, int right){ 
    double tmp[right]; 
    int l = left, m = mid+1, sort_index = left; 
    for(int i = left; i <= right; i++){ 
     tmp[i] = A[i]; 
    } 
    while(l <= mid && m <= right){ 
     if(tmp[l] <= tmp[m]){ 
      A[sort_index] = tmp[l]; 
      l++; 
     }else{ 
      A[sort_index] = tmp[m]; 
      m++; 
     } 
     sort_index++; 
    } 
    while(l <= mid){ 
     A[sort_index] = tmp[l]; 
     sort_index++; 
     l++; 
    } 
} 

Es stürzt ab, wenn die Eingabegröße genau ist, 129992 (ich habe es mit der int size_arr[6] getestet).

Der vollständige Code ist wie folgt:

#include <iostream> 
#include <array> 
#include <math.h> 
#include <stdlib.h> 
#include <time.h> 
#include <exception> 

void merge_sort(double *A, int p, int r); 
void merge(double *A, int p, int q, int r); 
double random_double(double min, double max); 

int main(){ 
    srand(time(NULL)); //initialize random num generator with time(NULL) as seed 
    int size_arr[7] = {1000, 10000, 25000, 50000, 100000, 150000, 200000}; 
// int size_arr[6] = {1000, 10000, 25000, 50000, 100000, 129992}; 
    int size = (sizeof(size_arr)/sizeof(int)); 

    std::cout << "Merge Sort:" << std::endl; 
     for(int k = 0; k < size; k++){ 
      double sort_arr[size_arr[k]]; 
      for(unsigned int l = 0; l < (sizeof(sort_arr)/sizeof(double)); l++){ 
       sort_arr[l] = random_double(100.00, 1000.00); 
      } 
      clock_t begin = clock(); 
      try{ 
       merge_sort(sort_arr, 0, (sizeof(sort_arr)/sizeof(double))); 
      }catch(const std::runtime_error& re){ 
       std::cerr << "Runtime error: " << re.what() << std::endl; 
      }catch(const std::exception &exc){ 
       std::cerr << exc.what(); 
      }catch(...){ 
       std::cerr << "Fuck" << std::endl; 
      } 
      clock_t end = clock(); 
      std::cout << "n = " << size_arr[k] << '\t' << (end - begin) << std::endl; 
     } 

    return 0; 
} 

//merge sort algorithm 
void merge_sort(double *A, int p, int r){ 

    if(p < r){      //stopping condition 
     int mid = floor((p + r)/2); //find array midpoint 
     merge_sort(A, p, mid);  //recursively divide array 
     merge_sort(A, mid+1, r); 
//  merge(A, p, mid, r);  //merge (sort) sub-arrays 
     merge_sort_merge(A, p, mid, r); 
    } 
} 

void merge_sort_merge(double *A, int left, int mid, int right){ 
    double tmp[right]; 
    int l = left, m = mid+1, sort_index = left; 
    for(int i = left; i <= right; i++){ 
     tmp[i] = A[i]; 
    } 
    while(l <= mid && m <= right){ 
     if(tmp[l] <= tmp[m]){ 
      A[sort_index] = tmp[l]; 
      l++; 
     }else{ 
      A[sort_index] = tmp[m]; 
      m++; 
     } 
     sort_index++; 
    } 
    while(l <= mid){ 
     A[sort_index] = tmp[l]; 
     sort_index++; 
     l++; 
    } 
} 

double random_double(double min, double max){ 
    return (max - min) * ((double)rand()/(double)RAND_MAX) + min; 
} 

Ich habe versucht, Ausnahmen zu kontrollieren (es jede nicht geworfen hat), den VS JIT-Debugger kann aber keine nützlichen Informationen aus ihn heraus, die Demontage ist wie folgt (Pfeil nach Fehler):

00000000004100D0 cmp   rax,1000h 
00000000004100D6 ja   00000000004100BF 
00000000004100D8 sub   rcx,rax 
00000000004100DB or   qword ptr [rcx],0 <---- 
00000000004100DF pop   rax 
00000000004100E0 pop   rcx 

Es scheint unmöglich zu Schritt durch> 129K Rekursion, wie kann ich verengen, wo das Problem ist, wenn ich so große Eingangsgrößen haben?

Jede Hilfe ist

geschätzt

Answer 1

Wenn size_arr[k] == 129'992, die Größe der

double sort_arr[size_arr[k]]; 

ist 129'992 * sizeof(double) == 129'992 * 8 == 1'039'936. Dies ist nur schüchtern von 1'048'576 == 1M (binär Mega).

Der C-Standard sagt nicht, wo variable length arrays gespeichert sind (C++ definiert VLA überhaupt nicht), aber normalerweise werden sie auf dem Stapel zugeordnet.

den VS JIT

mit Impliziert, dass Sie Windows verwenden. Die Standard-Stackgröße für Windows ist 1MB. Die 8640 Bytes, die nicht von sort_arr verwendet werden, sind leicht durch den Rest Ihres Programms erschöpft (meistens durch tmp innerhalb merge_sort_merge, die in der Spitze wird die Größe von sort_arr sein). Mit anderen Worten, Sie überlaufen den Stapel.

Lösung: Verwenden Sie keine Arrays mit variabler Länge für große Arrays. (Verwenden Sie VLA nicht, wenn Sie es vorziehen, dass das Programm portabel und standardkonform ist). Verwenden Sie stattdessen dynamisch zugewiesene Arrays (std::vector).