java - 如何使用并行流在 Java 中查找第 n 个素数

Question

似乎当使用有序流处理难以绑定(bind)的数值范围上的短路操作时，无法使用parallel()。例如:

public class InfiniteTest {

    private static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        if (x % 2 == 0 && x > 2) {
            return false;
        }
        // loop while i <= sqrt(x), using multiply for speedup
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static int findNthPrime(final int n) {
        // must not use infinite stream, causes OOME
        // but even big size causes huge slowdown
        IntStream.range(1, 1000_000_000)            
                // .parallel()
                .filter(InfiniteTest::isPrime)
                .skip(n - 1)
                .findFirst()
                .getAsInt();
    }

    public static void main(String[] args) {
        int n = 1000; // find the nth prime number
        System.out.println(findNthPrime(n));
    }
}

这个顺序流工作得很好。但是当我添加parallel()时，它似乎会永远运行(或者最后运行很长时间)。我认为这是因为流线程处理任意数字，而不是从流中的第一个数字开始。我不能有用bound the range of integers to scan for prime numbers .

那么有没有什么简单的技巧可以在没有陷阱的情况下与流并行运行这个问题，例如强制 splititerator 从流的开头提供工作 block ？或者从覆盖越来越多的数字范围的子流构建流？或者以某种方式设置 multithreading as producer/consumer pattern但是对于流呢？

类似的问题似乎都试图阻止使用并行:

• Generate infinite parallel stream
• Java 8, using .parallel in a stream causes OOM error
• Java 8's streams: why parallel stream is slower?

Answer 1

除了 2 和 3 之外，所有素数的形式都是 6n-1 或 6n+1。您已将 2 视为代码中的特殊情况。您可能想尝试将 3 也视为特殊的:

if (x % 3 == 0) {
    return x == 3;
}

然后运行两个并行流，一个测试 6n-1 形式的数字，从 5 开始，另一个测试 6n+1 形式的数字，从 7 开始。每个流一次可以跳过 6 个数字。

您可以使用Prime Number theorem估计第 n 个素数的值，并将搜索限制设置为略高于该估计值以确保安全。