Suggerimento per l'eccezione stackoverflow chkstk.asm in C++ con Visual Studio

Question

Sto lavorando con un'implementazione di merge sort. Sto provando con C++ Visual Studio 2010 (msvc). Ma quando ho preso un array di 300000 interi per il timing, mostra un'eccezione di stackoverflow non gestita e mi porta a un file di sola lettura chiamato "chkstk.asm". Ho ridotto la dimensione a 200000 e ha funzionato. Di nuovo lo stesso codice ha funzionato con C-free 4 editor (mingw 2.95) senza alcun problema mentre la dimensione era 400000. Hai qualche suggerimento per far funzionare il codice in Visual Studio?

Potrebbe essere la ricorsione nel mergesort a causare il problema.

Answer 1

Problema risolto. Grazie a Kotti per aver fornito il codice. Ho avuto il problema durante il confronto con quel codice. Il problema non era la troppa ricorsione. In realtà stavo lavorando con un normale array C++ che veniva memorizzato nello stack. Quindi il problema ha esaurito lo spazio di stack. L'ho appena modificato in una matrice allocata dinamicamente con le istruzioni new/delete e ha funzionato.

Answer 2

La mia ipotesi è che si abbia così tanto ricorsione che si sta appena esaurendo lo spazio di stack. Puoi aumentare le dimensioni dello stack con lo linker's /F command line option. Ma se continui a colpire i limiti della dimensione dello stack, probabilmente vuoi rifattorizzare la ricorsione dal tuo algoritmo.

Answer 3

Non sono esattamente sicuro, ma potrebbe trattarsi di un problema particolare dell'implementazione di un ordinamento di tipo merge (che causa uno stack overflow). Ci sono un sacco di buone implementazioni (usare google), le seguenti opere in VS2008 con dimensione di matrice = 2000000.

(si potrebbe provare in VS2010)

#include <cstdlib> 
#include <memory.h> 

// Mix two sorted tables in one and split the result into these two tables. 
void Mix(int* tab1, int *tab2, int count1, int count2) 
{ 
    int i,i1,i2; 
    i = i1 = i2 = 0; 
    int * temp = (int *)malloc(sizeof(int)*(count1+count2)); 

    while((i1<count1) && (i2<count2)) 
    { 
     while((i1<count1) && (*(tab1+i1)<=*(tab2+i2))) 
     { 
     *(temp+i++) = *(tab1+i1); 
     i1++; 
     } 
     if (i1<count1) 
     { 
     while((i2<count2) && (*(tab2+i2)<=*(tab1+i1))) 
     { 
      *(temp+i++) = *(tab2+i2); 
      i2++; 
     } 
     } 
    } 

    memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int)); 
    memcpy(tab1,temp,count1*sizeof(int)); 

    memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int)); 
    memcpy(tab2,temp+count1,count2*sizeof(int)); 
    free(temp); 
} 

void MergeSort(int *tab,int count) { 
    if (count == 1) return; 

    MergeSort(tab, count/2); 
    MergeSort(tab + count/2, (count + 1) /2); 
    Mix(tab, tab + count/2, count/2, (count + 1)/2); 
} 

void main() { 
    const size_t size = 2000000; 
    int* array = (int*)malloc(sizeof(int) * size); 
    for (int i = 0; i < size; ++i) { 
     array[i] = rand() % 5000; 
    } 

    MergeSort(array, size); 
}