3

我正在尝试递归：

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)}"

如果我像这样使用它，我会得到这个：

在 691 毫秒内完成

如果我取消注释第 2 行和第 3-4 行注释以删除trampoline()并运行它，我得到的数字要低得多：

在 335 毫秒内完成

因此，使用蹦床时，递归的工作速度要慢 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" )

它执行得更快一点：

在 178 毫秒内完成

更新

将闭包重写为带有注解的方法：

@groovy.transform.TailRecursive
def fac( int curr, res = 1G ) { 1 >= curr ? res : fac( curr - 1, res * curr ) }
// the rest

给

在 164 毫秒内完成

并且是超级科尔。尽管如此，我仍然想知道trampoline():)

4

1 回答 1

6

如文档中所述，Closure.trampoline()防止溢出调用堆栈。

递归算法通常受到物理限制的限制：最大堆栈高度。例如，如果你调用一个递归调用自身太深的方法，你最终会收到一个StackOverflowException.

在这些情况下有帮助的一种方法是使用Closure它的蹦床功能。

闭包被包裹在一个TrampolineClosure. 调用后，蹦床Closure将调用原件Closure等待其结果。如果调用的结果是 a 的另一个实例TrampolineClosure，可能是作为对该trampoline()方法的调用的结果而创建的，则将再次调用闭包。这种对返回的 trampolined Closures 实例的重复调用将继续，直到Closure返回一个除 trampolined 之外的值。该值将成为蹦床的最终结果。这样，调用是连续进行的，而不是填充堆栈。

来源： http: //groovy-lang.org/closures.html#_trampoline

然而，使用蹦床是有代价的。让我们看一下 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在所有执行中都使用了一个 of，而在使用 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/

于 2019-06-13T16:52:44.703 回答