0

我想知道是否有人对我可以做些什么来提高代码的运行速度有任何建议。我写了一个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 循环将素数存储在向量中，是否有更快的方法可以找到筛子中的所有素数以将它们存储在向量中？

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

4

2 回答 2

0

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

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

  • 我不相信您实际上可以保证对筛子的分配进行零初始化；为此，您需要使用bool *sieve = new bool[max+1]();. 如果您发现一切正常，那么您要么在这里很幸运，要么在零初始化调试构建的编译器下运行。如果是这种情况，请尝试启用优化的发布版本，您会看到一些加速。

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

  • 尝试max / log(max)通过适当的输入验证将素数数组的大小预置为 ，作为小于最大值的素数数量的近似值。

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

于 2015-04-16T19:03:43.897 回答
0

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

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

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

最好的优化通常是改变算法，通常做循环展开等事情最好留给编译器，除非代码对时间特别敏感（即使那样也可能不是）。

此外，请确保您正在编译优化 - 这可以产生巨大的差异。

于 2015-04-16T06:52:07.317 回答