groovy fibonacchi弹床和memoize

Question

我正在尝试评估10000000的fibonacchi序列。

使用基本的trampoline，它看起来像这样

def rFibonacchi
rFibonacchi = { 
    BigInteger n, prev = 0, next = 1 ->
        (n < 2) ? prev : rFibonacchi.trampoline(n - 1, prev, next + prev)
}.trampoline()

但是使用trampoline & memoize组合，我经常得到OutOfMemoryError。

def tFibonacchi, mFibonacchi

mFibonacchi = { BigInteger n, prev, next ->
    n < 2 ? prev : tFibonacchi.trampoline(n - 1, next, prev + next)
}.memoize()

tFibonacchi = { BigInteger n, prev = 0, next = 1 ->
    mFibonacchi(n, next, prev)
}.trampoline()

tFibonacchi(10000000); // GC overhead limit exceed

是我的算法的问题吗？

Answer 1

您的算法不会从使用memoization中获得任何奖励。引用the groovy docs on memoization:

Memoization允许缓存调用闭包的结果。如果一个函数(闭包)的计算速度很慢，这是很有趣的，但你知道这个函数会经常用相同的参数调用。一个典型的例子是Fibonacci套件。一个简单的实现可能如下所示：

定义fib ={ long n -> n<2?n:fib(n-1)+ fib (n-2) }断言fib(15) == 610 //慢！

这是一个天真的实现，因为'fib‘经常用相同的参数递归调用，导致一个指数算法：

• computing fib(15)需要fib(14)和fib(13)

的结果

• 计算fib(14)需要fib(13)和fib的结果

由于调用是递归的，您已经可以看到我们将一次又一次地计算相同的值，尽管它们可以被缓存。这个简单的实现可以通过使用memoize缓存调用的结果来“修复”：

fib ={ long n -> n<2?n:fib(n-1)+fib(n-2) }.memoize() assert fib(25) == 75025 //快速！

缓存使用参数的实际值工作。

您正在使用一个改进的Fibonacci算法来实现上面的算法。您的方法更具迭代性，并且它不会使用所有相同的参数调用mFibonacchi两次。这会导致groovy缓存每次调用的结果，但实际上从未使用过这个缓存，这会导致内存溢出。记忆实际上是一个问题。

你的算法相当于：

BigInteger fibonacchi(BigInteger n) {
    BigInteger prev = 0, next = 1
    for (; n > 2; n--) {
        BigInteger temp = prev
        prev = next
        next = prev + temp
    }
    return prev
}