optimization - paradigmas - programacion imperativa
Recursión eficiente en programación funcional vs. recursión ineficiente en diferentes paradigmas (8)
Hasta donde yo sé, la recursión es muy elegante pero poco eficiente en OOP y programación de procedimientos (vea el maravilloso "perl de alto orden", Mark Jason Dominus). Tuve algunas informaciones de que en la programación funcional la recursión es rápida , manteniendo su elegancia y simplicidad. ¿Podría alguien confirmar y posiblemente amplificar esto? Estoy pensando en términos de XSLT y Haskell (en la lista de mi próximo idioma para aprender)
Gracias
Daniel
Recursión eficiente en XSLT
Hay dos formas principales de lograr una recursión eficiente en XSLT:
- Optimización de recursión de cola
- Dividir y vencer (DVC)
Hay muchas respuestas que cubren la recursividad de cola, así que aquí hay solo un ejemplo simple :
<xsl:function name="my:sum">
<xsl:param name="pAccum" as="xs:double*"/>
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then $pAccum
else
my:sum($pAccum + $pNums[1], $pNums[position() >1])
"
/>
</xsl:function>
Uno puede verificar que my: sum (0, 1 a 100) se evalúa a: 5050.
Aquí es cómo uno implementaría la función sum() en una forma DVC :
<xsl:function name="my:sum2">
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then 0
else
if(count($pNums) eq 1)
then $pNums[1]
else
for $half in count($pNums) idiv 2
return
my:sum2($pNums[not(position() gt $half)])
+
my:sum2($pNums[position() gt $half])
"
/>
</xsl:function>
La idea principal detrás de DVC es subdividir la secuencia de entrada en dos (generalmente) o más partes y procesarlas independientemente una de la otra, luego combinar los resultados para producir el resultado para la secuencia de entrada total.
Tenga en cuenta que para una secuencia de N elementos, la profundidad máxima de la pila de llamadas en cualquier punto od time no excedería log2(N) , que es más que suficiente para la mayoría de los propósitos prácticos. Por ejemplo, la profundidad máxima de la pila de llamadas al procesar una secuencia de 1000000 (1M) elementos, sería solo 19.
Si bien hay algunos procesadores XSLT que no son lo suficientemente inteligentes como para reconocer y optimizar la repetición de cola, una plantilla recursiva DVC funciona en cualquier procesador XSLT.
Lo que hace que la recursión sea rápida en los lenguajes funcionales es que los compiladores pueden transformar internamente la recursión en iteración utilizando la eliminación de la recursión de cola (o, más en general, la eliminación de la cola de llamada). Básicamente, si una llamada recursiva es la última operación antes de que regrese una función, y el valor de retorno de la función es el de la llamada recursiva, entonces, en lugar de crear un nuevo marco de pila, el programa reutilizará el marco actual. Las variables de argumento se establecen en nuevos valores y la PC se configura al comienzo de la función.
Aprovechando la eliminación de la recursividad de la cola requiere cierta conciencia por parte del programador. Debes asegurarte de que tus llamadas recursivas sean en realidad las llamadas finales. Por ejemplo, aquí está el código en OCaml para calcular un factorial:
let rec factorial n =
if n = 0 then
1
else
n * factorial (n - 1)
La eliminación de llamada de cola no funcionaría directamente aquí ya que una multiplicación tiene que realizarse después de la llamada recursiva. Sin embargo, si la función se reescribió así:
let factorial n =
let rec fac_helper n p =
if n = 0 then
p
else
fac_helper (n - 1) (p * n)
in
fac_helper n 1
Ahora se puede usar la eliminación de llamadas de cola. Esto se transformaría en algo como esto (en pseudocódigo):
factorial p n =
p = 1
while n > 0
n = n - 1
p = p * n
return p
Este estilo puede parecer contradictorio, pero tiene tanto sentido como la versión iterativa. Cada paso del cálculo se realiza en una llamada a una función recursiva. Las variables de inducción como p y n anteriores, que se utilizan en todo el cálculo, se declaran como argumentos.
Cabe señalar que la mayoría de los compiladores, tanto para lenguajes imperativos como funcionales, aprovechan esta optimización. De hecho, la versión de la optimización de LLVM incluso permite operaciones asociativas entre la llamada recursiva y la devolución, por lo que podría escribir la primera versión de factorial y seguir utilizando la optimización. Sin embargo, la eliminación de llamada final no es compatible con la JVM, por lo que los lenguajes funcionales en la JVM como Scala solo tienen soporte limitado.
Si el compilador en uso admite la optimización de la cola de llamadas y usted estructura su código para aprovecharlo, la recursión no es ineficiente.
Debido a la prevalencia de recursión en la programación funcional, es más probable que los compiladores de lenguajes funcionales implementen la optimización de las llamadas finales que las de procedimiento.
Si el lenguaje no está optimizado por el compilador, es muy probable que la recursión sea más lenta que la iteración, porque además de descender por un carril determinado, que es más o menos equivalente a la iteración, debe retroceder sus pasos al principio al finalizar el proceso. trabajo.
De lo contrario, es prácticamente equivalente, excepto que puede ser mucho más elegante, ya que permite que el compilador y el sistema manejen el ciclo detrás de las escenas. Y, por supuesto, hay tareas (como el procesamiento de estructuras en forma de árbol) donde la recursión es la única forma (o al menos la única que no está intrincadamente complicada).
La recurrencia de la cola es una iteración en cualquier implementación decente del lenguaje funcional. Aquí hay un ejemplo usando GHC Haskell. Un programa simple para agregar una secuencia de números. Comienza como la composición de varias funciones recursivas:
import qualified Data.Vector as U
main = print (U.sum (U.enumFromTo 1 (10000000 :: Int)))
Lo que el compilador optimiza en una única función recursiva de cola (en una transformación de fuente a fuente):
loop x y = case y <= y 10000000 of
False -> x
True -> loop (x + y) (y + 1)
Esta función recursiva luego se compila en un ciclo directo:
loop:
.Lc216:
cmpq $10000000,%rsi
jle .Lc219
movq %r14,%rbx
movq (%rbp),%rax
jmp *(%rax)
.Lc219:
addq %rsi,%r14
incq %rsi
jmp loop
O con el backend GHC LLVM, se aplican optimizaciones adicionales a la representación imperativa del programa:
loop:
leaq 1(%rsi), %rax
addq %rsi, %r14
cmpq $10000001, %rax
jge .LBB1_5
addq $2, %rsi
addq %rax, %r14
test: # %tailrecurse
cmpq $10000001, %rsi
jl loop
Observe cómo se etiqueta la etiqueta recursiva de la cola.
Así que teníamos una serie de funciones recursivas, que se compilaron a una única función recursiva de cola, que se compiló en un solo bucle imperativo sin pila. Y 8 instrucciones al final.
Y es por eso que tanto la composición de la función como la recursividad son extremadamente eficientes en los lenguajes de función optimizadores.
Lo único que tengo que agregar a la respuesta de dons es que muchos idiomas son rehenes de las convenciones de llamadas heredadas . En ninguna parte esto es más cierto que los lenguajes que se ajustan a la convención de llamadas C en x86: cada parámetro va en la pila. Los lenguajes funcionales pasan al menos algunos parámetros en los registros, y así en las plataformas de 32 bits, incluso las llamadas sin cola (que no se pueden optimizar) son aún más eficientes que, por ejemplo, en C.
¡Gracias a Dios que el x86-64 tiene una convención decente de llamadas en C!
No asuma que la recursión frente a la iteración es donde debe ubicar su preocupación.
Normalmente, eso se vuelve significativo después de que haya eliminado por primera vez una serie de problemas de rendimiento más grandes .
OOP / Lenguajes de procedimiento tienden a colocar datos en la pila cada vez que se realiza una llamada recursiva, por lo que la recursión no es tan eficiente como la iteración en estos idiomas.
Por el contrario, los compiladores / intérpretes para lenguajes funcionales están generalmente diseñados para optimizar la repetición de cola para que sea tan eficiente como la iteración :
La recursión puede requerir el mantenimiento de una pila, pero la recursión de cola puede ser reconocida y optimizada por un compilador en el mismo código utilizado para implementar la iteración en lenguajes imperativos. El estándar de lenguaje de programación Scheme requiere implementaciones para reconocer y optimizar la recursividad de cola. La optimización de recurrencia de cola se puede implementar transformando el programa en un estilo de paso de continuación durante la compilación, entre otros enfoques.
lo que es-tail-call-optimization y which-languages-support-tail-recursion-optimization tienen información más detallada.