2

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

相反，阶乘（典型算法）O(N!)意味着它的增长非常非常非常快。

如果您为每个步骤创建一个新的分叉，那么分叉和连接的开销会补偿并行化带来的收益。

所以重要的是尝试用另一种不是O(N!). 如果您应用动态编程（重用中间结果），您可以将其转换为O(N).

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

查看您的代码，我可以看到每个阶乘方法执行都会引发两个子执行：(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 回答