素数计算瓶颈

Question

受这里的另一个问题的启发：2个百万以下素数之和，我决定尝试使用本文中描述的算法从头开始实现埃拉托斯提尼筛。

unsigned int CalculateSumOfPrimes(const unsigned int number) {
    if(number <= 1) return 0;
    if(number == 2) return 2;
    std::vector<unsigned int> listOfPrimes;
    CalculateListOfPrimes(listOfPrimes, number);
    unsigned int sum = 0;
    for(unsigned int i = 0; i < listOfPrimes.size(); ++i) {
        sum += listOfPrimes.at(i);
    }
    return sum;
}

void CalculateListOfPrimes(std::vector<unsigned int>& container, const unsigned int number) {
    if(container.size() != 0) {
        std::cout << "Container must be empty!" << std::endl;
        return;
    }
    unsigned int current_prime_check = 2;
    std::vector<unsigned int> listOfNonPrimes;
    while(current_prime_check < number) {
        for(unsigned int i = current_prime_check; i < number; i += current_prime_check) {
            if(i == current_prime_check) {
                container.push_back(i);
                continue;
            }
            if(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), i) != listOfNonPrimes.end()) continue;
            listOfNonPrimes.push_back(i);
        }
        ++current_prime_check;
        while(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), current_prime_check) != listOfNonPrimes.end()) {
            ++current_prime_check;            
        }
    }

}

目前，大型数据(65536或更高)的主要瓶颈是占15秒运行时间总数的67%的CalculateListOfPrimes(...)。

将使用从std::vector切换到std::list (因为我只是添加到列表的末尾，这似乎是个好主意)，只节省了5%。

看看它，内循环正在遍历从当前已知的非素数到下一个未知数的每一个可能的数字，是否有一种算法来判断下一个数字应该是什么，或者下一个数字是否是下一个数字，以及在保证它不存在于素数列表之后的每一个数字？

Answer 1

你的主要效率在这里：

if(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), i) != listOfNonPrimes.end()) 

对于每一个非素数，你都是在搜索非素数列表。对于std::vector和std::list，这是一个O(n)操作。

实现这一点的通常方法是有一个数组，其中删除的元素由其索引表示到数组中，因此表示O(1)的复杂性，用于设置和检查元素是否已经设置为false。

std::vector<bool> sieve(number + 1, true);

然后可以替换以下行：

if(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), i) != listOfNonPrimes.end())
    continue;
listOfNonPrimes.push_back(i);

// Change too
sieve[i] = false;

其他事情：

每次在循环过程中，您都要做一个测试：

if (i == current_prime_check) {
    container.push_back(i);
    continue;
}

这只是第一个元素。

所以把它吊出圈套。在循环外执行container.push_back(i);并在下一个位置启动i：

for (unsigned int i = 2 * current_prime_check; i < number; i += current_prime_check)
             //   ^^^^ Start one place up from where you were.

也替换了另一个查找：

++current_prime_check;
while (std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), current_prime_check) != listOfNonPrimes.end()) {
    ++current_prime_check;
}

如果您使用的是筛子，这可以用一个简单的测试替换成筛子：

++current_prime_check;
while (!sieve[current_prime_check]) {
    ++current_prime_check;
}

编辑注释后的

：

我们可以让它更快。

生成质数的函数：

void CalculateListOfPrimes(std::vector<unsigned int>& container, const unsigned int number)

传递一个数组，函数填充该数组，然后将该数组作为下一阶段处理。一个更好的解决方案是传递一个应用于每个素数的函数。然后，您可以使用一个简单的版本将值推入容器中。或者，您也可以使用一个函数来总结素数(因此您甚至不需要容器，也不需要对它进行迭代)。

所以试着：

template<typename Func>
void CalculateListOfPrimes(Func const& action, const unsigned int number);

然后你就可以像这样使用它：

struct PB
{
    std::vector<unsigned int>& cont;
    PB(std::vector<unsigned int>& c): cont(c) {}
    void operator()(unsigned int value) const { cont.push_back(value); }
};
…
std::vector<int> data;
CalculateListOfPrimes(PB(data), 2000000);

或者你可以有一个特定的功能

struct Sum
{
   unsigned int& sum;
   Sum(unsigned int& s) : sum(s) {}
   void operator()(unsigned int value) const { sum += value; }
};
…
unsigned int total;
CalculateListOfPrimes(Sum(total), 2000000);

评论：

不要使用system("pause");。这显然是特定于平台的。你所做的就是让程序等待。因此，从标准输入中读取一行。

std::getline(std::cin, line); // If you have other input you may need to flush first.

哈希定义的不是一个好动作.

更喜欢使用函数(没有性能损失，因为它可能是内联的)。如果您必须使用哈希定义，那么就像这一样定义它：

#define PAUSE  do { /* Action To Pause */ } while(false)

atoi()

primes = CalculateListOfPrimes(std::atoi(argv[2]));

不标准。无法检查失败。

我使用boost：：词法_cast(argv[2])它会在失败时抛出一个异常。

不要在

周围传递指针

DisplayResult(&primes, 0);

更改函数，以便通过const引用传递。这样可以避免复制，阻止您意外地修改数组，并且您不能意外地传递一个NULL，因此它总是有效的。

void DisplayResult(std::vector<bool> const& container, const unsigned int sum);

真值：

==操作的结果是布尔值，因此不需要在此基础上使用三元操作符：

bool isSumArg = (std::strcmp("-s", argv[1]) == 0 ? true : false);

与易于阅读的内容完全相同。

bool isSumArg = (std::strcmp("-s", argv[1]) == 0);

素数特定值：

这里的快速优化。您不需要这个循环就可以一直到number。

您只需要循环到sqrt(number)，在此之后不会影响结果。

while (current_prime_check < number) { … }

使函数做一件事。

这个函数根据不相关的输入做很多不同的事情。

void DisplayResult(std::vector<bool>* container, const unsigned int sum) {
    if(container == NULL && sum == 0) {
        return;
    }

    if(sum != 0) {
        std::cout << "Sum of Primes: " << sum << std::endl;
        return;
    } else if(container != NULL) {
        std::cout << "List of Primes:" << std::endl;
        for(unsigned int i = 1; i < container->size(); ++i) {
            if(container->at(i) == true) std::cout << std::setw(15) << std::right << i << std::endl;
        }
    }
}

Answer 2

您不应该在列表中添加非素数，然后对其执行大量的查找操作(所有这些操作都会扫描整个容器)。

相反，一个筛子是一个数字是否是某个素数的倍数的表。像这样的东西，然后你填写。

std::vector<bool> sieve(limit + 1);

例如，sieve[5]是false，意思是5是素数，而sieve[10]、sieve[15]将全部设置为true，为5的倍数。