我正在尝试递归:
def fac
//fac = { int curr, res = 1G -> 1 >= curr ? res : fac( curr - 1, res * curr ) }
fac = { int curr, res = 1G -> 1 >= curr ? res : fac.trampoline( curr - 1, res * curr ) }
fac = fac.trampoline()
def rnd = new Random()
long s = System.currentTimeMillis()
100000.times{ fac rnd.nextInt( 40 ) }
println "done in ${System.currentTimeMillis() - s} ms / ${fac(40)}"
如果我像这样使用它,我会得到这个:
done in 691 ms
如果我取消注释第 #2 行和注释行 #3-4 以删除 trampoline()
并运行它,我得到的数字会显着降低:
done in 335 ms
因此,使用蹦床,递归速度慢了 2 倍。
我错过了什么?
附注
如果我在 Scala 2.12 中运行相同的示例:
def fac( curr:Int, acc:BigInt = 1 ):BigInt = if( 1 >= curr ) acc else fac( curr - 1, curr * acc )
val s = System.currentTimeMillis
for( ix <- 0 until 100000 ) fac( scala.util.Random.nextInt(40).toInt )
println( s"done in ${System.currentTimeMillis - s} ms" )
它执行得更快一点:
done in 178 ms
更新
使用注释将闭包重写为方法:
@groovy.transform.TailRecursive
def fac( int curr, res = 1G ) { 1 >= curr ? res : fac( curr - 1, res * curr ) }
// the rest
给出
done in 164 ms
而且 super 酷。尽管如此,我仍然想了解 trampoline()
:)
最佳答案
如文档中所述,Closure.trampoline()
可防止调用堆栈溢出。
Recursive algorithms are often restricted by a physical limit: the maximum stack height. For example, if you call a method that recursively calls itself too deep, you will eventually receive a
StackOverflowException
.An approach that helps in those situations is by using
Closure
and its trampoline capability.Closures are wrapped in a
TrampolineClosure
. Upon calling, a trampolinedClosure
will call the originalClosure
waiting for its result. If the outcome of the call is another instance of aTrampolineClosure
, created perhaps as a result to a call to thetrampoline()
method, the Closure will again be invoked. This repetitive invocation of returned trampolined Closures instances will continue until a value other than a trampolinedClosure
is returned. That value will become the final result of the trampoline. That way, calls are made serially, rather than filling the stack.
但是,使用蹦床是有代价的。让我们看一下 JVisualVM 示例。
非蹦床用例
在没有 trampoline()
的情况下运行示例,我们在大约 441 毫秒内得到结果
done in 441 ms / 815915283247897734345611269596115894272000000000
此执行分配约 2,927,550 个对象并消耗约 100 MB 内存。
CPU 有一些事情要做,除了在 main()
和 run()
方法上花费时间之外,它还花费一些周期来强制参数。
trampoline()
用例
蹦床的引入确实改变了很多。首先,与之前的尝试相比,它使执行时间几乎慢了两倍。
done in 856 ms / 815915283247897734345611269596115894272000000000
其次,它分配~5,931,470(!!!)个对象并消耗~221 MB 内存。主要区别在于,在前一种情况下,所有执行中都使用了单个 $_main_closure1
,而在使用 Trampoline 的情况下 - 每次调用 trampoline()
方法都会创建:
- 一个新的
$_main_closure1
对象 - 它被
CurriedClosure<T>
包裹 - 然后用
TrampolineClosure<T>
包装
仅此分配就超过 1,200,000 个对象。
如果涉及到CPU,它还有更多的事情要做。只要看一下数字即可:
- 对
TrampolineClosure<T>.<init>()
的所有调用都会消耗199 毫秒 - 使用 Trampoline 会引入对
PojoeMetaMethodSite$PojoCachedMethodSietNoUnwrap.invoke()
的调用,总共会额外消耗 201 毫秒 - 对
CachedClass$3.initValue()
的所有调用总计额外消耗 98.8 毫秒 - 对
ClosureMetaClass$NormalMethodChooser.chooseMethod()
的所有调用总计额外消耗 100 毫秒
这正是为什么在您的案例中引入蹦床会使代码执行速度慢得多的原因。
那么为什么 @TailRecursive
做得更好呢?
简而言之 - @TailRecursive
注释用旧的 while 循环替换了所有闭包和递归调用。 @TailRecursive
的阶乘函数在字节码级别看起来像这样:
//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//
package factorial;
import groovy.lang.GroovyObject;
import groovy.lang.MetaClass;
import java.math.BigInteger;
import org.codehaus.groovy.runtime.ScriptBytecodeAdapter;
import org.codehaus.groovy.runtime.dgmimpl.NumberNumberMultiply;
import org.codehaus.groovy.transform.tailrec.GotoRecurHereException;
public class Groovy implements GroovyObject {
public Groovy() {
MetaClass var1 = this.$getStaticMetaClass();
this.metaClass = var1;
}
public static BigInteger factorial(int number, BigInteger acc) {
BigInteger _acc_ = acc;
int _number_ = number;
try {
while(true) {
try {
while(_number_ != 1) {
int __number__ = _number_;
int var7 = _number_ - 1;
_number_ = var7;
Number var8 = NumberNumberMultiply.multiply(__number__, _acc_);
_acc_ = (BigInteger)ScriptBytecodeAdapter.castToType(var8, BigInteger.class);
}
BigInteger var4 = _acc_;
return var4;
} catch (GotoRecurHereException var13) {
;
}
}
} finally {
;
}
}
public static BigInteger factorial(int number) {
return factorial(number, (BigInteger)ScriptBytecodeAdapter.castToType(1, BigInteger.class));
}
}
我不久前在我的博客上记录了这个用例。如果您想了解更多信息,可以阅读博客文章:
https://e.printstacktrace.blog/tail-recursive-methods-in-groovy/
关于recursion - Groovy 的 Tampoline() 使递归执行速度变慢 - 为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56578937/