有没有办法通过记住子节点来加速递归？

Question

例如,查看计算第n个Fibonacci数的代码:

fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

此代码的问题是它将为任何大于15的数字(在大多数计算机中)生成堆栈溢出错误.

假设我们正在计算fib(10).在这个过程中,说fib(5)计算很多次.有没有办法将其存储在内存中以便快速检索,从而提高递归的速度？

我正在寻找一种可用于几乎所有问题的通用技术.

Answer 1

是的,您的见解是正确的.这称为动态编程.它通常是一种常见的内存运行时权衡.

在fibo的情况下,您甚至不需要缓存所有内容:

[编辑]问题的作者似乎正在寻找一种缓存的通用方法,而不是一种计算斐波那契的方法.搜索维基百科或查看其他海报的代码以获得此答案.那些答案在时间和记忆上是线性的.

**这是一个线性时间算法O(n),内存常数**

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

这在线性时间内执行.但是日志实际上是可能的!Roo的程序也是线性的,但速度慢,并且使用内存.

这是日志算法O(log(n))

现在对于对数时间算法(方式方式更快),这里有一个方法:如果你知道u(n),u(n-1),计算u(n + 1),u(n)可以通过应用矩阵:

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

所以你有:

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

计算矩阵的指数具有对数复杂度.只需递归地实现这个想法:

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

你也可以对它进行对角化(不是很难),你会在它的特征值中找到金数和它的共轭,结果将给你一个u(n)的精确数学公式.它包含那些特征值的幂,因此复杂性仍然是对数的.

Fibo经常被用作说明动态编程的一个例子,但正如你所看到的,它并不是真正相关的.

@John:我认为它与哈希没有任何关系.

@John2:你觉得地图有点普遍吗？对于Fibonacci情况,所有键都是连续的,因此矢量是合适的,再次有更快的方法来计算fibo序列,请参阅那里的代码示例.

Answer 2

这被称为memoization,这篇文章中有一篇关于Memo Matthew Podwysocki发布的非常好的文章.它使用斐波纳契来举例说明它.并在C#中显示代码.在这里阅读.

Answer 3

如果你正在使用C#,并且可以使用PostSharp,这里有一个代码的简单memoization方面:

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

以下是使用它的Fibonacci实现示例:

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}