使用 LongStream 和 jOOλ 生成素数会导致 StackOverflowError

Question

出于教育目的，我想使用 Java-8 创建一个素数流。这是我的方法。如果数 x 没有不超过 sqrt(x) 的质数约数，则它是质数。所以假设我已经有了一个素数流，我可以用下面的谓词来检查它：

x -> Seq.seq(primes()).limitWhile(p -> p <= Math.sqrt(x)).allMatch(p -> x % p != 0)

这里我使用了 jOOλ 库（如果重要的话是 0.9.10）只是为了 limitWhile 操作，这在标准 Stream API 中是不存在的。所以现在知道一些以前的素数 prev 我可以生成下一个素数迭代数字直到找到匹配这个谓词的那个：

prev -> LongStream.iterate(prev + 1, i -> i + 1)
                  .filter(x -> Seq.seq(primes()).limitWhile(p -> p <= Math.sqrt(x))
                                                .allMatch(p -> x % p != 0))
                  .findFirst()
                  .getAsLong()

将所有内容放在一起我编写了以下 primes() 方法：

public static LongStream primes() {
    return LongStream.iterate(2L, 
            prev -> LongStream.iterate(prev + 1, i -> i + 1)
                              .filter(x -> Seq.seq(primes())
                                              .limitWhile(p -> p <= Math.sqrt(x))
                                              .allMatch(p -> x % p != 0))
                              .findFirst()
                              .getAsLong());
}

现在启动这个我使用：

primes().forEach(System.out::println);

不幸的是，它失败了，令人不快的 WhosebugError 看起来像这样：

Exception in thread "main" java.lang.WhosebugError
at java.util.stream.ReferencePipeline$StatelessOp.opIsStateful(ReferencePipeline.java:624)
at java.util.stream.AbstractPipeline.<init>(AbstractPipeline.java:211)
at java.util.stream.ReferencePipeline.<init>(ReferencePipeline.java:94)
at java.util.stream.ReferencePipeline$StatelessOp.<init>(ReferencePipeline.java:618)
at java.util.stream.LongPipeline.<init>(LongPipeline.java:225)
at java.util.stream.LongPipeline.mapToObj(LongPipeline.java:224)
at java.util.stream.LongPipeline.boxed(LongPipeline.java:201)
at org.jooq.lambda.Seq.seq(Seq.java:2481)
at Primes.lambda(Primes.java:13)
at Primes$$Lambda/1555009629.test(Unknown Source)
at java.util.stream.LongPipeline.accept(LongPipeline.java:324)
at java.util.Spliterators$LongIteratorSpliterator.tryAdvance(Spliterators.java:2009)
at java.util.stream.LongPipeline.forEachWithCancel(LongPipeline.java:160)
at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:529)
at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:516)
at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:502)
at java.util.stream.FindOps$FindOp.evaluateSequential(FindOps.java:152)
at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
at java.util.stream.LongPipeline.findFirst(LongPipeline.java:474)
at Primes.lambda[=14=](Primes.java:14)
at Primes$$Lambda/918221580.applyAsLong(Unknown Source)
at java.util.stream.LongStream.nextLong(LongStream.java:747)
at java.util.Spliterators$LongIteratorSpliterator.tryAdvance(Spliterators.java:2009)
...

您可能认为我应得的：我在 primes() 方法本身内部递归调用了 primes()。但是，让我们将方法 return 类型更改为 Stream<Long> 并改用 Stream.iterate，其他一切保持原样：

public static Stream<Long> primes() {
    return Stream.iterate(2L, 
            prev -> LongStream.iterate(prev + 1, i -> i + 1)
                              .filter(x -> Seq.seq(primes())
                                              .limitWhile(p -> p <= Math.sqrt(x))
                                              .allMatch(p -> x % p != 0))
                              .findFirst()
                              .getAsLong());
}

现在它就像一个魅力！不是很快，但在几分钟内我得到了超过 1000000 的质数，没有任何例外。结果是正确的，可以对照质数的table来检查：

System.out.println(primes().skip(9999).findFirst());
// prints Optional[104729] which is actually 10000th prime.

所以问题是：第一个基于 LongStream 的版本有什么问题？是 jOOλ 错误，JDK 错误还是我做错了什么？

请注意，我对生成素数的其他方法不感兴趣，我想知道这段特定代码有什么问题。

Answer 1

似乎 LongStream 和 Stream 在流由 iterate 生成时表现不同。下面的代码说明了区别：

LongStream.iterate(1, i -> {
    System.out.println("LongStream incrementing " + i);
    return i + 1;
}).limit(1).count();

Stream.iterate(1L, i -> {
    System.out.println("Stream incrementing " + i);
    return i + 1;
}).limit(1).count();

输出为

LongStream incrementing 1

因此 LongStream 将调用该函数，即使只需要第一个元素也是如此，而 Stream 则不会。这解释了您遇到的异常。

我不知道这是否应该被称为错误。 Javadoc 没有以一种或另一种方式指定此行为，但如果它是一致的就更好了。

修复它的一种方法是对素数的初始序列进行硬编码：

public static LongStream primes() {
    return LongStream.iterate(2L,
        prev -> prev == 2 ? 3 : 
                prev == 3 ? 5 :
                LongStream.iterate(prev + 1, i -> i + 1)
                        .filter(x -> Seq.seq(primes())
                            .limitWhile(p -> p <= Math.sqrt(x))
                            .allMatch(p -> x % p != 0)
                        ).findFirst()
                        .getAsLong());

Answer 2

您可以用更简单的方法产生这种差异。考虑以下两个版本的（同样低效的）递归长枚举流，可以按如下方式调用它们以生成 1-5 的序列：

longs().limit(5).forEach(System.out::println);

会导致同样的 WhosebugError

public static LongStream longs() {
    return LongStream.iterate(1L, i ->
        1L + longs().skip(i - 1L)
                    .findFirst()
                    .getAsLong());
}

会起作用

public static Stream<Long> longs() {
    return Stream.iterate(1L, i ->
        1L + longs().skip(i - 1L)
                    .findFirst()
                    .get());
}

原因

盒装Stream.iterate()实现优化如下：

    final Iterator<T> iterator = new Iterator<T>() {
        @SuppressWarnings("unchecked")
        T t = (T) Streams.NONE;

        @Override
        public boolean hasNext() {
            return true;
        }

        @Override
        public T next() {
            return t = (t == Streams.NONE) ? seed : f.apply(t);
        }
    };

与 LongStream.iterate() 版本不同：

    final PrimitiveIterator.OfLong iterator = new PrimitiveIterator.OfLong() {
        long t = seed;

        @Override
        public boolean hasNext() {
            return true;
        }

        @Override
        public long nextLong() {
            long v = t;
            t = f.applyAsLong(t);
            return v;
        }
    };

注意装箱迭代器如何仅在返回种子后调用函数，而原始迭代器在返回种子之前缓存下一个值。

这意味着当您将递归迭代函数与原始迭代器一起使用时，永远无法生成流中的第一个值，因为过早地获取了下一个值。

这可能会被报告为一个 JDK 错误，并且

使用 LongStream 和 jOOλ 生成素数会导致 StackOverflowError

Generating primes with LongStream and jOOλ leads to StackOverflowError

java

stack-overflow

java-8

java-stream

会导致同样的 WhosebugError

会起作用

原因