1

static List<long> primes特定の時点までのすべての既知の素数と、次のような関数があります。

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    foreach (long q in primes)
    {
        if (p % q == 0)
            return false;

        if (q >= rootP)
            return true;
    }

    return true;
}

これは次のように並列化できます。

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    primes.AsParallel().ForAll(q =>
        {
            if (p % q == 0)
                return false;

            if (q > rootP)
                break;
        });

    return true;
}

ただし、これにより、ブロック内の一部の戻り値の型がデリゲートの戻り値の型に暗黙的に変換できないというコンパイル時エラーが発生します。

私はLINQ、特にPLINQに少し慣れていません。これは、候補素数に対する既知の各素数のチェックが独立したプロセスであるため、並列処理の良い候補のように思えます。

ブロックが機能するように修正する簡単な方法はありますか、それともまったく別の方法でこの問題に取り組む必要がありますか?

4

4 に答える 4

1

構文的には、コードで 2 つの間違いを犯しています。

  1. ラムダの Areturnは、ラムダからだけで、囲んでいるメソッドから返されないため、return false;正しく機能しません。
  2. breakラムダの外に出ることはできません。そのラムダがループで実行されたとしても、そのループは基本的に目に見えず、直接制御することはできません。

コードを修正する最善の方法は、この目的のために正確に作成された LINQ メソッドを使用することAny()でTakeWhile()あり、大きすぎる素数を除外することです。

static bool IsPrime(long p)
{
    double rootP = Math.Sqrt(p);

    return !primes.AsParallel().TakeWhile(q => q > rootP).Any(q => p % q == 0);
}

しかし、あなたの推論にも欠陥があります。

これは、候補素数に対する既知の各素数のチェックが独立したプロセスであるため、並列処理の良い候補のように思えます。

それはそれほど単純ではありません。各素数のチェックも非常に簡単なプロセスです。これは、単純な並列化 (上記で提案したものなど) のオーバーヘッドが、パフォーマンスの向上よりも大きくなる可能性が高いことを意味します。より複雑な解決策 (コメントでマシュー・ワトソンが提案したものなど) がそれを助けることができます。

于 2013-05-30T10:34:56.303 に答える
1

これはあなたの問題の解決策です：

static List<long> primes = new List<long>() {
  2,3,5,7,11,13,17,19,23
};

static bool isPrime(long p) {
  var sqrt = (long)Math.Sqrt(p);
  if (sqrt * sqrt == p)
    return (false);
  return (primes.AsParallel().All(n => n > sqrt || p % n != 0));
}

二次数の並列処理を削減しようとし、最初の数が見つかるとすぐにそれ以上の候補のチェックを停止します。

于 2013-05-30T07:39:38.553 に答える
0

代わりに Parallel.For を使用する方が簡単かもしれません

static volatile bool result = true;
static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    Parallel.For(0, primes.Count, (q, state) =>
        {
            if (p % q == 0)
            {
                result = false;
                state.Break();
            }

            if (q > rootP)
                state.Break();
        });

    return result;
}
于 2013-05-30T11:01:15.037 に答える