在Java中正确使用并行流

Question

我正在尝试Java中的并行流,为此,我有以下代码来计算以前的素数n.

基本上我有两种方法

• calNumberOfPrimes(long n) - 4种不同的变种
• isPrime(long n) - 2种不同的变种

实际上我有上述每种方法的两种不同变体,一种是使用并行流的变体,另一种是不使用并行流的变体.

    // itself uses parallel stream and calls parallel variant isPrime
    private static long calNumberOfPrimesPP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .parallel()
                .filter(i -> isPrimeParallel(i))
                .count();
    }

    // itself uses parallel stream and calls non-parallel variant isPrime
    private static long calNumberOfPrimesPNP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .parallel()
                .filter(i -> isPrimeNonParallel(i))
                .count();
    }

    // itself uses non-parallel stream and calls parallel variant isPrime
    private static long calNumberOfPrimesNPP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .filter(i -> isPrimeParallel(i))
                .count();
    }

    // itself uses non-parallel stream and calls non-parallel variant isPrime
    private static long calNumberOfPrimesNPNP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .filter(i -> isPrimeNonParallel(i))
                .count();
    }
    // uses parallel stream
    private static boolean isPrimeParallel(long n) {
        return LongStream
                .rangeClosed(2, (long) Math.sqrt(n))
                .parallel()
                .noneMatch(i -> n % i == 0);
    }

    // uses non-parallel stream
    private static boolean isPrimeNonParallel(long n) {
        return LongStream
                .rangeClosed(2, (long) Math.sqrt(n))
                .noneMatch(i -> n % i == 0);
    }

我试图找出哪些calNumberOfPrimesPP,哪个calNumberOfPrimesPNP,calNumberOfPrimesNPP并且calNumberOfPrimesNPNP是最佳的并行流的正确使用效率和为什么它是最好的.

我尝试将所有这4种方法计时50次,并使用以下代码取平均值:

    public static void main(String[] args) throws Exception {
        int iterations = 50;
        int n = 1000000;
        double pp, pnp, npp, npnp;
        pp = pnp = npp = npnp = 0;
        for (int i = 0; i < iterations; i++) {
            Callable<Long> runner1 = () -> calNumberOfPrimesPP(n);
            Callable<Long> runner2 = () -> calNumberOfPrimesPNP(n);
            Callable<Long> runner3 = () -> calNumberOfPrimesNPP(n);
            Callable<Long> runner4 = () -> calNumberOfPrimesNPNP(n);

            pp += TimeIt.timeIt(runner1);
            pnp += TimeIt.timeIt(runner2);
            npp += TimeIt.timeIt(runner3);
            npnp += TimeIt.timeIt(runner4);
        }
        System.out.println("___________final results___________");
        System.out.println("avg PP = " + pp / iterations);
        System.out.println("avg PNP = " + pnp / iterations);
        System.out.println("avg NPP = " + npp / iterations);
        System.out.println("avg NPNP = " + npnp / iterations);
    }

TimeIt.timeIt只需以毫秒为单位返回执行时间.我得到以下输出:

___________final results___________
avg PP = 2364.51336366
avg PNP = 265.27284506
avg NPP = 11424.194316620002
avg NPNP = 1138.15516624

现在我试图推断上述执行时间:

• 该PP变种是不一样快PNP变,因为所有的并行数据流使用普通的fork-join线程池,如果我们提交一个长时间运行的任务,我们正在有效地阻止在池中的所有线程.
• 但是上述论点也适用于NPP变体,因此NPP变体也应该与PNP变体一样快.(但事实并非如此,NPP变数在时间上最差).有人可以解释一下这背后的原因吗？

我的问题:

• 我的推理是否适用于PNP变体的小运行时间？
• 我错过了什么吗？
• 为什么NPP变体是最差的(就运行时间而言)？

TimeIt测量时间如何:

class TimeIt {
    private TimeIt() {
    }

    /**
     * returns the time to execute the Callable in milliseconds
     */
    public static <T> double timeIt(Callable<T> callable) throws Exception {
        long start = System.nanoTime();
        System.out.println(callable.call());
        return (System.nanoTime() - start) / 1.0e6;
    }
}

PS:我知道这不是计算素数的最佳方法. Eratosthenes的筛子和其他更复杂的方法就是这样做的.但是通过这个例子,我只想了解并行流的行为以及何时使用它们.

Answer 1

我想,很清楚,NPP为何如此缓慢.

将结果数字排列在表格中:

       |    _P    |   _NP
-------+----------+---------
  P_   |   2364   |   265
-------+----------+---------
  NP_  |  11424   |  1138
-------+----------+---------

所以你看到外流并行时总是更快.这是因为在流中还有很多工作要做.因此,与要完成的工作相比,处理并行流的额外开销较低.

您还可以看到,当内部流不平行时,它总是更快.isPrimeNonParallel比...更快isPrimeParallel.这是因为在流中没有太多工作要做.在大多数情况下,经过几个步骤后,很明显这个数字不是素数.一半的数字是均匀的(只有一步).与要完成的工作相比,处理并行流的额外开销很高.