java - 通过 DnC 计算阶乘

Question

我正在尝试通过分而治之的策略来实现阶乘函数。我使用 ForkJoin 框架来 fork 每个递归任务以加快计算速度。 但我发现它并没有像我预期的那样加速。 在不使用 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 的结果。请帮忙!

Answer 1

Fork/Join 可以并行化计算。它是:给你一个恒定的增益(例如将时间除以4)。这受到您拥有的实际 CPU 的限制(例如 200 个线程将仅共享相同的 4 个 CPU)。

相比之下，阶乘(典型算法)是O(N!)，这意味着它增长得非常非常快。

如果您为每个步骤创建一个新的 fork ，则 fork 和加入的开销将补偿并行化带来的 yield 。

因此，重要的是尝试使用另一种非 O(N!) 的算法来计算阶乘。如果您应用动态规划(重复使用中间结果)，则可以将其转换为 O(N)。

我不知道你试图模仿的算法我应该做的是维护一个矩阵或一些带有成对计算的东西，以便在我第二次需要它们时重用它们......

---

查看您的代码，我可以看到每个阶乘方法执行都会引发两个子执行:(p+q)/2,q 和 p,(p+q)/2+1 ...或者类似的东西。如果每次阶乘方法找到结果，将其保存在映射[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
   }
}