Atkin代码优化的C++筛子

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

为了优化这个函数，我有几个关于我可以做得更好的问题。

我将筛子数组初始化为布尔值的动态数组，因此它们都将缺省为false，让筛子像这样动态更快，还是应该将其保留为普通数组？

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

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

Answer 1

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

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

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

最好的优化通常是改变算法，通常像循环展开之类的事情最好留给编译器，除非代码是特别时间关键的(即使是这样)。

此外，确保您在编译时启用了优化-这可能会产生巨大的差异。

Answer 2

正如另一个答案所建议的那样，剖析是计算时间走向的最好方法。

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

，

• ，我不相信你在你的sieve分配上确实有零初始化的保证；要做到这一点，你需要使用bool *sieve = new bool[max+1]();。如果你发现事情运行正常，那么你要么是幸运的，要么是在一个零初始化调试构建的编译器下运行的。如果是这样的话，尝试一个启用了优化的发布版本，你会看到一些加速。
• 你的bool[]很可能不会使用每个元素1位，而可能是一个字节。您可能会发现使用std::vector<bool>更有效，因为它通常专门用于密集存储布尔值-每个布尔值1位。您将在减少内存占用和增加读取/写入单个布尔值的复杂性之间进行权衡。
• 尝试通过适当的输入验证将素数组预先调整为max / log(max)，作为小于max的素数的近似值。
• 如果在应用程序中重复调用该函数，请尝试重用以前的筛选器数组来应答后续调用。