DnCを介した階乗の計算

Question

私は分裂と征服戦略によってFactorial関数を実装しようとしています。私はForkJoinフレームワークを使用して、各再帰的タスクをforkして計算を高速化しました。 しかし私はそれが私の期待通りにスピードアップしていないことを発見しました。 ForkJoinを使わずに階数を計算するのに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の結果だとは思わない。助けてください！

Answer 1

フォーク/ジョインは、並列処理をパラレル化できます。それはあなたに一定の利益を与えます（時間を4で割る例）。そして、それはあなたが持っている実際のCPUによって制限されています（200のスレッドは例で同じ4つのCPUしか共有しません）。

コントラスト（典型的なアルゴリズム）はO(N!)で、非常に非常に速く成長することを意味します。

各ステップごとに新しいフォークを作成すると、フォークと結合のオーバーヘッドによって、並列化からの利得が補正されます。

重要なことは、O(N!)ではない別のアルゴリズムで階乗を計算しようとしていることです。動的プログラミング（中間結果の再利用）を適用する場合は、O(N)に変換することができます。私はあなたが私が何をすべきかで真似しようとしているアルゴリズムは、私は彼らに二時間を必要とするときにそれらを再利用するために、ペアの計算と行列か何かをmantainingされるかわからない

...

---

あなたのコードを見れば、各階乗メソッドの実行が2つの子の実行を引き起こすことがわかります：(p+q)/2,qとp,(p+q)/2+1 ...またはそのようなものです。各時間ファクタルメソッドが結果を見つけてマップ[Pair -> BigDecimal]に保存すると、メソッドの先頭でこのキャッシュを照会できます。このマップをクラスのメンバーにする（または引数を渡す）ので、異なるメソッド呼び出しがマップを共有します。