6

我正在将一个简单的素数生成单线从 Scala 改编为 C#（作者在此博客的评论中提到）。我想出了以下内容：

int NextPrime(int from)
{
  while(true)
  {
    n++;
    if (!Enumerable.Range(2, (int)Math.Sqrt(n) - 1).Any((i) => n % i == 0))
      return n;
  }
}

它可以工作，返回与运行博客中引用的代码相同的结果。事实上，它的工作速度相当快。在 LinqPad 中，它在大约 1 秒内生成了第 100,000 个素数。出于好奇，我在没有Enumerable.Range()and的情况下重写了它Any()：

int NextPrimeB(int from)
{
  while(true)
  {
    n++;
    bool hasFactor = false;
    for (int i = 2; i <= (int)Math.Sqrt(n); i++)
    {
        if (n % i == 0) hasFactor = true;
    }
    if (!hasFactor) return n;
  }
}

直观地说，我希望它们以相同的速度运行，或者甚至让后者运行得更快一些。实际上，用第二种方法计算相同的值（第 100,000 个素数）需要12 秒- 这是一个惊人的差异。

那么这里发生了什么？从根本上说，在第二种方法中一定会发生一些额外的事情，它会占用 CPU 周期，或者在 Linq 示例的背景下进行一些优化。有人知道为什么吗？

4

6 回答 6

9

对于 for 循环的每次迭代，您都会找到 n 的平方根。而是缓存它。

int root = (int)Math.Sqrt(n);
for (int i = 2; i <= root; i++)

正如其他人所提到的，一旦找到一个因素，就打破 for 循环。

于 2013-03-04T20:58:04.197 回答
4

Enumerable.Any如果条件成功而您的循环不成功，则提前退出。

source一旦可以确定结果，就停止枚举。

这是一个糟糕的基准测试的例子。尝试修改你的循环，看看有什么不同：

    if (n % i == 0) { hasFactor = true; break; }
}

throw new InvalidOperationException("Cannot satisfy criteria.");
于 2013-03-04T20:58:06.973 回答
4

LINQ 版本短路，您的循环不会。我的意思是当你确定一个特定的整数实际上是一个因素时，LINQ 代码会停止，返回它，然后继续。您的代码会一直循环，直到完成。

如果您更改for以包含该短路，您应该会看到类似的性能：

int NextPrimeB(int from)
{
  while(true)
  {
    n++;
    for (int i = 2; i <= (int)Math.Sqrt(n); i++)
    {
        if (n % i == 0) return n;;
    }
  }
}
于 2013-03-04T20:58:13.730 回答
4

看起来这是罪魁祸首：

for (int i = 2; i <= (int)Math.Sqrt(n); i++)
{
    if (n % i == 0) hasFactor = true;
}

一旦找到一个因素，您应该退出循环：

if (n % i == 0){
   hasFactor = true;
   break;
}

正如其他人指出的那样，将 Math.Sqrt 调用移到循环之外，以避免在每个循环中调用它。

于 2013-03-04T20:58:26.787 回答
4

以优化的名义，您可以通过避免 2 之后的偶数来更聪明一点：

if (n % 2 != 0)
{
  int quux = (int)Math.Sqrt(n);

  for (int i = 3; i <= quux; i += 2)
  {
    if (n % i == 0) return n;
  }
}

还有一些其他方法可以优化主要搜索，但这是更容易做到的方法之一，并且有很大的回报。

编辑：您可能需要考虑使用 (int)Math.Sqrt(n) + 1。FP 函数 + 向下舍入可能会导致您错过一个大素数的平方。

于 2013-03-04T21:25:13.497 回答
2

至少部分问题是Math.Sqrt执行的次数。在 LINQ 查询中执行一次，但在循环示例中执行 N 次。尝试将其拉出到本地并重新分析应用程序。这将为您提供更具代表性的细分

int limit = (int)Math.Sqrt(n);
for (int i = 2; i <= limit; i++)
于 2013-03-04T21:00:20.560 回答