Решето Эратосфена с СТД::вектор


Как я могу улучшить и оптимизировать этот код?

#include <iostream>
#include <vector>

std::vector<bool> sieve_of_eratosthenes(int n)
{
    std::vector<bool> primes(n+1, true);
    primes[0] = false;
    primes[1] = false;

    for (int i = 2; i <= n; i++)
    {
        if (primes[i] == true)
        {
            for (int j = i * 2; j <= n; j += i)
            {
                primes[j] = false;
            }
        }
    }
    return primes;
}

int main()
{
    int n;
    std::cout << "Enter number :\n";
    std::cin >> n;
    std::vector<bool> result = sieve_of_eratosthenes(n);
    std::cout << "Prime numbers upto " << n << " is :\n";
    for (int i = 0 ; i < result.size(); i++)
    {
        if (result[i] == true)
        {
            std::cout << i << " ";
        }
    }
    std::cout << '\n';
}


339
4
задан 14 апреля 2018 в 08:04 Источник Поделиться
Комментарии
4 ответа

Я вижу несколько вещей, которые могут помочь вам улучшить вашу программу.

Будьте осторожны с подписанное и неподписанное

Если отрицательное число передается sieve_of_eratosthenes функция, маловероятно, чтобы произвести полезные результаты. По этой причине, имеет смысл отвергать отрицательные числа при получении значения от пользователя и/или объявить функцию, чтобы принимать только unsigned.

Рассмотрим пользователей

А не требуют интерактивной сессии, было бы удобно указать номер в командной строке. Кроме того, грамматически, мне кажется, что стоит сказать, "простых чисел до n являются:"

Уменьшить количество итераций

Другие, чем 2, только нечетные числа возможных простых чисел. По этой причине, я предлагаю изменить инициализации этого:

std::vector<bool> primes(n+1);
primes[2] = true;
// all odd numbers are possible primes
for (unsigned i = 3; i <= n; i+=2) {
primes[i] = true;
}

Обратите внимание, что primes(n+1) инициализирует весь вектор falseпри изменении инициализации исходного кода.

Нужно только перебрать до \$\функция sqrt{н}\$ для внешнего цикла. Некоторые думают о том, что должны показать, почему это так.

В подобном ключе мы можем начать внутренний цикл со значением i * i потому что меньше нескольких уже были зачеркнуты.

Альтернативные представления тест на производительность

Он часто утверждал, что некоторые другие представления, такие как std::vector<std::byte> или std::vector<char> будет быстрее, чем std::vector<bool>. Интуитивно в этом есть определенный смысл, потому что std::vector<bool> делать упаковки и распаковки битов, чтобы открыть. Однако эта интуиция не всегда корректны из-за эффектов кэширования. То есть, это часто быстрее, чтобы делать сложные манипуляции в кэше, чем это, чтобы сделать простые операции на области памяти, не в кэше. Мы можем догадываться, но лучший способ-это проверить его на вашу машину с вашим компилятором. Для упрощения такого тестирования, я использовал этот код:

#include <iostream>
#include <vector>
#include <cmath>

#if 0
#include <cstddef>
using mytype = std::byte;
#else
using mytype = bool;
#endif
constexpr mytype yes{1};
constexpr mytype no{0};

std::vector<mytype> sieve_of_eratosthenes(unsigned n) {
std::vector<mytype> primes(n+1);
primes[2] = yes;
// all odd numbers are possible primes
for (unsigned i = 3; i <= n; i+=2) {
primes[i] = yes;
}
// we only have to check up to the square root of the limit
unsigned limit = std::sqrt(n);
for (unsigned i = 3; i <= limit; i+=2) {
if (primes[i] == yes) {
const unsigned stride{2 * i};
for (unsigned j = i * i; j <= n; j += stride) {
primes[j] = no;
}
}
}
return primes;
}

int main(int argc, char *argv[]) {
if (argc != 2) {
std::cout << "Usage: primesUpTo n\n";
return 1;
}
int n{atoi(argv[1])};
if (n < 0) {
std::cout << "Error: the number must be positive\n";
return 2;
}
std::vector<mytype> result = sieve_of_eratosthenes(n);
std::cout << "Prime numbers up to " << n << " are:\n";
for (unsigned i = 0 ; i < result.size(); i++) {
if (result[i] == yes) {
std::cout << i << '\n';
}
}
std::cout << '\n';
}

С помощью bash скрипт, используя time и R на моей машине (64-битный Линукс коробки, используя GCC версия 7.3.1) я получаю следующие результаты, но помните, что ваши результаты могут отличаться, и поэтому я настоятельно призываю вас сделать свое собственное тестирование. В каждом из графиков, красная линия-версия через std::byte а зеленая линия-версию, используя std::bool. Как видите, в моем тестировании std::bool почти всегда выигрывает в обоих скорость выполнения и размер памяти.
timing results byte vs bool
memory results byte vs bool

2
ответ дан 15 апреля 2018 в 02:04 Источник Поделиться

Помимо прочих оптимизаций, если вы используете сито для проверки на простоту числа, можно оптимизировать дальше, каждый после 2-нечетное, поэтому любое четное число, не 2 не премьер. Это может легко быть проверено без сетки. Я бы предположил, что все четные числа ложных лишнее. Так Марк 2 как истинные и начало внешнего цикла на 3 и шага 2. Как уже было сказано, внутренний цикл может начинаться i*iи поскольку это будет нечетное число, Вам только нужно пометить любой другой несколько, поэтому вы можете увеличить на i*2. Что-то вроде этого:

std::vector<bool> sieve_of_eratosthenes(int n)
{
std::vector<bool> primes(n+1, true);
primes[0] = false;
primes[1] = false;
int limit = (int)sqrt(n) + 1;
for (int i = 3; i < limit; i += 2)
{
if (primes[i])
{
int step = i * 2;
for (int j = i * i; j <= n; j += step)
{
primes[j] = false;
}
}
}
return primes;
}

5
ответ дан 14 апреля 2018 в 09:04 Источник Поделиться

Не используйте странно vector<bool>. Используя вектор байт будет быстрее, и с помощью bitset даст вам компактность, если это было ваше намерение.

Пишу if (x==true) глупо.

Используйте равномерное инициализации:

std::vector<std::byte> primes { n+1, true };


редактировать: (vector есть инит-список конструктор в дополнение к другим конструкторам. Рекламируется как компонент при равномерном инит был произведен, на самом деле вызывает headscratching в комментарии код именно так, как я просто провалился в себя!)

использовать auto (практически везде):

auto result= sieve(n);

3
ответ дан 14 апреля 2018 в 08:04 Источник Поделиться

С j петли в sieve_of_eratosthenes вы можете начать в i * iпоскольку все кратные i с коэффициентами меньше, чем i будут уже сняты. И вы можете остановить i цикл при i * i > n (состояние, вы можете проверить, когда вы найти новый премьер, перед j петли).

3
ответ дан 14 апреля 2018 в 07:04 Источник Поделиться