Алгоритм C ++ Sieve of Eratosthenes приводит к переполнению стека

Я работал над простым алгоритмом Сита Эратосфена, и его код приведен ниже:

int main()
{

    const int n = 1000000;

    int sqrn = floor(sqrt(n));

    bool primes[n + 1] = { 0 }; // false means prime, true not prime

    primes[0] = true;
    primes[1] = true;

    for (int i = 2; i <= sqrn; i++){

        if (primes[i] == false) {
            int j = i + i;
            while (j<=n-1){
                primes[j] = true;
                j = j + i;
            }
        }
    }
}

Мой главный вопрос заключается в том, что этот код приводит к ошибке переполнения стека, если я пытаюсь установить массив поиска больше, чем n = 1000000. Я не уверен, что это из-за ошибки программирования или из-за того, что программа не может содержать логический массив размером более 10 ^ 6 записей? Любой совет приветствуется.

Другой второстепенный вопрос, который у меня есть, заключается в том, увеличивает ли скорость выполнения установка вычисления квадратного корня из n вне оператора цикла for.

Спасибо


c++ algorithm primes sieve-of-eratosthenes
person virtore    schedule 29.04.2014    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Вместо bool primes[n + 1] = { 0 }; выполните:

std::vector<bool> primes(n+1);

Это выделяет пространство вне стека для достаточного количества простых чисел и инициализирует их все равным false.

Эта версия имеет еще одно преимущество в том, что компилятор может специализировать ее на использование одного бита на значение, тогда как ваша версия использует один байт на значение.

Аналогичная альтернатива, которая может иметь лучшую производительность (но возможна только в том случае, если размер известен во время компиляции), является

std::bitset<n+1> primes;

Если вы посмотрите его документацию, вы сможете улучшить производительность своего кода.

person M.M    schedule 29.04.2014
comment
Спасибо. Векторный метод, кажется, хорошо работает для больших n. Bitset также использует стек? - person virtore; 29.04.2014
comment
Стандарт C ++, похоже, не говорит, использует ли bitset автоматическое выделение или выделение свободного хранилища для своих битов. Может быть разрешено использовать автоматическое хранилище (также известное как стек), поэтому, возможно, вам следует придерживаться vector. - person M.M; 29.04.2014
comment
просто любопытно, есть ли способ разместить вектор в стеке вместо кучи? - person Namit Sinha; 29.04.2014
comment
Нет, было бы невозможно изменить размер вектора во время выполнения, если бы векторы работали таким образом - person M.M; 29.04.2014

arrow_upward
2
arrow_downward

Вы размещаете массив primes в стеке. Стек имеет ограниченный размер (он довольно большой, но все еще ограничен). Вы также можете:

  • разместить свой массив в области глобальных данных или
  • разместите свой массив в куче с помощью new
person Greg Hewgill    schedule 29.04.2014

arrow_upward
1
arrow_downward

Вероятно, переполнение стека связано с тем, что размер вашего стека не превышает 1 МБ (или 1 МБ в зависимости от вашего определения). bool обычно составляет 1 байт. Попробуйте выделить массив простых чисел в куче (используя new[]), чтобы избежать ограничения размера стека. Не забудьте освободить массив с помощью delete[].

Также примитивность n будет неверной из этого алгоритма. Вы хотите изменить j<=n-1 на j<=n.

person John Colanduoni    schedule 29.04.2014
comment
В целом, сколько места доступно в стеке? Зависит ли это от системы, в которой работает код? - person virtore; 29.04.2014
comment
@virtore Да, это во многом зависит от вашей среды выполнения C ++. Его можно расширить разными способами в зависимости от платформы. Например, программы Win32 могут устанавливать размер стека нового потока, когда поток создается с помощью CreateThread, а при использовании потоков POSIX в Linux с pthread_attr_setstacksize. Однако я бы просто выделил большой объем памяти в куче; выделение такого большого стека расточительно и затрудняет восстановление памяти. - person John Colanduoni; 30.04.2014