2

分割統治戦略を介して階乗関数を実装しようとしています。ForkJoin フレームワークを使用して各再帰タスクをフォークし、計算を高速化しました。しかし、思ったほどスピードアップしていないことがわかりました。ForkJoin を使用しないと 50000 の階乗を計算すると 28 秒かかりましたが、ForkJoin を使用した場合は 25 秒かかりました。これは forkjoin のないコードです:

public static BigInteger factorial(long p, long q) {
    if (q < p) {
        return new BigInteger("1");
    }
    if (p == q) {
        return new BigInteger("" + p);
    }
    BigInteger fact = new BigInteger("1");
    fact = fact.multiply(factorial(p, (p + q) / 2)).multiply(factorial((p + q) / 2 + 1, q));
    return fact;
}

これは forkJoin を使用したコードです。

public class Factorial extends RecursiveTask<BigInteger>{
private long p, q;
public Factorial(long p, long q) {
    this.p = p;
    this.q = q;
}
@Override
public BigInteger compute() {
    if(q < p) {
        return new BigInteger("1");
    } 
    if( p == q) {
        return new BigInteger(""+p);
    }
    Factorial f1 = new Factorial(p, (p+q)/2);
    Factorial f2 = new Factorial((p+q)/2 + 1, q);
    f2.fork();
    return f1.compute().multiply(f2.join());        
}    
}

どこが間違っていますか？これは、Fork/Join の結果ではないと思います。助けてください！

4

1 に答える 1

5

Fork/Join は、コンピューティングを並列化できます。それは次のとおりです：一定のゲインを提供します（例では時間を4で割ります）。そして、それはあなたが持っている実際の CPU によって制限されます (例では、200 スレッドは同じ 4 つの CPU しか共有しません)。

対照的に、factorial (典型的なアルゴリズム) はO(N!)、非常に非常に速く成長することを意味します。

また、ステップごとに新しいフォークを作成すると、フォークと結合のオーバーヘッドが並列化による利益を相殺します。

したがって、重要なことは、 ではない別のアルゴリズムで階乗を計算しようとすることですO(N!)。動的計画法 (中間結果の再利用) を適用すると、 に変換できますO(N)。

私がすべきことによって模倣しようとしているアルゴリズムが、2回目に必要なときに再利用するために、ペアの計算で行列または何かを管理することであることがわかりません...

あなたのコードを見ると、各階乗メソッドの実行が2つの子実行を引き起こすことがわかります.and (p+q)/2,q...p,(p+q)/2+1またはそのようなもの。factorial メソッドが結果を見つけるたびに map に保存する場合[Pair -> BigDecimal]は、メソッドの開始時にこのキャッシュをクエリできます。このマップをクラスのメンバーにする (または引数を介して渡す) ことで、さまざまなメソッド呼び出しがマップを共有します。

factorial(p,q) {
   if (there is result for (p,q) in the map)
      return it
   else
   {
      normal computation (provokes two child invocations)
      save result into cache
   }
}
于 2012-02-02T17:12:42.263 に答える