java - 提高并行计算欧拉数的性能

Question

我正在尝试计算 e=∑(3−4k^2/(2k+1)!); k=0..10000但是我卡住了，无法使用多线程获得所需的性能提升。

给定线程数，我尝试将总和划分为 k/numberOfThreads block ，并为每个部分总和提交 future 。我认为不好的部分可能是阶乘计算或粒度。我尝试了一个较小的步骤，但没有得到很大的改进。也许需要一种不同的方法。

ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);
int step = k / numberOfThreads ;
BigDecimal result = BigDecimal.ZERO;
for (int j = 0; j <= k; j += step) {
    Future<BigDecimal> future = executor.submit(new EulerCalculator(j, j + step));
    futures.add(future);
}
for (Future<BigDecimal> future : futures) {
    result = result.add(future.get());
}

public class EulerCalculator implements Callable<BigDecimal> {
    private int start;
    private int end;

    public BigDecimal call() {
        long numerator = 3 - 4 * start * start;
        BigDecimal denominator = factorial(2 * start + 1);
        BigDecimal partialSum = BigDecimal.valueOf(numerator)
                                .divide(denominator, 1000, RoundingMode.HALF_EVEN);
        for (int i = start + 1 ; i < end; i++) {
            numerator = 3 - 4 * i * i;
            denominator = denominator.multiply(BigDecimal.valueOf(2 * i * (2*i + 1)));
            partialSum = partialSum.add(BigDecimal.valueOf(numerator)
                                        .divide(fact, 1000, RoundingMode.HALF_EVEN));
        }

        return partialSum;
    }

    private BigDecimal factorial(int cur) {
        BigDecimal fact = BigDecimal.ONE;
        for (int i = 2; i <= cur; i++) {
            fact = fact.multiply(BigDecimal.valueOf(i));
        }

        return fact;
    }
}

在四核上运行几次的最佳结果:

k = 10000

线程 = 1:345 毫秒

线程数 = 2:216 毫秒

线程数 = 4:184 毫秒

线程数 = 8:225 毫秒

Answer 1

您的阶乘部分不是常数时间运算，而是 O(n)。这意味着您的第一个线程比最后一个线程的工作要少得多。因此，您没有平均分配工作。

通常有三种方法来解决这个问题。

您可以采用不均匀步长，即较小的 k 步长较大。但是，这是非常低效的，因为您要进行数千次相同的乘法运算。

您可以尝试切换到近似算法来计算阶乘，使其达到常数时间。对于小 k，您可以使用迭代来防止精度损失，因为惩罚会很低，而且小 k 也不多。

另一种方法是构建一个大数组，其中包含所有可能用于计算的阶乘，它必须在您提交任何任务之前运行。这种缓存方法损失的精度较低。请参阅下面关于如何并行化此过程的评论。