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

Question

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

将数字 n 除以 列表中的数字 k ( k < sqrt(n)) - 耗时 20 秒
将数字 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";
    }
}

方法二：

#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。

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

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

包括 Bjarne Stroustrup 在内的许多人已经证明，std::vector 在很多情况下比 std::list 快，即使 std::list 有 "theoretically" 更好的复杂性（随机插入、删除……）只是因为缓存有很大帮助。因此，请始终使用 std::vector 作为默认值。如果您认为链表在您的情况下会更快，测量它并且惊讶 - 大多数时候 - std::vector占主导地位。

编辑：正如其他人所指出的，您寻找素数的方法效率不高。我只是玩了一下并使用位集实现了 Sieve of 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 亿次搜索。

一亿对比：

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

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

Answer 2

首先要做的是确保您在编译时启用了优化。 c++ 标准库模板类在使用未优化代码时往往性能很差，因为它们会生成大量函数调用。优化器内联了大部分这些函数调用，这使得它们更便宜。

std::list是一个链表。它在您想随机插入或删除元素（即不是从末尾开始）的情况下最有用。

对于仅追加到列表末尾的情况 std::list 存在以下问题：

遍历列表相对昂贵，因为代码必须遵循节点指针然后检索数据
列表使用了相当多的内存，每个元素除了实际数据之外还需要一个指向上一个和下一个节点的指针。在 64 位系统上，这相当于每个元素 20 个字节，而不是 int
由于列表中的元素在内存中不连续，因此编译器无法执行尽可能多的 SIMD 优化，您将遭受更多 CPU 缓存未命中

A std::vector 将解决上述所有问题，因为它的内存是连续的，并且遍历它基本上只是递增数组索引的情况。您确实需要确保在开始时以足够大的值在向量上调用 reserve，以便附加到向量不会导致整个数组被复制到新的更大的数组。

一个比上面更大的优化是使用 Sieve of Eratosthenes 来计算你的素数。由于生成此光需要随机删除（取决于您的具体实施），std::list 可能比 std::vector 表现更好，但即使在这种情况下，std::list 的开销可能不会超过其成本。

Answer 3

A test at Ideone（几乎没有表面改动的OP代码）完全矛盾在这个问题中提出的主张：

/* check_prime__list:

              time taken       No of divisions         No of primes
    10M:    0.873 seconds        286144936                664579
    20M:    2.169 seconds        721544444               1270607   */

    <b>2B:       projected time: at least 16 minutes but likely much more</b>   (*)

/* check_prime__nums:

              time taken       No of divisions         No of primes
    10M:    4.650 seconds       1746210131                664579
    20M:   12.585 seconds       4677014576               1270607   */

    <b>2B:       projected time: at least 3 hours but likely much more</b>      (*)

我还将分度数计数器的类型更改为 long int，因为它绕过了数据类型限制。所以他们可能一直在误解那个。

但是运行时间并没有受到影响。挂钟就是挂钟。

最有可能的解释似乎是 OP 的草率测试，错误地在每个测试用例中使用了不同的值。

(*) 时间投影是通过 empirical orders of growth 分析得出的：

100**1.32 * 2.169 / 60 = 15.8

100**1.45 * 12.585 / 3600 = 2.8

根据给定的大小范围测量，列表算法的经验增长顺序明显更好，n^1.32 vs . n^1.45 用于所有数字的测试。这完全符合理论上的复杂性，因为素数比所有数字都少 n，总计 log n O(n^1.5/log n) 对比 O(n^1.5)。任何实施差异也极不可能击败实际的算法优势。

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

prime number below 2 billion - usage of std::list hinders performance

c++

performance

primes

performance-testing

data-structures

A test at Ideone（几乎没有表面改动的OP代码）完全矛盾在这个问题中提出的主张：