scala - porcentajes - funcion si con dos condiciones
¿Es la función anidada eficiente? (5)
En lenguajes de programación como Scala o Lua, podemos definir funciones anidadas como
function factorial(n)
function _fac(n, acc)
if n == 0 then
return acc
else
return _fac(n-1, acc * n)
end
end
return _fac(n, 1)
end
¿Este enfoque causa alguna ineficiencia porque la instancia de la función anidada se define o crea cada vez que invocamos la función externa?
¿Este enfoque causa alguna ineficiencia porque la instancia de la función anidada se define o crea cada vez que invocamos la función externa?
La eficiencia es un tema amplio y amplio. Estoy asumiendo que por "ineficiente" quiere decir "¿llamar el método recursivamente cada vez tiene una sobrecarga"?
Solo puedo hablar en nombre de Scala, específicamente el sabor que apunta a la JVM, ya que otros sabores pueden actuar de manera diferente.
Podemos dividir esta pregunta en dos, dependiendo de lo que realmente quisiste decir.
Los métodos anidados (de alcance local) en Scala son una característica de alcance léxico, lo que significa que le brindan acceso a los valores de los métodos externos, pero una vez que emitimos el código de bytes, se definen a nivel de clase, simplemente como un método Java simple.
Para estar completo, sepa que Scala también tiene valores de función , que son ciudadanos de primera clase, lo que significa que puede pasarlos a otras funciones, por lo que estos incurrirían en una sobrecarga de asignación , ya que se implementan utilizando clases.
El factorial se puede escribir de una manera recursiva de cola, como lo escribió en su ejemplo. El compilador de Scala es lo suficientemente inteligente como para notar que su método es recursivo y lo convierte en un bucle iterativo, evitando la invocación del método para cada iteración. También puede, si es posible, intentar alinear el método factorial , evitando la sobrecarga de una asignación de marco de pila adicional.
Por ejemplo, considere la siguiente implementación factorial en Scala:
def factorial(num: Int): Int = {
@tailrec
def fact(num: Int, acc: Int): Int = num match {
case 0 => acc
case n => fact(n - 1, acc * n)
}
fact(num, 1)
}
A primera vista, tenemos un método recursivo. Veamos cómo se ve el bytecode JVM:
private final int fact$1(int, int);
Code:
0: iload_1
1: istore 4
3: iload 4
5: tableswitch { // 0 to 0
0: 24
default: 28
}
24: iload_2
25: goto 41
28: iload 4
30: iconst_1
31: isub
32: iload_2
33: iload 4
35: imul
36: istore_2
37: istore_1
38: goto 0
41: ireturn
Lo que vemos aquí es que la recursión se convirtió en un bucle iterativo (un tableswitch + una instrucción de salto).
Con respecto a la creación de la instancia del método, si nuestro método no era recursivo, el tiempo de ejecución de JVM tendría que interpretarlo para cada invocación, hasta que el compilador C2 lo encuentre suficiente para que JIT lo compile y reutilice el código de máquina para cada método llamar despues
En general, diría que esto no debería preocuparle a menos que haya notado que el método está en la ejecución de su ruta de acceso y el perfil del código lo llevó a hacer esta pregunta.
Para concluir, la eficiencia es un tema muy delicado y específico para cada caso de uso. Creo que no tenemos suficiente información para decirle, del ejemplo simplificado que ha proporcionado, si esta es la mejor opción para elegir su caso de uso. Repito, si esto no es algo que apareció en su perfilador, no se preocupe por esto.
Comparémoslo en Lua con / sin funciones anidadas.
Variante 1 (el objeto de función interna se crea en cada llamada)
local function factorial1(n)
local function _fac1(n, acc)
if n == 0 then
return acc
else
return _fac1(n-1, acc * n)
end
end
return _fac1(n, 1)
end
Variante 2 (las funciones no están anidadas)
local function _fac2(n, acc)
if n == 0 then
return acc
else
return _fac2(n-1, acc * n)
end
end
local function factorial2(n)
return _fac2(n, 1)
end
Código de referencia (calcule 12! 10 millones de veces y visualice el tiempo de CPU utilizado en segundos):
local N = 1e7
local start_time = os.clock()
for j = 1, N do
factorial1(12)
end
print("CPU time of factorial1 = ", os.clock() - start_time)
local start_time = os.clock()
for j = 1, N do
factorial2(12)
end
print("CPU time of factorial2 = ", os.clock() - start_time)
Salida para Lua 5.3 (intérprete)
CPU time of factorial1 = 8.237
CPU time of factorial2 = 6.074
Salida para LuaJIT (compilador JIT)
CPU time of factorial1 = 1.493
CPU time of factorial2 = 0.141
La respuesta depende del idioma del curso.
Lo que sucede en Scala en particular es que las funciones internas se compilan como si estuvieran fuera del alcance de la función dentro de la cual se definen.
De esta manera, el lenguaje solo le permite invocarlos desde el ámbito léxico donde están definidos, pero en realidad no instancia la función varias veces.
Podemos probar esto fácilmente compilando dos variantes de la
El primero es un puerto bastante fiel de su código Lua:
class Function1 {
def factorial(n: Int): Int = {
def _fac(n: Int, acc: Int): Int =
if (n == 0)
acc
else
_fac(n-1, acc * n)
_fac(n, 1)
}
}
El segundo es más o menos el mismo, pero la función recursiva de la cola se define fuera del alcance del factorial :
class Function2 {
def factorial(n: Int): Int = _fac(n, 1)
private final def _fac(n: Int, acc: Int): Int =
if (n == 0)
acc
else
_fac(n-1, acc * n)
}
Ahora podemos compilar estas dos clases con scalac y luego usar javap para ver el resultado del compilador:
javap -p Function*.scala
lo que dará la siguiente salida
Compiled from "Function1.scala"
public class Function1 {
public int factorial(int);
private final int _fac$1(int, int);
public Function1();
}
Compiled from "Function2.scala"
public class Function2 {
public int factorial(int);
private final int _fac(int, int);
public Function2();
}
Agregué las palabras clave private final para minimizar la diferencia entre los dos, pero lo más importante es notar que en ambos casos las definiciones aparecen a nivel de clase, con funciones internas definidas automáticamente como private y final y con una pequeña decoración para garantizar que no haya clase de nombre (por ejemplo, si define una función interna de loop dentro de dos funciones diferentes).
No estoy seguro de Lua u otros idiomas, pero puedo esperar que al menos la mayoría de los idiomas compilados adopten un enfoque similar.
No sé sobre lua, pero en Scala son muy comunes y se usan en funciones recursivas para garantizar una optimización segura de la cola:
def factorial(i: Int): Int = {
@tailrec
def fact(i: Int, accumulator: Int): Int = {
if (i <= 1)
accumulator
else
fact(i - 1, i * accumulator)
}
fact(i, 1)
}
Más información sobre cola segura y recursión here
Sí (o solía hacerlo), como lo demuestra el esfuerzo de Lua por reutilizar los valores de la función cuando la ejecución pasa a través de una definición de función varias veces.
La igualdad entre los valores de función ha cambiado. Ahora, una definición de función puede no crear un nuevo valor; puede reutilizar algún valor anterior si no hay una diferencia observable en la nueva función.
Ya que ha codificado (asumiendo Lua) una función asignada a un global o local declarado en un alcance superior, puede codificar el cortocircuito usted mismo (suponiendo que ningún otro código lo establece en otro que no sea nil o false ):
function factorial(n)
_fac = _fac or function (n, acc)
…
end
…
end