使并行 IntStream 更高效/更快？

Question

我已经寻找这个答案一段时间了，但找不到任何东西。

我正在尝试创建一个 IntStream ，它可以非常快速地找到素数（很多很多素数，非常快——几秒钟内数百万个）。

我目前正在使用这个并行流：

import java.util.stream.*;
import java.math.BigInteger;

public class Primes {
    public static IntStream stream() {
        return IntStream.iterate( 3, i -> i + 2 ).parallel()
                .filter( i -> i % 3 != 0 ).mapToObj( BigInteger::valueOf )
                .filter( i -> i.isProbablePrime( 1 ) == true )
                .flatMapToInt( i -> IntStream.of( i.intValue() ) );
    }
}

但生成数字需要很长时间。（生成 1,000,000 个素数需要 7546 毫秒）。

有没有任何明显的方法可以使其更高效/更快？

Answer 1

代码的高效并行处理存在两个常见问题。首先，使用iterate，这不可避免地需要前一个元素来计算下一个元素，这对于并行处理来说不是一个好的起点。其次，您使用的是无限流。有效的工作负载分割至少需要估计要处理的元素数量。

\n\n

由于您正在处理升序整数，因此在达到时存在明显的限制Integer.MAX_VALUE，但流实现并不知道您实际上正在处理升序数字，因此，会将形式上的无限流视为真正的无限。

\n\n

解决这些问题的解决方案是

\n\n

public static IntStream stream() {\n    return IntStream.rangeClosed(1, Integer.MAX_VALUE/2).parallel()\n            .map(i -> i*2+1)\n            .filter(i -> i % 3 != 0).mapToObj(BigInteger::valueOf)\n            .filter(i -> i.isProbablePrime(1))\n            .mapToInt(BigInteger::intValue);\n}\n

\n\n

但必须强调的是，在这种形式下，只有当您确实想要处理整个整数范围内的全部或大部分素数时，此解决方案才有用。一旦您应用skip或limit到流，并行性能就会显着下降，如这些方法的文档所指定。另外，使用filter with a predicate that accepts values in a smaller numeric range only, implies that there will be a lot of unnecessary work that would better not be done than done in parallel.

\n\n

您可以调整该方法以接收值范围作为参数，以调整源的范围IntStream to solve this.

\n\n

现在是强调算法相对于并行处理的重要性的时候了。考虑埃拉托斯特尼筛法. The following implementation

\n\n

public static IntStream primes(int max) {\n    BitSet prime = new BitSet(max>>1);\n    prime.set(1, max>>1);\n    for(int i = 3; i<max; i += 2)\n        if(prime.get((i-1)>>1))\n            for(int b = i*3; b>0 && b<max; b += i*2) prime.clear((b-1)>>1);\n    return IntStream.concat(IntStream.of(2), prime.stream().map(i -> i+i+1));\n}\n

\n\n

尽管不使用并行处理，但与其他方法相比，即使用作Integer.MAX_VALUE上限（使用.reduce((a,b) -> b)代替toArray或的终端操作测量），结果还是快了一个数量级forEach(System.out::println), to ensure complete processing of all values without adding additional storage or printing costs).

\n\n

要点是，isProbablePrime当您有特定的候选人或想要处理小范围的数字时（或者当数字远远超出int或什至是long range)\xc2\xb9, but for processing a large ascending sequence of prime numbers there are better approaches, and parallel processing is not the ultimate answer to performance questions.

\n\n\n\n

\xc2\xb9 考虑，例如

\n\n

Stream.iterate(new BigInteger("1000000000000"), BigInteger::nextProbablePrime)\n      .filter(b -> b.isProbablePrime(1))\n

\n