java - La generación de primos con LongStream y jOOλ conduce a StackOverflowError

java-8 stack-overflow

Question

Para fines educativos, quiero crear una secuencia de números primos utilizando Java-8. Aquí está mi enfoque. El número x es primo si no tiene divisores primos que no excedan de sqrt(x) . Entonces, asumiendo que ya tengo una secuencia de números primos, puedo verificar esto con el siguiente predicado:

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

Aquí jOOλ biblioteca jOOλ (0.9.10 si es importante) solo para la operación limitWhile que está ausente en la API estándar de Stream. Así que ahora, sabiendo algo anterior prev , puedo generar el siguiente número primo iterando los números hasta que encuentre el que coincide con este predicado:

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()

Poniendo todo junto, escribí el siguiente método 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());
}

Ahora para lanzar esto yo uso:

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

Desafortunadamente, falla con el desagradable StackOverflowError que se ve así:

Exception in thread "main" java.lang.StackOverflowError
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$3.<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$2(Primes.java:13)
at Primes$$Lambda$4/1555009629.test(Unknown Source)
at java.util.stream.LongPipeline$8$1.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$0(Primes.java:14)
at Primes$$Lambda$1/918221580.applyAsLong(Unknown Source)
at java.util.stream.LongStream$1.nextLong(LongStream.java:747)
at java.util.Spliterators$LongIteratorSpliterator.tryAdvance(Spliterators.java:2009)
...

Podría pensar que merezco lo que obtengo: llamé a primes() recursivamente dentro del propio método primes() . Sin embargo, cambiemos el tipo de retorno del método a Stream<Long> y usemos Stream.iterate en Stream.iterate lugar, dejando todo lo demás como está:

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());
}

¡Ahora funciona como un encanto! No es muy rápido, pero en un par de minutos obtengo los números primos que superan los 1000000 sin ninguna excepción. El resultado es correcto, que puede compararse con la tabla de números primos:

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

Entonces, la pregunta es: ¿qué hay de malo con la primera versión basada en LongStream ? ¿Es jOOλ bug, JDK bug o estoy haciendo algo mal?

Tenga en cuenta que no estoy interesado en formas alternativas de generar números primos, quiero saber qué está mal con este código específico.

Answer 1

Parece que LongStream y Stream comportan de manera diferente cuando las secuencias se producen por iterate . El siguiente código ilustra la distinción:

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();

La salida es

LongStream incrementando 1

Por LongStream tanto, LongStream llamará a la función incluso si solo se necesita el primer elemento, mientras que Stream no. Esto explica la excepción que está recibiendo.

No sé si esto debería llamarse un error. Javadoc no especifica este comportamiento de una manera u otra, aunque sería bueno si fuera consistente.

Una forma de solucionarlo es codificar la secuencia inicial de números primos:

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

Puedes producir esta diferencia de maneras mucho más simples. Considere las siguientes dos versiones de secuencias de enumeración largas recursivas (igualmente ineficientes), que se pueden llamar de la siguiente manera para producir una secuencia de 1-5:

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

Provocará el mismo Error

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

Trabajará

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

La razón

La implementación de Stream.iterate() caja se optimiza de la siguiente manera:

    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);
        }
    };

a diferencia de la versión 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;
        }
    };

Observe cómo el iterador encuadrado llama a la función solo después de que se haya devuelto la semilla, mientras que el iterador primitivo almacena en caché el siguiente valor antes de devolver la semilla.

Esto significa que cuando se utiliza una función de iteración recursiva con el iterador primitivo, el primer valor de la secuencia nunca se puede producir, porque el siguiente valor se recupera prematuramente.

Esto probablemente se puede informar como un error JDK, y también explica la observación de Misha