并行化比非并行化任务花费更长的时间

Question

我需要为大学做一个编程作业。任务是实现一个程序，它返回方程 q² + 3qp + p² = r² (q,p,r 素数) 的所有解。随后，程序将通过并行化来加速。不幸的是，我们必须使用 BigInteger，所以不要感到惊讶。

这是我写的我的课，它精确地计算了这个方程。

    public boolean calculateEquation() {

    //Equation: p² + 3pq + q² = r²

    if (calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare())) {

        System.out.println("p: " + p + " q: " + q + " r: " + r);

    }

    return calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare());

}

@Override

public void run() {

    calculateEquation();

}

该类的完整代码： https ://pastebin.com/wwrDurUT

我的下一步是测试代码并停止时间以查看并行化是否在以后起作用。为了实现并行化，我查看了不同的线程，其中还有一个链接在这里：在 java 中并行化任务的最简单方法是什么？

这是我的结果：

ExecutorService executorService = Executors.newFixedThreadPool(Configuration.instance.maximumNumberOfCores);

        ExecutorCompletionService executorCompletionService = new ExecutorCompletionService(executorService);

        for (BigInteger pValue : possiblePValues) {

            for (BigInteger qValue : possibleQValues) {

                for (BigInteger rValue : possibleRValues) {

                    executorCompletionService.submit(new Thirteen(pValue, qValue, rValue), null);

                }

            }

        }

        executorCompletionService.take();

完整代码： https ://pastebin.com/kviEnnFH

现在有趣的是，并行化版本只有在任务数量少的情况下才会更快。对于 0-500 之间的所有素数，并行化版本更快。如果我取 0 到 2000 之间的所有素数，结果看起来会非常不同：

0 到 100 之间的所有素数：

未并行化：任务耗时：110ms

并行化：任务耗时：64ms

0 到 2000 之间的所有素数：

未并行化：任务耗时：7797ms

并行化：任务耗时：25799ms

由于关于该主题的易于理解的资源很少，而且老实说我不太了解我的代码究竟做了什么，我很惊讶它为什么会这样。

Answer 1

首先，p² + 3pq + q² = r²使用三重嵌入式 for 循环来实现这个等式是没有意义的，这导致复杂度为O(n) = n^3. 这可以仅使用两个 for 循环来完成，因为如果我们知道 和 的值，p可以使用等式计算。qrfor (BigInteger p: possiblePValues) {    for (BigInteger q: possibleQValues) {        BigInteger r = p.pow(2).add(q.pow(2)).add(p.multiply(q).multiply(new BigInteger("3")))        // decide if sqrt(r) is prime     } }现在，如果我们将预先计算的素数保存在一个Hashmap例子中，我们可以r通过查找立即确定是否是素数。关于并行化：您的方法是错误的，因为您只是为一些需要相对较短的时间才能完成的操作生成线程。线程管理的开销可能比计算方程本身的操作花费的时间更长。我猜这就是为什么多线程版本的运行时间更长的原因。关于如何并行化两个嵌入式 for 循环没有黄金法则。我的方法是根据您拥有的核心数量将第一个循环分成更小的块并创建一些间隔。例如，如果我们有 100 个素数和 4 个线程，则第一个线程将采用p索引从 0 到 24 的值，第二个线程将采用索引从 25 到 49 的值，依此类推。第二个 for 循环应该在每个线程中从 0 运行到 100。使用这种方法，您可以计算所有可能的r价值观。