Статьи

Остерегайтесь рекурсии в Java 8 [Primitive] Stream.iterate ()

Январь 14, 2019

Интересный вопрос Тагира Валеева о переполнении стека недавно привлек мое внимание. Для краткости (прочитайте вопрос подробнее), пока работает следующий код:

1
2
3
4
5
6
7
8
public static Stream<Long> longs() {
    return Stream.iterate(1L, i ->
        1L + longs().skip(i - 1L)
                    .findFirst()
                    .get());
}
 
longs().limit(5).forEach(System.out::println);

печать

1
2
3
4
5
1
2
3
4
5

Следующий похожий код не будет работать:

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

Вызывает StackOverflowError .

Конечно, этот вид рекурсивной итерации не является оптимальным. Это не было до Java 8, и, конечно же, не с новыми API. Но можно подумать, что это должно хотя бы сработать, верно? Причина, по которой он не работает, заключается в незначительной разнице в реализации между двумя методами iterate() в Java 8. Хотя Iterator потока ссылочного типа сначала возвращает seed а только затем продолжает итерацию, применяя функцию итерации к предыдущему значение:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
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() (и другим примитивным потокам):

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
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;
    }
};

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

  1. Проблемы оптимизации, когда итерационная функция стоит дорого
  2. Бесконечные рекурсии, когда итератор используется рекурсивно

В качестве обходного пути может быть лучше просто избежать рекурсии с помощью этого метода в потоках примитивного типа. К счастью, исправление в JDK 9 уже в процессе (как побочный эффект для улучшения функции): https://bugs.openjdk.java.net/browse/JDK-8072727

Ссылка: Следите за рекурсией в Java 8 [Primitive] Stream.iterate () от нашего партнера по JCG Лукаса Эдера в блоге JAVA, SQL и AND JOOQ .
41
Share: