자바의 깊은 재귀에서 오버플로 스택?
https://stackoverflow.com/questions/860550
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
기능적 언어에 대한 경험이 난 후에는 자바에서 재귀를 더 많이 사용하기 시작했지만 언어는 약 1000의 상대적으로 얕은 통화 스택을 갖는 것 같습니다.
콜 스택을 더 크게 만들 수있는 방법이 있습니까? Erlang에서와 같이 수백만 건의 전화가 깊은 기능을 할 수 있습니까?
나는 프로젝트 euler 문제를 할 때 이것을 점점 더 많이 알아 차리고 있습니다.
감사.
해결책
이 매개 변수를 사용할 수 있다고 생각합니다
-SS Stacksize 기본 스택 크기를 늘리기 위해
-OSS 스택 크기 Java 스택 크기를 높이기 위해
기본 기본 스택 크기는 128K이며 최소값은 1000 바이트입니다. 기본 Java 스택 크기는 400K이며 최소값은 1000 바이트입니다.
http://edocs.bea.com/wls/docs61/faq/java.html#251197
편집하다:
첫 번째 의견 (척)을 읽고 질문을 읽고 또 다른 답변을 읽은 후, 나는 그 질문을 단지 "스택 크기 증가"로 해석했음을 분명히하고 싶습니다. 나는 당신이 기능 프로그래밍과 같은 무한 스택을 가질 수 있다고 말하지 않았다 (표면 만 긁힌 프로그래밍 패러다임).
다른 팁
스택 크기를 증가시키는 것은 임시 붕대 역할 만합니다. 다른 사람들이 지적했듯이, 당신이 정말로 원하는 것은 Tail Call 제거이며, Java는 여러 가지 이유로 이것을 가지고 있지 않습니다. 그러나 원한다면 속임수를 낼 수 있습니다.
손에 붉은 알약? 좋아, 이렇게 제발.
힙으로 스택을 교환 할 수있는 방법이 있습니다. 예를 들어, 함수 내에서 재귀를 호출하는 대신 게으른 데이터 구조 그것은 평가 될 때 호출을합니다. 그런 다음 Java의 For-Construct로 "스택"을 풀 수 있습니다. 나는 예제로 시연 할 것이다. 이 haskell 코드를 고려하십시오.
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
이 기능은 목록의 꼬리를 절대 평가하지 않습니다. 따라서 기능은 실제로 재귀적인 호출을 할 필요가 없습니다. Haskell에서는 실제로 a 멍청이 꼬리의 경우, 필요한 경우 호출됩니다. 우리는 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 ()가 호출 될 때 나머지 스트림을 반환하는 펑크와 같습니다. 확실히 재귀처럼 보이지만, 재귀적인 맵에 대한 호출은 이루어지지 않았지만 스트림 데이터 구조의 일부가됩니다.
그런 다음 정기적 인 구성으로 풀릴 수 있습니다.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
Project Euler에 대해 이야기 한 이후로 또 다른 예가 있습니다. 이 프로그램은 상호 재귀 함수를 사용하며 수백만 건의 통화조차도 스택을 날리지 않습니다.
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
이 후자의 기술은 비선형 재귀에 완벽하게 작동합니다. 즉, 꼬리 호출이없는 알고리즘도 일정한 스택으로 실행됩니다.
당신이 할 수있는 또 다른 일은 트램폴린. 트램폴린은 계산으로, 데이터 구조로 재구성되어 단계를 밟을 수 있습니다. 그만큼 기능적 자바 라이브러리 포함 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 Spec은 JVM이 꼬리 수익성 최적화 기술을 구현하는 데 필수적이지 않기 때문에 문제를 해결하는 유일한 방법은 유지 해야하는 로컬 변수/매개 변수의 수를 줄임으로써 스택 압력을 줄이는 것입니다. 재귀 수준을 크게 줄이거 나 재귀없이 다시 쓰는 것만으로 또는 이상적으로 추적하십시오.
대부분의 기능 언어는 꼬리 재귀를 지원합니다. 그러나 대부분의 Java 컴파일러는이를 지원하지 않습니다. 대신 다른 기능 호출을합니다. 이것은 당신이 만들 수있는 재귀 통화 수에 항상 상한이있을 것임을 의미합니다 (결국 스택 공간이 부족할 때).
꼬리 재귀를 사용하면 재발하는 함수의 스택 프레임을 재사용하므로 스택에 동일한 제약 조건이 없습니다.
이것을 명령 선에서 설정할 수 있습니다.
Java -xss8m 클래스
Java VM에서 실행되는 Clojure는 Tail Call 최적화를 구현하는 것을 매우 좋아하지만 JVM Bytecode의 제한으로 인해 할 수는 없습니다 (세부 사항을 모릅니다). 결과적으로, 그것은 특별한 "recur"형태로만 도움이 될 수 있으며, 이는 적절한 꼬리 재귀에서 기대할 몇 가지 기본 기능을 구현합니다.
어쨌든 이것은 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-Loop로 다시 작성합니다 그리고 그것은 속임수를 만들었습니다.
사용중인 경우 Eclipse에서 설정하십시오 -xss2m VM 주장으로.
또는
-xss2m 명령 선에 직접 직접.
java -xss2m classname
