Pila trabocca dal profondo ricorsione in Java?

Question

Dopo alcune esperienze con linguaggi funzionali, sto iniziando a utilizzare la ricorsione più in Java -. Ma il linguaggio sembra avere una chiamata pila relativamente poco profondo di circa 1000

C'è un modo per rendere lo stack più grande chiamata? Come posso fare le funzioni che sono milioni di chiamate in profondità, come in Erlang?

sto notando questo sempre di più quando lo faccio problemi Project Euler.

Grazie.

Answer 1

Credo che si potrebbe utilizzare questi parametri

  

-ss stacksize per aumentare il nativo   stack o

     

-oss stacksize per aumentare la Java   dimensione dello stack,

     

La dimensione di stack nativo di default è 128k,   con un valore minimo di 1000 byte.   La dimensione di stack Java di default è 400k,   con un valore minimo di 1000 byte.

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

EDIT:

Dopo aver letto il primo commento (Chuck's), così come ri lettura della domanda e la lettura di un altro risponde, come i'd a precisare che ho interpretato la questione solo come "aumenta la dimensione del stack". Mi hanno ragione't intenzione di dire che si può avere infinite pile, come ad esempio nella programmazione funzionale (un paradigma di programmazione che Ive solo scalfito la superficie).

Answer 2

L'aumento delle dimensioni dello stack servirà solo come un bendaggio temporaneo. Come altri hanno fatto notare, cosa si vuole veramente è l'eliminazione di chiamata coda, e Java non ha questo per vari motivi. Tuttavia, si può barare, se vuoi.

La pillola rossa in mano? OK, in questo modo si prega.

Ci sono modi in cui è possibile scambiare stack per heap. Ad esempio, invece di fare una chiamata ricorsiva all'interno di una funzione, farlo restituire un datastructure artificiale che effettua la chiamata quando valutato. È quindi possibile svolgere il "stack" con Java di per-costrutto. Io dimostrare con un esempio. Considerate questo codice Haskell:

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

Si noti che questa funzione non valuta la coda della lista. Quindi la funzione in realtà non ha bisogno di fare una chiamata ricorsiva. In Haskell, in realtà restituisce un thunk per la coda, che si chiama se è sempre necessario. Siamo in grado di fare la stessa cosa in Java (questo utilizza le classi da Java funzionale ):

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

Si noti che Stream<A> consiste in un valore di tipo A e un valore di tipo P1 che è come un thunk che restituisce il resto del flusso quando viene chiamata _1 (). Mentre sembra certamente come ricorsione, la chiamata ricorsiva alla mappa non è fatta, ma diventa parte del datastructure Stream.

Questo può essere svolto con un normale per-costrutto.

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

Ecco un altro esempio, dal momento che si stava parlando di Project Euler. Questo programma utilizza le funzioni ricorsive reciprocamente e non suona lo stack, anche per milioni di chiamate:

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

Un'altra cosa che potete fare per lo scambio di stack per heap è quello di utilizzare più thread . L'idea è che invece di fare una chiamata ricorsiva, si crea un thunk che effettua la chiamata, lato questo thunk fuori ad un nuovo thread e lasciare che l'uscita thread corrente della funzione. Questa è l'idea che sta dietro le cose come Stackless Python.

Il seguente è un esempio di questo in Java. Scuse che è un po 'opaco a guardare senza le clausole 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 è sostenuta da un pool di thread, e la funzione promise porge un tonfo al pool di thread, restituendo un Promise, che è molto simile a java.util.concurrent.Future, solo meglio. Vedi qui. Il punto è che il metodo di cui sopra pieghe un datastructure destro ricorsiva a destra in O (1) pila , che richiede normalmente eliminazione della coda di guardia. Così abbiamo effettivamente achived TCE, in cambio di una certa complessità. Si potrebbe chiamare questa funzione come segue:

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

Si noti che quest'ultima tecnica funziona perfettamente bene per non lineare ricorsione. Cioè, verrà eseguito in costante pila anche algoritmi che non hanno chiamate coda.

Un'altra cosa che puoi fare è impiegare una tecnica chiamata trampolino . Un trampolino è un calcolo, reificata come una struttura di dati, che possono essere entrò. biblioteca funzionale Java La include una Trampoline tipo di dati che ho scritto, che consente in modo efficace di trasformare qualsiasi chiamata di funzione in una chiamata coda. Come esempio ecco un trampolined foldRightC che si piega a destra in pila costante:

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

E 'lo stesso principio utilizzando più thread, salvo che invece di invocare ogni passo nel proprio thread, si costruisce ogni passaggio sul mucchio, molto simile utilizzando un Stream, e poi eseguire tutte le fasi di uno Loop singolo con Trampoline.run.

Answer 3

E 'fino alla JVM o meno di utilizzare la ricorsione in coda - non so due piedi se qualcuno di loro lo fanno, ma non si dovrebbe fare affidamento su di esso. In particolare, la modifica della dimensione dello stack sarebbe molto raramente essere la cosa giusta da fare, a meno che non hai avuto qualche limite rigido di come molti livelli di ricorsione si sarebbe effettivamente utilizzare, e si sapeva esattamente quanto spazio di stack ogni avrebbe preso su. Molto fragile.

In sostanza, non si dovrebbe usare la ricorsione sconfinata in una lingua che non è costruire per esso. Dovrete usare l'iterazione invece, temo. E sì, che può essere un leggero dolore a volte: (

Answer 4

Se si deve chiedere, probabilmente stai facendo qualcosa sbagliato.

Ora, mentre si può probabilmente trovare un modo per aumentare la pila di default in java, vorrei solo aggiungere i miei 2 centesimi a che si ha realmente bisogno di trovare un altro modo per fare ciò che si vuole fare, invece di basarsi su un aumento impilare.

Poiché specifiche Java non lo rende obbligatorio per JVM implementare tecniche di ottimizzazione coda-ricorsione, l'unico modo per aggirare il problema è quello di ridurre la pressione pila, sia riducendo il numero di variabili locali / parametri che deve per essere tenuto traccia di, o idealmente semplicemente riducendo il livello di ricorsione in modo significativo, o semplicemente riscrivere senza ricorsione a tutti.

Answer 5

lingue più funzionali hanno il supporto per la ricorsione in coda. Tuttavia, la maggior parte dei compilatori Java non supportano questa. Invece nuova chiamata di funzione. Questo significa che ci sarà sempre un limite superiore al numero di chiamate ricorsive si possono fare (come più volte si esaurisce lo spazio dello stack).

Con coda ricorsione si riutilizzare lo stack frame della funzione che viene recursing, in modo da non avere gli stessi vincoli sulla pila.

Answer 6

È possibile impostare questo sulla riga di comando:

java classe -Xss8M

Answer 7

Clojure, che gira su Java VM, piacerebbe molto per implementare l'ottimizzazione chiamata coda, ma non può a causa di una limitazione nel bytecode JVM (io non conosco i dettagli). Di conseguenza, si può solo aiutare con sé una forma speciale di "ricorrere", che implementa alcune caratteristiche di base che ci si aspetta da una corretta ricorsione di coda.

In ogni caso, questo significa che la JVM attualmente non possono Ottimizzazione supporto chiamata coda. Vorrei suggerire di non utilizzare la ricorsione come un costrutto iterativo generale sulla JVM. La mia opinione personale è che Java non è un linguaggio di livello sufficientemente elevato.

Answer 8

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

Answer 9

Ho incontrato lo stesso problema, e ha finito per riscrivere la ricorsione in un ciclo for e che ha fatto il trucco.

Answer 10

in Eclipse se si utilizza, impostare -xss2m come argomenti VM.

o

-xss2m direttamente sulla riga di comando.

java -xss2m classname