Suggestion pour l'exception stackoverflow chkstk.asm en C ++ avec Visual Studio

Je travaille avec une mise en œuvre de la fusion de tri. Je suis en train d'essayer avec C++ Visual Studio 2010 (msvc). Mais quand j'ai fait un tableau de 300000 entiers pour le moment, il est en montrant une non gérée stackoverflow exception et me prendre pour un fichier en lecture seule nommé "chkstk.asm". J'ai réduit la taille de 200000 et cela a fonctionné. De nouveau le même code a travaillé avec C-gratuit 4 de l'éditeur (mingw 2.95) sans aucun problème alors que la taille a été 400000. Avez-vous une suggestion à faire fonctionner le code dans Visual Studio?

Peut-être la récursivité dans le mergesort est à l'origine du problème.

source d'informationauteur Gulshan

  1. 11

    Le problème est résolu. Grâce à Kotti pour fournir le code. J'ai eu le problème en comparant avec ce code. Le problème n'était pas trop de la récursivité. En fait, je travaillais avec un normal C++ tableau qui a été stocké sur la pile. Ainsi, le problème a couru hors de la pile de l'espace. J'ai juste changé d'un tableau alloué dynamiquement avec la new/delete, et cela a fonctionné.

  2. 5

    Ma conjecture est que vous avez tellement de récursivité que vous êtes tout simplement en cours d'exécution hors de l'espace de pile. Vous pouvez augmenter la taille de votre tapis avec le linker /F option de ligne de commande. Mais, si vous continuez à frapper taille de la pile des limites que vous avez probablement envie de revoir la récursivité de votre algorithme.

  3. 5

    Je ne suis pas sûr, mais cela peut être un problème particulier de votre mise en œuvre de yor fusion de tri (qui provoque un débordement de pile). Il y a beaucoup de bonnes implémentations (utilisation de google), les travaux suivants sur VS2008 avec la taille du tableau = 2000000.

    (Vous pouvez l'essayer dans 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);
}