¿Cómo maneja tu lenguaje favorito la recursividad profunda?[cerrado]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Recientemente comencé a aprender Python y me sorprendió bastante encontrar un límite de recursividad profunda de 1000 (de forma predeterminada).Si lo configuras lo suficientemente alto, alrededor de 30000, falla con una falla de segmentación como C.Aunque C parece subir mucho más.
(La gente de Python se apresura a señalar que siempre se pueden convertir funciones recursivas en iterativas y que siempre son más rápidas.Eso es 100% cierto.Aunque en realidad no se trata de eso mi pregunta.)
Intenté el mismo experimento en Perl y alrededor de 10 millones de recursiones consumieron mis 4 gigas de RAM y usé ^C para dejar de intentarlo.Claramente, Perl no usa la pila C, pero usa una cantidad ridícula de memoria cuando se repite, lo que no es muy sorprendente considerando cuánto trabajo tiene que hacer para llamar funciones.
Lo intenté en Pike y me sorprendió completamente obtener 100.000.000 de recursiones en aproximadamente 2 segundos.No tengo idea de cómo hizo eso, pero sospecho que redujo la recursividad a un proceso iterativo: no parece consumir memoria adicional mientras lo hace.[Nota:Pike aplana los casos triviales, pero segmenta los más complicados, o eso me han dicho.]
Utilicé estas funciones que de otro modo serían inútiles:
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
Tengo mucha curiosidad sobre cómo otros lenguajes (por ejemplo, PHP, Ruby, Java, Lua, Ocaml, Haskell) manejan la recursividad y por qué la manejan de esa manera.Además, tenga en cuenta si hay alguna diferencia si la función es "recursiva de cola" (ver comentario).
Solución
" La gente de Python se apresura a señalar que siempre puedes convertir funciones recursivas en iterativas y que siempre son más rápidas "
Esto es cierto, pero si es realmente tan fácil como todo eso, ¿por qué Python no lo hace por mí, para que mi código pueda parecer lo más simple posible? (Digo esto no para golpear a los implementadores de Python, sino porque la respuesta explica el problema).
Las optimizaciones de recursión han estado presentes en lenguajes funcionales desde, como, el siglo XIV o algo así. Las implementaciones de Haskell, CAML, Lisp suelen convertir al menos las funciones recursivas de cola en iteraciones: básicamente se hace esto al detectar que es posible, es decir, que la función se puede reorganizar de modo que no se utilicen variables locales distintas del valor de retorno después de la llamada recursiva . Un truco para hacerlo posible si se realiza algún trabajo en el valor de retorno recursivo antes del retorno, es introducir un & Quot; acumulador & Quot; parámetro. En términos simples, esto significa que el trabajo se puede hacer efectivamente en el camino & Quot; down & Quot; en lugar de en el camino " up " ;: busque 'cómo hacer que una función sea recursiva en la cola' para obtener detalles.
Los detalles reales de convertir una función recursiva de cola en un bucle es básicamente manipular su convención de llamada para que pueda " realizar la llamada " simplemente configurando los parámetros y volviendo al inicio de la función, sin molestarse en guardar todas esas cosas en el alcance que sabe que nunca usará. En términos de ensamblador, no tiene que conservar los registros de guardado de llamadas si el análisis de flujo de datos le indica que no se utilizan más allá de la llamada, y lo mismo ocurre con cualquier cosa en la pila: no tiene que mover el puntero de la pila en una llamada si no le importa " su " bit de pila que la próxima recursión / iteración garabateó.
Contrariamente a cómo parafraseaste a la gente de Python, convertir una función recursiva general en una iteración no es trivial: por ejemplo, si es recursivo múltiple, entonces, en un enfoque simple, todavía necesitarías una pila.
La memorización es una técnica útil, sin embargo, para funciones recursivas arbitrarias, que le gustaría buscar si está interesado en los posibles enfoques. Lo que significa es que cada vez que se evalúa una función, se pega el resultado en un caché. Para usar esto para optimizar la recursividad, básicamente, si su función recursiva cuenta & Quot; down & Quot ;, y la memoriza, entonces puede evaluarla iterativamente agregando un bucle que cuenta & Quot; up < !> quot; calculando cada valor de la función a su vez hasta llegar al objetivo. Esto utiliza muy poco espacio de pila siempre que la memoria caché de memo sea lo suficientemente grande como para contener todos los valores que necesitará: por ejemplo, si f (n) depende de f (n-1), f (n-2) y f (n -3) solo necesitas espacio para 3 valores en el caché: a medida que subes puedes patear la escalera. Si f (n) depende de f (n-1) yf (n / 2), necesita mucho espacio en el caché, pero aún menos de lo que usaría para apilar en una recursión no optimizada.
Otros consejos
Esta es más una pregunta de implementación que una pregunta de idioma. No hay nada que impida que un implementador de compilador C (stoopid) también limite su pila de llamadas a 1000. Hay muchos procesadores pequeños que no tendrían espacio de pila para esa cantidad.
(La gente de Python se apresura a señalar que siempre puedes convertir funciones recursivas en iterativas y que siempre son más rápidas. Eso es 100% cierto. No es realmente de lo que se trata mi pregunta).
Quizás digan eso, pero esto no es del todo correcto. La recursión siempre se puede convertir en iteración, pero a veces también requiere el uso manual de una pila . En esas circunstancias, podría ver que la versión recursiva es más rápida (suponiendo que sea lo suficientemente inteligente como para hacer optimizaciones simples, como extraer declaraciones innecesarias fuera de la rutina recursiva). Después de todo, la pila empuja las llamadas a procedimientos circundantes son un problema bien limitado que su compilador debe saber cómo optimizar muy bien. Las operaciones de apilamiento manual, por otro lado, no tendrán un código de optimización especializado en su compilador, y es probable que tengan todo tipo de comprobaciones de estado de la interfaz de usuario que requerirán ciclos adicionales.
Puede darse el caso de que la solución iterativa / stack sea siempre más rápida en Python . Si es así, eso es una falla de Python, no de recurrencia.
PHP tiene un límite predeterminado de 100 antes de morir:
Fatal error: Maximum function nesting level of '100' reached, aborting!
Editar: puede cambiar el límite con ini_set('xdebug.max_nesting_level', 100000);, pero si supera las 1150 iteraciones se bloquea PHP:
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C # /. NET utilizará la recursividad de cola en un conjunto particular de circunstancias. (El compilador de C # no emite un código de operación de cola, pero el JIT implementará la recursividad de cola en algunos casos .
Shri Borde también tiene una publicación sobre este tema . Por supuesto, el CLR está cambiando continuamente, y con .NET 3.5 y 3.5SP1 puede haber cambiado nuevamente con respecto a las llamadas de cola.
Utilizando lo siguiente en la consola interactiva de F #, se ejecutó en menos de un segundo:
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
Luego intenté una traducción directa, es decir,
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
Mismo resultado pero diferente compilación.
Así es como se ve f cuando se traduce a C #:
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g , sin embargo, se traduce a esto:
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
Es interesante que el compilador de F # represente de manera diferente dos funciones que son básicamente las mismas. También muestra que el compilador de F # tiene una optimización recursiva de cola. Por lo tanto, esto debería repetirse hasta que alcance el límite para los enteros de 32 bits.
De acuerdo con este hilo, alrededor de 5,000,000 con java, 1Gb de RAM. (y eso, con la versión 'cliente' del punto de acceso)
Eso fue con una stack (-Xss) de 300Mo.
Con una -server opción , que podría incrementarse.
También se puede intentar optimizar el compilador ( con JET por ejemplo) para reducir el apilar sobre cada capa.
En algunos casos no patológicos (como el suyo), (más reciente) Lua usará recursividad de llamadas de cola , es decir. saltará sin empujar los datos en la pila. Por lo tanto, la cantidad de bucles de recursión puede ser casi ilimitada.
Probado con:
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
También con:
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
e incluso probé la recursión cruzada (f llamando a g yg llamando a f ...).
En Windows, Lua 5.1 usa alrededor de 1.1MB (constante) para ejecutar esto, termina en unos segundos.
Ejecutando Ruby 1.9.2dev (2010-07-11 revisión 28618) [x86_64-darwin10.0.0] en una macbook blanca más antigua:
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
genera 9353 para mí, lo que significa que Ruby falla con menos de 10,000 llamadas en la pila.
Con recursividad cruzada, como por ejemplo:
def f
@i += 1
g
end
def g
f
end
se caga en la mitad del tiempo, en 4677 (~= 9353/2).
Puedo realizar algunas iteraciones más envolviendo la llamada recursiva en un proceso:
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
que llega hasta 4850 antes de generar un error.
Visual Dataflex apilará el desbordamiento.
Soy un gran admirador de la programación funcional, y dado que la mayoría de esos idiomas implementan la optimización de llamadas de cola, puede recurrir tanto como quiera :-P
Sin embargo, prácticamente, tengo que usar mucho Java y Python también. No tengo idea de qué límite tiene Java, pero para Python en realidad había planeado (pero aún no lo he hecho) implementar un decorador que pudiera optimizar la función decorada. Estaba planeando esto no para optimizar la recursividad, sino principalmente como un ejercicio para parchear dinámicamente el código de bytes de Python y aprender más sobre las partes internas de Python. Aquí hay algunos enlaces interesantes: http://lambda-the-ultimate.org/node/1331 y http://www.rowehl.com/blog/?p=626
Hay una manera de mejorar el código Perl, para que use una pila de tamaño constante. Para ello, utilice una forma especial de goto.
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
Cuando se llama por primera vez, asignará espacio en la pila. Luego cambiará sus argumentos y reiniciará la subrutina, sin agregar nada más a la pila. Por lo tanto, pretenderá que nunca se llamó a sí mismo, transformándolo en un proceso iterativo.
También puede usar el Sub :: Call :: Recur módulo. Lo que hace que el código sea más fácil de entender y más corto.
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure proporciona una forma especial para la recursión de cola " recur " esto solo se puede usar en lugares de cola del ast. De lo contrario, se comporta como Java y probablemente arroje una StackverflowException.
