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 番目の素数を生成しました。好奇心から、 and なし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 番目の素数) を 2 番目の方法で計算すると、12 秒かかります。これは驚異的な違いです。

それで、ここで何が起こっているのですか？2 番目のアプローチでは、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

これが犯人のようです：

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

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

最適化という名目で、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;
  }
}

プライム検索を最適化する方法は他にもいくつかありますが、これは最も簡単に実行できる方法の 1 つであり、大きなメリットがあります。

編集: (int)Math.Sqrt(n) + 1 の使用を検討することをお勧めします。FP 関数 + 切り捨てにより、大きな素数の 2 乗を見逃す可能性があります。

于 2013-03-04T21:25:13.497 に答える
2

Math.Sqrt問題の少なくとも一部は、実行される回数です。LINQ クエリでは、これは 1 回実行されますが、ループの例では N 回実行されます。それをローカルに引き出して、アプリケーションを再プロファイリングしてみてください。これにより、より代表的な内訳が得られます

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