2

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

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

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 毫秒

4

3 回答 3

1

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

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

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

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

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

于 2019-05-18T22:37:37.020 回答
1

由于您需要所有denominators 并且每个 s 都依赖于ALL以前，我将有一个专用线程来计算所有这些；并为每个denominator计算提交一个不同的任务到您的线程池以并行计算特定的部分总和。最后使用并行流聚合所有结果。以下代码显示了这些详细信息：

    public static BigDecimal calculate(int k, int numberOfThreads) {
        ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
        List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);

        BigDecimal denominator = BigDecimal.ONE;
        for (int j = 1; j <= k; j++) {
            denominator = denominator.multiply(BigDecimal.valueOf(4 * j * j + 2 * j));
            Future<BigDecimal> future = executor.submit(computePartialSum(j, denominator));
            futures.add(future);
        }

        return futures.stream().parallel()
            .map(future.get())
            .reduce(BigDecimal.ZERO, BigDecimal::add).add(BigDecimal.valueOf(3));
    }

    public static Callable<BigDecimal> computePartialSum(int curr, BigDecimal denominator) {
        return () -> {
            long numerator = 3 - 4 * curr * curr;
            return BigDecimal.valueOf(numerator).divide(denominator, 1000, RoundingMode.HALF_EVEN);
        };
    }

不过，您的瓶颈将是阶乘的计算；您可以将其划分为较小的阶乘段并缓存它们以聚合成它们的真实值，我的两分钱。

GitHub上的完整代码

于 2019-05-19T01:24:14.483 回答
0

感谢您的回答！我用一个简单的循环缓存了阶乘，for并且在其他计算中得到了很好的结果：

1 thread = 17ms
2 threads  = 10ms
4 threads = 7ms

但是，我需要绘制一个类似于下图的图表，并且只有在我利用线程来计算阶乘时才有可能。

在此处输入图像描述

我测试了这个n!算法：

public BigDecimal calculate(int number) {
        if (number == 0 || number == 1) {
            return BigDecimal.ONE;
        }
        List<Callable<BigDecimal>> callables = new ArrayList<>();
        int step = number / processors;
        for (int i = 2; i <= number; i += step + 1) {
            callables.add(new FactorialPartCalculator(i, i + step >= number ? number : i + step));
        }
        List<Future<BigDecimal>> futures = executor.invokeAll(callables);
        BigDecimal result = BigDecimal.ONE;
        for (Future<BigDecimal> future : futures) {
            result = result.multiply(future.get());
        }
        return result;
    }
public class FactorialPartCalculator implements Callable<BigDecimal> {
    @Override
    public BigDecimal call() throws Exception {
        BigDecimal factorialPart = BigDecimal.ONE;
        for (int i = start; i <= end; i++) {
            factorialPart = factorialPart.multiply(BigDecimal.valueOf(i));
        }

        return factorialPart;
    }

我用 6 个线程获得了 6.4 倍的加速20000!。所以我需要缓存阶乘并将缓存过程包含在整个时间中。该程序将在 32 个处理器上进行测试，我应该获得尽可能多的加速

所以我的问题是如何更改上述算法以将所有阶乘存储在数组中？如果有帮助，我只需要奇怪的阶乘。

于 2019-05-19T12:43:36.730 回答