Desbordamientos de pila de profunda recursividad en Java?
https://stackoverflow.com/questions/860550
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Después de la experiencia con los lenguajes funcionales, estoy empezando a usar recursividad más en Java - Pero el lenguaje parece tener una relativamente baja de la pila de llamadas es de alrededor de 1000.
Es allí una manera de hacer que la pila de llamadas más grande?Como puedo hacer que funciones que son millones de llamadas profundo, como en Erlang?
Estoy notando más y más cuando tengo que hacer el Proyecto de Euler problemas.
Gracias.
Solución
Creo que se puede utilizar estos parámetros
-SS STACKSIZE para aumentar el nativo tamaño de la pila o
-oss STACKSIZE para aumentar el Java tamaño de la pila,
El tamaño de la pila nativa por defecto es 128k, con un valor mínimo de 1000 bytes. El tamaño de la pila de Java por defecto es 400k, con un valor mínimo de 1000 bytes.
http://edocs.bea.com/wls/docs61/ FAQ / java.html # 251197
EDIT:
Después de leer el primer comentario (de Chuck), así como volver a leer la pregunta y la lectura de otras respuestas, Me gustaría aclarar que interpreté la pregunta simplemente como "aumentar tamaño de la pila". Google No tiene la intención de decir que usted puede tener infinitas pilas, como en la programación funcional (un paradigma de programación que sólo he arañado la superficie).
Otros consejos
Aumentar el tamaño de la pila sólo servirá como un vendaje temporal.Como otros han señalado, lo que realmente quiere es la cola de llamadas eliminación, y Java no tiene esto por varias razones.Sin embargo, usted puede hacer trampa, si quieres.
Píldora roja en la mano?OK, de esta manera, por favor.
Hay maneras en que usted puede cambiar la pila heap.Por ejemplo, en lugar de hacer una llamada recursiva dentro de una función, tiene que devolver un perezoso discbased que hace la llamada cuando se evalúan.Usted puede descansar la "pila" con Java para construir.Voy a demostrar con un ejemplo.Considere la posibilidad de este código Haskell:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
Tenga en cuenta que esta función nunca se evalúa la cola de la lista.Así que la función en realidad no se necesita para hacer una llamada recursiva.En Haskell, se devuelve realmente un thunk para la cola, que se llama a si alguna vez lo necesita.Podemos hacer lo mismo en Java (esto utiliza las clases de Funcional 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);}});}
Tenga en cuenta que Stream<A> consta de un valor de tipo A y un valor de tipo P1 que es como un procesador que devuelve el resto de la secuencia cuando _1() es llamado.Aunque ciertamente parece como la recursividad, la llamada recursiva a la mapa no se hace, pero se convierte en parte de la Corriente de discbased.
Esto puede ser compensados con una regular para construir.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
He aquí otro ejemplo, ya que estaban hablando acerca de Project Euler.Este programa utiliza mutuamente funciones recursivas y no toca la pila, incluso para millones de llamadas:
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())));}}
Otra cosa que puedes hacer a cambio de la pila heap es el uso de varios subprocesos.La idea es que en lugar de hacer una llamada recursiva, crear un procesador que realiza la llamada, la mano de este procesador a un nuevo hilo y dejar que el subproceso actual salida de la función. Esta es la idea detrás de cosas como Stackless Python.
El siguiente es un ejemplo de que en Java.Disculpas que es un poco opaco a mirar sin el import static cláusulas:
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 está respaldado por un grupo de subprocesos, y el promise la función de manos de un procesador para el grupo de subprocesos, la devolución de un Promise, que es muy parecida a la de java.util.concurrent.Future, sólo que mejor. Vea aquí. El punto es que el método anterior los pliegues de un derecho recursivo discbased a la derecha en O(1) pila, que normalmente requiere de la cola de llamadas eliminación.Así que en realidad hemos logrado TCE, a cambio de cierta complejidad.Usted podría llamar a esta función de la siguiente manera:
Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000
Tenga en cuenta que esta última técnica funciona perfectamente bien para no lineal de la recursividad.Es decir, que se ejecute en constante pila incluso algoritmos que no tienen cola de llamadas.
Otra cosa que puedes hacer es emplear una técnica llamada trampolining.Una cama elástica es un cálculo, se concreta como una estructura de datos, que puede ser un paso a través.El Funcional de la biblioteca de Java incluye un Trampoline tipo de datos que escribí, lo que efectivamente permite convertir cualquier llamada a la función en una cola de llamadas.Como un ejemplo aquí está una trampolined foldRightC que se dobla a la derecha en la constante de la pila:
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 el mismo principio que el uso de múltiples hilos, excepto que en lugar de invocar a cada paso en su propio hilo, se construye a cada paso en el montón, mucho como el uso de una Stream, y , a continuación, volvemos a ejecutar todos los pasos en un solo bucle con Trampoline.run.
Todo depende de la JVM si debe o no utilizar la recursión de cola - No sé improvisada si alguno de ellos lo hacen, pero no se debe confiar en ella. En particular, el cambio del tamaño de la pila sería muy rara vez será lo que hay que hacer, a menos que tenía un límite duro de cuántos niveles de recursividad se usaría en realidad, y que sabía exactamente cuánto espacio de pila cada tomaría. Muy frágil.
Básicamente, no se debe utilizar la recursividad ilimitada en un idioma que no está construido para ello. Vas a tener que utilizar iteración en cambio, me temo. Y sí, eso puede ser un dolor leve a veces: (
Si usted tiene que pedir, es probable que hacer algo mal.
Ahora, si bien es probable que pueda encontrar una manera de aumentar la pila por defecto en Java, permítanme añadir mis 2 centavos en la que realmente tiene que encontrar otra manera de hacer lo que quiere hacer, en lugar de depender de un aumento apilar.
Desde la especificación de Java no significa que sea obligatorio para la JVM para poner en práctica las técnicas de optimización de la cola-recursividad, la única forma de evitar el problema es reducir la presión de la pila, ya sea mediante la reducción del número de variables / parámetros locales que necesita mantenerse un registro de, o, idealmente, con sólo reducir el nivel de recursividad significativamente, o simplemente volver a escribir sin recursividad en absoluto.
Lenguas más funcionales tienen soporte para la recursión de cola. Sin embargo, la mayoría de los compiladores Java no soportan esto. En su lugar, realice otra llamada a la función. Esto significa que siempre habrá un límite superior en el número de llamadas recursivas que puede hacer (como que finalmente va a ejecutar sin espacio de pila).
Con la recursión de cola que volver a utilizar el marco de pila de la función que se recursiva, por lo que no tienen las mismas limitaciones en la pila.
Puede configurar esto en la línea de comandos:
-Xss8M clase java
Clojure, que se ejecuta en la máquina virtual de Java, le gustaría mucho para implementar la optimización de llamada de cola, pero no puede debido a una restricción en el código de bytes JVM (no sé los detalles). Como consecuencia, sólo puede ayudarse a sí misma con una forma especial "se repita", que implementa algunas características básicas que se espera de la recursión de cola adecuada.
De todos modos, esto significa que la JVM actualmente no puede Optimización de apoyo llamada de cola. Me gustaría sugerir fuertemente no utilizar la recursividad como una construcción general de un bucle en la JVM. Mi opinión personal es que Java no es un lenguaje de nivel suficientemente alto.
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())));
}
Me encontré con el mismo problema, y terminó la reescritura de la recursividad en un bucle y que hizo el truco.
eclipse si está utilizando, ajustar -xss2m como argumentos vm.
o
-xss2m directamente en la línea de comandos.
java -xss2m classname
