Подтвердить что ты не робот

Генерация простых чисел с помощью LongStream и jOOλ приводит к StackOverflowError

В образовательных целях я хочу создать поток простых чисел с использованием Java-8. Вот мой подход. Число x является простым, если оно не имеет простых делителей, не превышающих sqrt(x). Поэтому, предполагая, что у меня уже есть поток простых чисел, я могу проверить это со следующим предикатом:

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

Здесь я использовал jOOλ library (0.9.10, если это имеет значение) только для операции limitWhile, которая отсутствует в стандартном потоковом 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);

К сожалению, он не работает с неприятным StackOverflowError, который выглядит так:

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

Вы можете подумать, что я заслуживаю того, что получаю: я вызывал primes() рекурсивно внутри самого метода primes(). Однако пусть просто измените тип возвращаемого метода на 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 без каких-либо исключений. Результат правильный, который можно проверить по таблице простых чисел:

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

Итак, вопрос: что случилось с первой версией на основе LongStream? Это ошибка jOOλ, ошибка JDK или я что-то не так?

Обратите внимание, что меня не интересуют альтернативные способы генерации простых чисел, я хочу знать, что не так с этим конкретным кодом.

4b9b3361

ОТВЕТЫ

Ответ 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 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());

Ответ 2

Вы можете произвести эту разницу гораздо проще. Рассмотрим следующие две версии (одинаково неэффективных) рекурсивных длинных перечислительных потоков, которые можно вызвать следующим образом, чтобы получить последовательность из 1-5:

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

Вызывает тот же StackOverflowError

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, а также объясняет наблюдение Миши