嵌套功能是否有效？ [英] Is nested function efficient?
问题描述
function factorial（n）
函数_fac（n，acc）
如果n == 0那么
返回acc
else
return _fac（n-1，acc * n）
end
end
return _fac（n，1）
end
这种方法是否会导致任何效率低下，因为每次我们调用外部函数时都会定义或创建嵌套函数实例？解析方案
blockquote>
这种方法是否会导致效率低下，因为每当我们调用外部
函数时，嵌套函数
实例被定义或创建？
效率是一个大而广泛的话题。我假设效率低下的意思是每次都有开销调用递归方法？
我只能代表Scala发言，特别是风格定位JVM，因为其他口味可能会有所不同。
我们可以将这个问题分成两部分，具体取决于您的意思。
Scala中的嵌套（局部作用域）方法是一个词法作用域特征，意味着它们可以提供对外部方法值的可访问性，但是一旦我们发出字节码，就会定义它们在类级别，就像一个普通的java方法一样。
为了保持完整性，要知道Scala也有函数值，它们是first class公民，这意味着你可以将它们传递给其他函数，然后这些会产生分配开销，因为它们是使用类实现的。
因子可以用尾部递归的方式编写，就像你在例子中写的那样。 Scala编译器足够聪明，它会注意到你的方法是递归的，并将它变成一个迭代循环，避免了每次迭代的方法调用。如果可能的话，它也可以尝试内联 factorial 方法，避免额外的堆栈帧分配的开销。
例如，在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）
}
表面上，我们有一个递归方法。让我们来看看JVM字节码是什么样的：
private final int fact $ 1（int，int）;
代码：
0：iload_1
1：istore 4
3：iload 4
5：tableswitch {// 0至0
0：24
默认值：28
}
24：iload_2
25：转到41
28：iload 4
30：iconst_1
31：isub
32：iload_2
33：iload 4
35：imul
36：istore_2
37：istore_1
38：转到0
41：ireturn
我们在这里看到递归变成了一个迭代循环（a tableswitch +一个跳转指令）。
关于方法实例的创建，如果我们的方法不是尾递归的，JVM运行时需要为每次调用解释它，直到 C2 compiler a>发现它足够，这样它将JIT编译它并在之后重新使用每个方法调用的机器代码。
通常，我会说这不应该担心你除非你已经注意到这个方法正在执行你的热门路径，并且分析代码导致你提出这个问题。
总之，效率是一个非常微妙的，用例特定的主题。我想我们没有足够的信息来告诉您，从您提供的简化示例中，如果这是您的用例选择的最佳选择。我再说一遍，如果这不是你的分析器上显示的东西，不要担心这一点。
In programming languages like Scala or Lua, we can define nested functions such as
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
Does this approach cause any inefficiency because the nested function instance is defined, or created, everytime we invoke the outer function?
Does this approach cause any inefficiency because the nested function instance is defined, or created, everytime we invoke the outer function?
Efficiency is a large and broad topic. I am assuming that by "inefficient" you mean "does calling the method recursively each time have an overhead"?
I can only speak on Scala's behalf, specifically the flavor targeting the JVM, as other flavors may act differently.
We can divide this question into two, depending on what you really meant.
Nested (local scope) methods in Scala are a lexical scope feature, meaning they give you the accessibility to outer method values, but once we emit the bytecode, they are defined at the class level, just as a plain java method.
For completeness, do know that Scala also has function values, which are first class citizens, meaning you can pass them around to other functions, then these would incur an allocation overhead, since they are implemented using classes.
Factorial can be written in a tail recursive manner, as you wrote it in your example. The Scala compiler is intelligent enough such that it will notice your method is tail recursive and turn it into an iterative loop, avoiding the method invocation for each iteration. It may also, if found possible, attempt to inline the factorial method, avoiding the overhead of an additional stack frame allocation.
For example, consider the following factorial implementation in 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)
}
On the face of it, we have a recursive method. Let's see what the JVM bytecode looks like:
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
What we see here is that the recursion turned into an iterative loop (a tableswitch + a jump instruction).
Regarding the method instance creation, if our method was not tail recursive, the JVM runtime would need to interpret it for each invocation, until the C2 compiler finds it sufficient such that it will JIT compile it and re-use the machine code for each method call afterwards.
Generally, I would say this shouldn't worry you unless you've noticed the method is on the execution of your hot path and profiling the code led you to ask this question.
To conclude, efficiency is a very delicate, use case specific topic. I think we don't have enough information to tell you, from the simplified example you've provided, if this is the best option to choose for your use case. I say again, if this isn't something that showed up on your profiler, don't worry about this.
这篇关于嵌套功能是否有效？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
