Предложение для исключения chkstk.asm stackoverflow в C ++ с Visual Studio - PullRequest
Новая
       30

Предложение для исключения chkstk.asm stackoverflow в C ++ с Visual Studio

10 голосов
/ 14 мая 2010

Я работаю с реализацией сортировки слиянием. Я пытаюсь с C ++ Visual Studio 2010 (MSVC). Но когда я взял массив из 300000 целых чисел для измерения времени, он показывает необработанное исключение stackoverflow и переносит меня в файл только для чтения с именем "chkstk.asm". Я уменьшил размер до 200000, и это сработало. Опять же, тот же код работал без проблем с редактором C-free 4 (mingw 2.95), пока его размер был 400000. У вас есть какие-либо предложения, чтобы заставить код работать в Visual Studio?

Может быть, рекурсия в слиянии вызывает проблему.

Ответы [ 3 ]

12 голосов
/ 15 мая 2010

Проблема решена. Спасибо Котти за предоставление кода. У меня проблема при сравнении с этим кодом. Проблема была не в слишком большой рекурсии. На самом деле я работал с обычным массивом C ++, который хранился в стеке. Таким образом, проблема исчерпала пространство стека. Я просто изменил его на динамически размещенный массив с операторами new / delete, и он работал.

5 голосов
/ 14 мая 2010

Я не совсем уверен, но это может быть особой проблемой вашей реализации сортировки слиянием (которая вызывает переполнение стека). Есть много хороших реализаций (используйте google), следующие работают на VS2008 с размером массива = 2000000.

(Вы можете попробовать это в 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);
}
5 голосов
/ 14 мая 2010

Полагаю, у вас так много рекурсии, что вам просто не хватает места в стеке.Вы можете увеличить свой размер стека с помощью опции командной строки компоновщика.Но если вы продолжаете устанавливать ограничения на размер стека, вы, вероятно, захотите реорганизовать рекурсию из вашего алгоритма.

...