Ошибки памяти для Sieve of Eratosthenes, который выделяет память в стеке и куче - PullRequest
Новая
       88

Ошибки памяти для Sieve of Eratosthenes, который выделяет память в стеке и куче

0 голосов
/ 23 сентября 2019

Я реализовал приведенную ниже версию Решета Эратосфена, которая выделяет память в куче для хранения массива, представляющего простые числа. 

void sieve(int *primes, int n) {
   for (int i = 0; i < n - 1; i++) {
      primes[i] = 1;
   }

   for (int p = 2; p <= n; p++) {
      if (primes[p - 2] == 1) {
         for (int i = 2*p - 2; i < n; i += p) {
            primes[i] = 0;
         }
      }
   }
}

void print_sieves(int n) {
   if (n < 3) return;

   int *primes = (int*) malloc((n - 1) * sizeof(int));
   sieve(primes, n);
   int print_counter = 0;

   for (int i = 0; i < n - 1; i++) {
      if (primes[i] == 1) {
         printf("%10d ", i + 2);
         print_counter++;

         if (print_counter % COLUMNS == 0)
            printf("\n");
      }
   }
   free(primes);
   printf("\n");
}

Для большинства аргументов, передаваемых в print_sieves программуРаботает, как и ожидалось, при передаче 15 в print_sieves я получаю следующую ошибку: 

a.out: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)

Для немного другой версии этой программы, в которой вместо этого я выделяю память в стекечтобы сохранить массив, представляющий простые числа, я сталкиваюсь с другой ошибкой.А именно, при попытке найти слишком большие простые числа, например при вызове print_sieves с аргументом 10000000, я сталкиваюсь с ошибкой Segmentation fault (core dumped).Реализации sieve идентичны для обеих версий программы, но print_sieves имеют небольшие различия.Ниже приведен код для моей print_sieves функции, которая выделяет память в стеке: 

void print_sieves(int n) {
   if (n < 3) return;

   int primes[n - 1];
   sieve(primes, n);
   int print_counter = 0;

   for (int i = 0; i < n - 1; i++) {
      if (primes[i] == 1) {
         printf("%10d ", i + 2);
         print_counter++;

         if (print_counter % COLUMNS == 0)
            printf("\n");
      }
   }
   printf("\n");
}

Я предполагаю, что я не управляю памятью должным образом, но я не знаю, где я иду неправильно.Что может быть причиной этих ошибок и как их можно устранить?

1 Ответ

0 голосов
/ 23 сентября 2019

Поскольку вы выделяете память для n - 1 элементов, я предлагаю изменить самый внутренний цикл в sieve() с 

         for (int i = 2*p - 2; i < n; i += p) {

на 

         for (int i = 2*p - 2; i < n - 1; i += p) {

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

С n = 10000000 вы, скорее всего, получите переполнение стека.

Вы можете использовать getrlimit() / setrlimit(), чтобы получить / установить размер стека.Может быть трудно рассчитать предел для размера массива из максимального размера стека, потому что вам придется выяснить, какой объем стека необходим помимо большого массива.

См. Также Увеличение размера стека в Linuxс setrlimit

...