Переполнение стека из-за глубокой рекурсии в Java?
https://stackoverflow.com/questions/860550
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
После некоторого опыта работы с функциональными языками я начинаю больше использовать рекурсию в Java. Но стек вызовов этого языка, похоже, относительно неглубокий, около 1000.
Есть ли способ увеличить стек вызовов?Например, могу ли я создавать функции с глубиной в миллионы вызовов, как в Erlang?
Я замечаю это все больше и больше, когда решаю задачи проекта Эйлера.
Спасибо.
Решение
Я думаю, вы могли бы использовать эти параметры
-SS Stacksize для увеличения размера собственного стека или
-ОСС СТАКОВОГО для увеличения размера стека Java,
Размер собственного стека по умолчанию составляет 128 тыс., С минимальным значением 1000 байтов.Размер стека Java по умолчанию составляет 400K, с минимальным значением 1000 байтов.
http://edocs.bea.com/wls/docs61/faq/java.html#251197
РЕДАКТИРОВАТЬ:
Прочитав первый комментарий (Чака), а также перечитав вопрос и прочитав другие ответы, я хотел бы уточнить, что я интерпретировал вопрос как просто «увеличение размера стека».Я не собирался говорить, что у вас могут быть бесконечные стеки, как, например, в функциональном программировании (парадигма программирования, которую я только поверхностно рассмотрел).
Другие советы
Увеличение размера стопки послужит лишь временной повязкой.Как отмечали другие, на самом деле вам нужно устранение хвостовых вызовов, а в Java этого нет по разным причинам.Однако при желании вы можете обмануть.
Красная таблетка в руке?Хорошо, сюда, пожалуйста.
Существуют способы обмена стека на кучу.Например, вместо рекурсивного вызова внутри функции пусть она возвращает ленивая структура данных который делает вызов при оценке.Затем вы можете развернуть «стек» с помощью конструкции Java for.Я продемонстрирую на примере.Рассмотрим этот код Haskell:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
Обратите внимание, что эта функция никогда не оценивает хвост списка.Таким образом, функции на самом деле не нужно выполнять рекурсивный вызов.В Haskell он фактически возвращает думать для хвоста, который вызывается, если он когда-нибудь понадобится.Мы можем сделать то же самое в Java (при этом используются классы из Функциональная Java):
public <B> Stream<B> map(final F<A, B> f, final Stream<A> as)
{return as.isEmpty()
? nil()
: cons(f.f(as.head()), new P1<Stream<A>>()
{public Stream<A> _1()
{return map(f, as.tail);}});}
Обратите внимание, что Stream<A> состоит из значения типа A и значение типа P1 это похоже на преобразователь, который возвращает остальную часть потока при вызове _1().Хотя это определенно похоже на рекурсию, рекурсивный вызов карты не выполняется, а становится частью структуры данных Stream.
Затем это можно развернуть с помощью обычной конструкции for.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
Вот еще один пример, раз уж вы говорили о проекте Эйлера.Эта программа использует взаимно рекурсивные функции и не взрывает стек даже при миллионах вызовов:
import fj.*; import fj.data.Natural;
import static fj.data.Enumerator.naturalEnumerator;
import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd;
import fj.data.Stream; import fj.data.vector.V2;
import static fj.data.Stream.*; import static fj.pre.Show.*;
public class Primes
{public static Stream<Natural> primes()
{return cons(natural(2).some(), new P1<Stream<Natural>>()
{public Stream<Natural> _1()
{return forever(naturalEnumerator, natural(3).some(), 2)
.filter(new F<Natural, Boolean>()
{public Boolean f(final Natural n)
{return primeFactors(n).length() == 1;}});}});}
public static Stream<Natural> primeFactors(final Natural n)
{return factor(n, natural(2).some(), primes().tail());}
public static Stream<Natural> factor(final Natural n, final Natural p,
final P1<Stream<Natural>> ps)
{for (Stream<Natural> ns = cons(p, ps); true; ns = ns.tail()._1())
{final Natural h = ns.head();
final P1<Stream<Natural>> t = ns.tail();
if (naturalOrd.isGreaterThan(h.multiply(h), n))
return single(n);
else {final V2<Natural> dm = n.divmod(h);
if (naturalOrd.eq(dm._2(), ZERO))
return cons(h, new P1<Stream<Natural>>()
{public Stream<Natural> _1()
{return factor(dm._1(), h, t);}});}}}
public static void main(final String[] a)
{streamShow(naturalShow).println(primes().takeWhile
(naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}}
Еще одна вещь, которую вы можете сделать, чтобы обменять стек на кучу, — это использовать несколько потоков.Идея состоит в том, что вместо рекурсивного вызова вы создаете преобразователь, который выполняет вызов, передаете этот переходник новому потоку и позволяете текущему потоку выйти из функции. Это идея, лежащая в основе таких вещей, как Stackless Python.
Ниже приведен пример этого на Java.Извините, что это немного непрозрачно без import static положения:
public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
final F<A, F<B, B>> f,
final B b,
final List<A> as)
{return as.isEmpty()
? promise(s, P.p(b))
: liftM2(f).f
(promise(s, P.p(as.head()))).f
(join(s, new P1<Promise<B>>>()
{public Promise<B> _1()
{return foldRight(s, f, b, as.tail());}}));}
Strategy<Unit> s поддерживается пулом потоков, а promise функция передает переход в пул потоков, возвращая Promise, что очень похоже java.util.concurrent.Future, только лучше. Глянь сюда. Дело в том, что метод выше сворачивает праворекурсивную структуру данных вправо в стеке O(1), что обычно требует устранения хвостового вызова.Таким образом, мы фактически добились TCE в обмен на некоторую сложность.Вы могли бы вызвать эту функцию следующим образом:
Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000
Обратите внимание, что последний метод отлично работает для нелинейной рекурсии.То есть он будет работать в постоянном стеке, даже если алгоритмы не имеют хвостовых вызовов.
Еще одна вещь, которую вы можете сделать, это использовать технику, называемую прыжки на батуте.Батут — это вычисление, воплощенное в виде структуры данных, через которое можно пройти шаг за шагом.А Функциональная библиотека Java включает в себя Trampoline тип данных, который я написал, который эффективно позволяет превратить любой вызов функции в хвостовой вызов.В качестве примера вот батут foldRightC который складывается вправо в постоянном стеке:
public final <B> Trampoline<B> foldRightC(final F2<A, B, B> f, final B b)
{return Trampoline.suspend(new P1<Trampoline<B>>()
{public Trampoline<B> _1()
{return isEmpty()
? Trampoline.pure(b)
: tail().foldRightC(f, b).map(f.f(head()));}});}
Это тот же принцип, что и при использовании нескольких потоков, за исключением того, что вместо вызова каждого шага в отдельном потоке мы создаем каждый шаг в куче, что очень похоже на использование Stream, а затем выполняем все шаги в одном цикле с помощью Trampoline.run.
JVM решает, использовать или нет хвостовую рекурсию - я не знаю навскидку, использует ли кто-нибудь из них, но полагаться на нее не следует.В частности, изменение размера стека приведет очень редко бывает правильным, если только у вас нет жесткого ограничения на количество уровней рекурсии, которые вы действительно будете использовать, и вы точно не знаете, сколько места в стеке будет занимать каждый.Очень хрупкий.
По сути, вам не следует использовать неограниченную рекурсию в языке, который не предназначен для нее.Боюсь, вместо этого вам придется использовать итерацию.И да, иногда это может причинять небольшую боль :(
Если вам приходится спрашивать, возможно, вы делаете что-то не так.
Теперь, хотя вы, вероятно, можете найти способ увеличить стек по умолчанию в Java, позвольте мне добавить свои 2 цента, поскольку вам действительно нужно найти другой способ делать то, что вы хотите, вместо того, чтобы полагаться на увеличенный стек.
Поскольку спецификация Java не обязывает JVM реализовывать методы оптимизации хвостовой рекурсии, единственный способ обойти проблему — уменьшить нагрузку на стек, либо за счет уменьшения количества локальных переменных/параметров, которые необходимо сохранить. отследить или, в идеале, просто значительно снизить уровень рекурсии, или просто переписать без рекурсии вообще.
Большинство функциональных языков поддерживают хвостовую рекурсию.Однако большинство компиляторов Java этого не поддерживают.Вместо этого он выполняет еще один вызов функции.Это означает, что всегда будет существовать верхняя граница количества рекурсивных вызовов, которые вы можете сделать (поскольку в конечном итоге у вас закончится место в стеке).
При хвостовой рекурсии вы повторно используете кадр стека рекурсивной функции, поэтому у вас нет одинаковых ограничений на стек.
Вы можете установить это в командной строке:
класс java -Xss8M
Clojure, который работает на виртуальной машине Java, очень хотел бы реализовать оптимизацию хвостовых вызовов, но не может из-за ограничения в байт-коде JVM (подробностей я не знаю).Как следствие, он может помочь себе только с помощью специальной «рекурсивной» формы, которая реализует несколько основных функций, которые можно ожидать от правильной хвостовой рекурсии.
В любом случае, это означает, что JVM в настоящее время не могу поддержка оптимизации хвостового вызова.Я настоятельно рекомендую не использовать рекурсию в качестве общей конструкции цикла в JVM.Моё личное мнение таково, что Java не является языком достаточно высокого уровня.
public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
final F<A, F<B, B>> f,
final B b,
final List<A> as)
{
return as.isEmpty() ? promise(s, P.p(b))
: liftM2(f).f(promise(s, P.p(as.head())))
.f(join(s, new F<List<A>, P1<Promise<B>>>()
{
public Promise<B> f(List<A> l)
{
return foldRight(s, f, b, l);
}
}.f(as.tail())));
}
Я столкнулся с той же проблемой и в итоге оказался переписать рекурсию в цикл for и это сработало.
в eclipse, если вы используете, установите -xss2m как аргументы виртуальной машины.
или
-xss2m непосредственно в командной строке.
java -xss2m classname
