C++-筛选Atkin代码优化

Question

我想知道是否有人对我可以做些什么来提高代码的运行速度有任何建议。我编写了一个Sieve of Atkin函数，该函数返回一个向量，该向量包括[2, max]中的所有素数。

这是我的密码。

void atkin_sieve (unsigned int max, std::vector <unsigned int> & primes) {
// Sieve array up to max defaulted to false
// Index's [0, max] correspond to numbers
// Dynamic memory so all values default false
bool* sieve = new bool [max + 1];
// Square root of max number
unsigned int sqrt_max = int (sqrt (max));
// Unsigned integers declared to save time
unsigned int n, x, y;
// TODO - Explain this
for (x = 1; x < sqrt_max; x++) {
for (y = 1; y < sqrt_max; y++) {
n = (4 * x * x) + (y * y);
if (n <= max && (n % 12 == 1 || n % 12 == 5))
sieve [n] = !sieve [n];
n = (3 * x * x) + (y * y);
if (n <= max && (n % 12 == 7))
sieve [n] = !sieve [n];
n = (3 * x * x) - (y * y);
if (x > y && n <= max && (n % 12 == 11))
sieve [n] = !sieve [n];
}
}
// TODO - Explain this
for (x = 5; x < sqrt_max; x++) {
if (sieve [x]) {
n = x * x;
for (y = n; y <= max; y += n)
sieve [y] = false;
}
}
// Push primes 2, 3, and 5
primes.push_back(2);
primes.push_back(3);
primes.push_back(5);
// Start from prime 7, skip even numbers
for (x = 7; x <= max; x += 2) {
// If the number is prime
if (sieve [x])
// Push it into the vector
primes.push_back(x);
}
// Delete the sieve array
delete [] sieve;
}

我有几个问题，我可以做得更好，以优化这个功能。

我将sieve数组初始化为布尔值的动态数组，这样它们都会默认为false，让sieve像这样动态会更快吗？还是应该将其保持为正常数组？

在算法处理后，我使用for循环将素数存储在向量中，有没有更快的方法可以找到筛子中的所有素数并将其存储在向量？

欢迎并非常感谢任何其他提示、技巧、提示或代码，谢谢。

Answer 1

根据返回的素数数量，使用std::vector可能会导致问题，每次向量必须增长以处理超出其容量的对象时，它可能需要创建一个新数组，并将所有值从旧数组复制到新数组。考虑使用std::list或std::deque来避免此问题。如果你真的需要一个vector，它可能会更快地循环并计算素数的数量，然后reserve在向量中的大小，这样向量就永远不需要增长。

您可能应该对代码进行一些分析——如何进行分析取决于您的开发环境。这应该会告诉您代码的大部分时间都花在了哪里。如果没有这些信息，你可能会花很长时间优化代码的一部分，而它不会对结果产生巨大影响。

至少添加一些定时代码，这样你就可以看到你所做的任何更改是否有帮助，以及有多大帮助。

最好的优化通常是更改算法，通常是做循环展开等事情，最好留给编译器，除非代码是特别关键的时间(即使这样也可能不是)。

此外，请确保您在编译时进行了优化——这可能会产生巨大的影响。

Answer 2

正如另一个答案所建议的那样，分析是确定时间走向的最佳方法。

一些建议和意见，其中一些可能是显而易见的

• 我不相信你真的能保证在你的筛子分配上零初始化；为此，您需要使用bool *sieve = new bool[max+1]();。如果你发现一切正常，那么你要么在这里很幸运，要么在一个零初始化调试构建的编译器下运行。如果是这样的话，尝试启用优化的版本构建，你会看到速度有所加快。

• 您的bool[]很可能不会使用每个元素1位，而是可能使用一个字节。您可能会发现使用std::vector<bool>更有效，因为它通常专门用于密集存储布尔值——每个布尔值1位。您将在减少内存占用和增加读/写单个布尔值的复杂性之间进行权衡。

• 尝试将素数数组的大小预先调整为max / log(max)，并进行适当的输入验证，作为小于最大的素数的近似值

• 如果函数在应用程序中被重复调用，请尝试重用以前的sive数组来回答后续调用。