时间戳

首页 > 解决方案 > 低于 20 亿的素数 - 使用 std::list 会影响性能

c++ - 低于 20 亿的素数 - 使用 std::list 会影响性能

问题描述

问题陈述是在 < 20 秒的时间范围内找到 20 亿以下的素数。我遵循以下方法。

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

  2. 将数字 n 与sqrt(n) 下面的素数列表相除。在这种情况下，我将素数存储在 std::list 中 - 耗时超过 180 秒

有人能帮我理解为什么第二种方法需要很长时间，即使我们减少了 50%（大约）的划分？还是我选择了错误的数据结构？

方法一：

#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";
    }
}

标签： c++performancedata-structuresperformance-testingprimes

解决方案

您的第二个示例需要更长的时间的原因是您正在迭代std::list.

C++ 中的Astd::list是一个链表，这意味着它不使用连续内存。这很糟糕，因为要迭代列表，您必须以（到 CPU/预取器）不可预测的方式从一个节点跳到另一个节点。此外，您很可能只“使用”每个缓存行的几个字节。内存很慢。从 RAM 中获取一个字节比从 L1 中获取它花费的时间要长得多。这些天 CPU 很快，所以你的程序大部分时间什么都不做，等待内存到达。

改用 a std::vector。它一个接一个地存储所有值，并且迭代非常便宜。由于您在内存中向前迭代而不跳转，因此您正在使用完整的缓存行，并且您的预取器将能够在您需要它们之前获取更多页面，因为您对内存的访问是可预测的。

包括 Bjarne Stroustrup 在内的许多人已经证明，在很多情况下它std::vector比. 所以总是使用你的默认值。如果您认为链表在您的情况下会更快，请测量它并惊讶于 - 大多数时候 -占主导地位。std::liststd::liststd::vectorstd::vector

编辑：正如其他人所指出的，您找到素数的方法不是很有效。我只是玩了一下，并使用 bitset实现了一个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 秒（不知道为什么在轻微修改后会发生如此大的变化......一定是我不再尝试的优化）在我的机器上找到十亿（1,000,000,000）以下的所有素数。即使是 1 亿人，您的方法也花费了太长时间。大约两分钟后，我取消了 10 亿次搜索。

1亿比较：

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

我不是数学家，所以我很确定还有办法进一步优化它，我只优化偶数。

推荐阅读