质数低于20亿-使用std :: list会阻碍性能

Question

问题陈述是要在20秒钟内找到20亿以下的质数。我遵循以下方法。

1. 将数字n除以数字k的列表（k <sqrt（n）） -花费了20秒

2. 将数字n除以sqrt（n）以下的质数列表。在这种情况下，我将质数存储在std :: list中-花费了超过180秒的时间

有人可以帮助我理解为什么即使我们将除数都减少了50％（大约），第二种方法仍要花很长时间？还是我选择了错误的数据结构？

方法1：

#include <iostream>
#include<list>
#include <ctime>
using namespace std;

list<long long> primeno;
void ListPrimeNumber();

int main()
{
    clock_t time_req = clock();
    ListPrimeNumber();
    time_req = clock() - time_req;
    cout << "time taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds" << endl;
    return 0;
}

void check_prime(int i);

void ListPrimeNumber()
{
    primeno.push_back(2);
    primeno.push_back(3);
    primeno.push_back(5);
    for (long long i = 6; i <= 20000000; i++)
    {
        check_prime(i);
    }

}

void check_prime(int i)
{
    try
    {
        int j = 0;
        int limit = sqrt(i);
        for (j = 2 ; j <= limit;j++)
        {
            if(i % j == 0)
            {
                break;
            }
        }
        if( j > limit)
        {
            primeno.push_back(i);
        }
    }

    catch (exception ex)
    {
        std::cout << "Message";
    }
}

方法2：

#include <iostream>
#include<list>
#include <ctime>
using namespace std;

list<long long> primeno;
int noofdiv = 0;
void ListPrimeNumber();

int main()
{
    clock_t time_req = clock();
    ListPrimeNumber();
    time_req = clock() - time_req;
    cout << "time taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds" << endl;
    cout << "No of divisions : " << noofdiv;
    return 0;
}

void check_prime(int i);

void ListPrimeNumber()
{
    primeno.push_back(2);
    primeno.push_back(3);
    primeno.push_back(5);
    for (long long i = 6; i <= 10000; i++)
    {
        check_prime(i);
    }

}

void check_prime(int i)
{
    try
    {
        int limit = sqrt(i);
        for (int iter : primeno)
        {
            noofdiv++;
            if (iter <= limit && (i%iter) == 0)
            {
                break;
            }
            else if (iter > limit)
            {
                primeno.push_back(i);
                break;
            }
        }
    }

    catch (exception ex)
    {
        std::cout << "Message";
    }
}

Answer 1

您的第二个示例花费较长时间的原因是您正在迭代std::list。

std::listC ++中的A 是一个链表，这意味着它不使用连续的内存。这很不好，因为要迭代该列表，您必须以一种无法预测的方式从一个节点跳到另一个节点（到CPU / prefetcher）。同样，您很可能仅“使用”每个高速缓存行的几个字节。RAM很慢。取出由RAM字节需要很多比L1获取它更长的时间。这些天CPU速度很快，因此您的程序大多数时候不做任何事情，而是在等待内存到达。

使用std::vector代替。它一个接一个地存储所有值，并且迭代非常便宜。由于您要在内存中向前循环而不跳转，因此您将使用完整的高速缓存行，并且由于可以预知内存的访问，因此预取程序将能够在需要它们之前获取更多的页面。

包括Bjarne Stroustrup在内的许多人已经证明，std::vector在很多情况下，它的速度要比快std::list，即使在std::list“理论上”具有更好的复杂性（随机插入，删除...）的情况下，这只是因为缓存可以提供很多帮助。因此，请始终将其std::vector用作默认值。而且，如果您认为链表在您的情况下会更快，请对其进行测量，并感到惊讶-大多数情况下- std::vector占主导地位。

编辑：正如其他人指出的那样，您查找素数的方法不是很有效。我只是玩了一下，并使用位组实现了Eratosthenes筛网。

constexpr int max_prime = 1000000000;
std::bitset<max_prime> *bitset = new std::bitset<max_prime>{};
// Note: Bit SET means NO prime
bitset->set(0);
bitset->set(1);

for(int i = 4; i < max_prime ; i += 2)
    bitset->set(i); // set all even numbers
int max = sqrt(max_prime);
for(int i = 3; i < max; i += 2) { // No point testing even numbers as they can't be prime
    if(!bitset->test(i)) { // If i is prime
        for(int j = i * 2; j < no_primes; j += i)
            bitset->set(j); // set all multiples of i to non-prime
    }
}

这需要4.2至4.5秒 30秒（不知道为什么在稍作修改后它改变了这么多...必须是我不再要进行的优化）才能找到机器上所有小于10亿（1,000,000,000）的质数。您的方法花费了太长时间，甚至花费了1亿。大约两分钟后，我取消了10亿次搜索。

一亿的比较：

time taken:                63.515 seconds
time taken bitset:         1.874 seconds
No of divisions :          1975961174
No of primes found:        5761455
No of primes found bitset: 5761455

我不是数学家，所以我很确定仍有进一步优化的方法，我只针对偶数进行优化。