Stack überläuft aus tiefer Rekursion in Java?

StackOverflow https://stackoverflow.com/questions/860550

Frage

Nach einiger Erfahrung mit funktionalen Sprachen, ich beginne Rekursion mehr in Java zu verwenden, -. Aber die Sprache scheint von etwa 1000 mit einem relativ flachen Call-Stack haben

Gibt es eine Möglichkeit den Call-Stack größer zu machen? Wie kann ich Funktionen, die Millionen von Anrufen tief, wie in Erlang sind?

Ich bemerkte dies mehr und mehr, wenn ich tun Projekt Euler Probleme.

Danke.

War es hilfreich?

Lösung

Ich denke, man diese Parameter verwenden könnte

  

-ss STACK die native erhöhen   Stapelgröße oder

     

-oss STACK die Java erhöhen   Stapelgröße,

     

Der Standard nativen Stack-Größe ist 128k,   mit einem Mindestwert von 1000 Byte.   Die Standard-Java-Stack-Größe ist 400k,   mit einem Mindestwert von 1000 Byte.

http://edocs.bea.com/wls/docs61/ faq / java.html # 251197

EDIT:

Nach dem ersten Kommentar (Chuck's) zu lesen, sowie Wieder die Frage zu lesen und weiteren Antworten zu lesen, wie Id klarstellen, dass ich die Frage nur als „Erhöhung Stapelgröße“ interpretiert. Ich Artikel nicht zu sagen, die Absicht, dass Sie unendliche Stapel haben können, wie in der funktionalen Programmierung (ein Programmierparadigma, das nur ive seine Oberfläche gekratzt).

Andere Tipps

die Stapelgröße erhöht, wird nur als vorübergehender Verband dienen. Wie andere haben darauf hingewiesen, was Sie wirklich wollen, ist Endaufruf Eliminierung und Java ist dies aus verschiedenen Gründen nicht haben. Sie können jedoch betrügen, wenn Sie wollen.

Rote Pille in der Hand? OK, so wenden Sie sich bitte.

Es gibt Möglichkeiten, wie Sie Stapel für die Halde austauschen können. Zum Beispiel, anstatt einen rekursiven Aufruf innerhalb einer Funktion zu machen, haben sie eine faul Datenstruktur zurückkehren , die den Anruf macht, wenn ausgewertet. Anschließend können Sie den „Stack“ mit Java for-Konstrukt entspannen. Ich werde mit einem Beispiel demonstrieren. Betrachten Sie diesen Haskell Code: 

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Beachten Sie, dass diese Funktion nie das Ende der Liste auswertet. So ist die Funktion braucht nicht wirklich einen rekursiven Aufruf zu machen. In Haskell, es gibt tatsächlich ein thunk für den Schwanz, die jemals benötigt, wenn sie aufgerufen wird. Wir können in Java das gleiche tun (dies nutzt Klassen von rel="noreferrer">): 

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);}});}

Beachten Sie, dass Stream<A> besteht aus einem Wert vom Typ A und einen Wert vom Typ P1 die wie ein Thunk ist, die den Rest des Stroms liefert, wenn _1 () aufgerufen wird. Während es der rekursive Aufruf sicher wie Rekursion sieht, zur Karte nicht gemacht wird, sondern Teil der Stream-Datenstruktur wird.

Dies kann dann mit einem regulären for-Konstrukt abgewickelt werden. 

for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
  {System.out.println(b.head());}

Hier ist ein weiteres Beispiel, da Sie über Project Euler sprechen. Dieses Programm verwendet für beide Seiten rekursive Funktionen und nicht den Stapel nicht blasen, auch für Millionen von Anrufen: 

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())));}}

Ein andere Sache, die Sie tun können Stapel für die Halde zum Austausch verwenden mehr Threads . Die Idee ist, dass stattdessen einen rekursiven Aufruf zu machen, Sie eine Thunk erstellen, der den Anruf tätigt, Hand, dies zu einem neuen Thread thunk ab und die aktuelle Fadenausgang die Funktion lassen. Das ist die Idee hinter den Dingen wie Stackless Python.

Im Folgenden ist ein Beispiel für die in Java. Entschuldigt, dass es ein bisschen undurchsichtig ist zu sehen, ohne dass die import static Klauseln: 

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 wird durch einen Thread-Pool gesichert, und die promise Funktion einen Thunk an den Thread-Pool übergibt, eine Promise Rückkehr, die wie java.util.concurrent.Future sehr viel ist, nur besser. hier. Der Punkt ist, dass die oben beschriebene Methode faltet eine rechts rekursive Datenstruktur auf der rechten Seite in O (1) stack , die normalerweise tail-Call-Eliminierung erfordert. Deshalb haben wir effektiv TCE achived, im Austausch für einige Komplexität. Sie würden diese Funktion aufrufen wie folgt: 

Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000

Beachten Sie, dass diese letztere Technik sehr gut für nicht-lineare Rekursion funktioniert. Das heißt, es in konstanten Stack sogar Algorithmen laufen, die nicht über Endrekursion.

Eine andere Sache, die Sie tun können, ist eine Technik einsetzen namens trampolining . Ein Trampolin ist eine Berechnung, als eine Datenstruktur verdinglichter, die gestufte Durch werden kann. Die Functional Java-Bibliothek enthält eine Trampoline Datentyp, die ich schrieb, die Sie machen jeden Funktionsaufruf in einen Endaufruf effektiv lässt. Als Beispiel rel="noreferrer"> hier foldRightC, die nach rechts in konstanten Stapel faltet: 

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()));}});}

Es ist das gleiche Prinzip wie mehrere Threads verwendet werden, mit der Ausnahme, dass anstelle der einzelnen Schritte in einem eigenen Thread aufgerufen wird, wirkonstruieren jeden Schritt auf dem Heap, sehr ähnlich wie ein Stream verwenden, und dann laufen wir alle Schritte in einer einzigen Schleife mit Trampoline.run.

Es liegt an der JVM, ob oder nicht Endrekursion verwenden - ich weiß es nicht ohne weiteres, ob einer von ihnen tun, aber man sollte sich nicht darauf verlassen. Insbesondere würde die Stapelgröße zu ändern sehr selten sein das Richtige zu tun, wenn Sie einige harte Grenze, wie viele Ebenen der Rekursion hatte würden Sie tatsächlich nutzen, und Sie wusste genau, wie viel Stack-Speicher jedes einnehmen würde. Sehr zerbrechlich.

Grundsätzlich sollten Sie nicht unbegrenzt Rekursion in einer Sprache benutzen, die nicht für sich ist zu bauen. Sie werden stattdessen Iteration verwenden müssen, fürchte ich. Und ja, das kann ein leichter Schmerz manchmal: (

Wenn Sie fragen haben, sind Sie wahrscheinlich etwas zu tun falsch .

Jetzt, während Sie wahrscheinlich einen Weg finden, die Standard-Stack in Java zu erhöhen, lassen Sie mich meine nur hinzufügen, 2 cents, dass Sie wirklich einen anderen Weg finden müssen, um zu tun, was Sie tun wollen, anstatt sich auf eine erhöhte der Berufung stapeln.

Da die Java-Spezifikation macht es keinen zwingend für JVM Schwanz-Rekursion Optimierung Techniken zu implementieren, der einzige Weg, um das Problem zu bekommen, ist der Stapeldruck zu reduzieren, entweder durch die Anzahl der lokalen Variablen / Parameter zu reduzieren, die benötigt weiterverfolgen, oder im Idealfall werden, indem nur die Höhe der Rekursion erheblich verringert wird, oder einfach nur neu zu schreiben, ohne Rekursion überhaupt.

Die meisten funktionalen Sprachen haben Unterstützung für Endrekursion. Allerdings sind die meisten Java-Compiler unterstützen dies nicht. Stattdessen es eine andere Funktion Anruf. Das bedeutet, dass es immer auf der Anzahl der rekursiven Aufrufe eine obere Grenze, die Sie machen können (wie Sie schließlich aus Stapelspeicher ausgeführt werden).

Mit Endrekursion wieder verwenden Sie den Stapelrahmen der Funktion, die ist Rekursion, so dass Sie nicht über die gleichen Einschränkungen auf dem Stapel.

Sie können dies auf der Kommandozeile ein:

java -Xss8M Klasse

Clojure, die auf der Java VM läuft, möchte sehr viel Endrekursion Optimierung implementieren, aber es kann zu einer Einschränkung in dem JVM-Bytecode nicht wegen (ich weiß nicht, die Details). Als Folge kann es helfen, sich nur mit einer speziellen „wiederholen“ Form, die ein paar grundlegenden Funktionen implementiert Sie von richtigen Endrekursion erwarten würden.

Wie auch immer, bedeutet dies, dass die JVM zur Zeit kann nicht Unterstützung Endaufruf Optimierung. Ich würde dringend davon abgeraten Rekursion als allgemeines Schleifenkonstrukt auf der JVM zu verwenden. Meine persönliche Meinung ist, dass Java ist kein ausreichend hohes Niveau Sprache. 

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())));
}

Ich lief in das gleiche Problem, und am Ende Umschreiben die Rekursion in einen for-Schleife und das war der Trick.

in Eclipse, wenn Sie verwenden, setzen Sie -xss2m als vm Argumente.

oder

-xss2m direkt auf Kommandozeile. 

java -xss2m classname
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top