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

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

Здесь я использовал jOOλ library (0.9.10, если это имеет значение) только для операции limitWhile, которая отсутствует в стандартном потоковом API. Итак, теперь, зная некоторые предыдущие простые prev, я могу сгенерировать следующее простое итерационное число, пока не найду тот, который соответствует этому предикату:

Собирая все вместе, я написал следующий метод primes():

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

Вы можете подумать, что я заслуживаю того, что получаю: я вызывал primes() рекурсивно внутри самого метода primes(). Однако пусть просто измените тип возвращаемого метода на Stream<Long> и вместо этого используйте Stream.iterate, оставив все остальное как есть:

Теперь это работает как шарм! Не очень быстро, но через пару минут я получаю простые числа, превышающие 1000000 без каких-либо исключений. Результат правильный, который можно проверить по таблице простых чисел:

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

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

Ответы

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