Enumerable.Range(..). any(..)优于基本循环:Why

本文关键字：循环 Why 于基本 any Range Enumerable | 更新日期: 2023-09-27 18:02:15

我正在将一个简单的质数生成一行程序从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秒内生成了第10万个素数。出于好奇，我重写了它，去掉了Enumerable.Range()和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示例的后台进行了一些优化。有人知道为什么吗?

Enumerable.Range(..). any(..)优于基本循环:Why

对于For循环的每次迭代，您都要找到n的平方根。将其缓存。

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

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

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

看起来这就是罪魁祸首:

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

一旦找到一个因子，就应该退出循环:

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

正如其他人指出的那样，移动数学。

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

一旦可以确定结果，source的枚举将立即停止。

这是一个不好的基准测试的例子。试着修改你的循环，看看有什么不同:

    if (n % i == 0) { hasFactor = true; break; }
}
throw new InvalidOperationException("Cannot satisfy criteria.");

以优化的名义，你可以更聪明一点，避免在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函数+舍入可能会导致您错过大素数的平方。

至少部分问题在于执行Math.Sqrt的次数。在LINQ查询中，这只执行一次，但在循环示例中，它执行了N次。尝试将其拉出到本地并重新分析应用程序。这会给你一个更有代表性的分解

int limit = (int)Math.Sqrt(n);
for (int i = 2; i <= limit; i++)
相关文章：