关于性能:是否有某种方法可以通过记住子节点来加快递归?

关于性能:是否有某种方法可以通过记住子节点来加快递归?

Is there some way to speed up recursion by remembering child nodes?

例如,
查看计算第n个斐波那契数的代码:

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

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

假设我们正在计算fib(10)。 在此过程中,fib(5)被多次计算。 是否有某种方法可以将其存储在内存中以便快速检索,从而提高递归速度?

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


是的,您的见解是正确的。
这称为动态编程。通常,这是常见内存运行时的折衷方案。

对于fibo,您甚至不需要缓存所有内容:

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

**这里是线性时间算法O(n),在内存中恒定**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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),则可以通过应用矩阵来完成:

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

这样就可以了:

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

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

1
2
3
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为例来说明动态编程,但是正如您所看到的,它并不是真正相关的。

@约翰:
我认为这与哈希无关。

@ John2:
地图有点一般吧?对于斐波那契情况,所有键都是连续的,因此向量是合适的,再次有更快的方法来计算斐波那契序列,请参阅那边的代码示例。


这就是所谓的回忆,这几天有一篇关于回忆的很好的文章Matthew Podwysocki发表了。它以斐波那契为例。并在C#中也显示代码。在这里阅读。


如果您使用的是C#,并且可以使用PostSharp,则以下是代码的简单备注方面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
[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
}

这是一个使用它的示例斐波那契实现:

1
2
3
4
5
6
7
8
[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

C ++中的快速脏记录:

任何type1 foo(type2 bar) { ... }递归方法都可以很容易地用map M记住。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// your original method
int fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

编辑:@Konrad Rudolph
Konrad指出std :: map并不是我们可以在此处使用的最快的数据结构。是的,vector应该比map快(尽管如果函数的递归调用的输入不是这种情况下的连续整数,则可能需要更多的内存),但是使用映射很方便通常。


根据维基百科,Fib(0)应该为0,但这并不重要。

这是带有for循环的简单C#解决方案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

将递归转换为尾递归然后进行循环是很常见的技巧。有关更多详细信息,请参见本讲课(ppt)。


其他人已经很好且准确地回答了您的问题-您正在寻找备忘录。

具有尾部调用优化功能的编程语言(主要是功能语言)可以执行某些递归情况,而不会引起堆栈溢出。尽管有一些技巧,但它并不直接适用于您对斐波那契的定义。

问题的措辞使我想到了一个有趣的主意。通过仅存储堆栈框架的子集并在必要时进行重建,避免了纯递归函数的堆栈溢出。仅在某些情况下才有用。如果您的算法仅在条件上依赖于上下文而不是返回,并且/或者您正在针对内存进行优化而不是提高速度。


@ESRogs:

std::map查找为O(log n),这会使它变慢。最好使用向量。

1
2
3
4
5
6
7
8
9
10
vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}

尝试使用地图,n是键,其对应的斐波那契数是值。

保罗

谢谢(你的)信息。我不知道您在Wikipedia链接中提到:

This technique of saving values that
have already been calculated is called
memoization

是的,我已经看过代码(+1)。 :)


这是故意选择的示例吗? (例如,您要测试的极端情况)

因为它目前是O(1.6 ^ n),所以我只想确保您只是在寻找处理此问题的一般情况(缓存值等)的答案,而不仅仅是不小心编写不良代码:D

查看此特定情况,您可能会遇到以下问题:

1
2
3
4
5
6
7
8
var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

在最坏的情况下会退化为O(n):D

[编辑:*不等于+:D]

[还有另一个编辑:Haskell版本(因为我是受虐狂之类的人)

1
2
fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]


Mathematica有一种特别巧妙的方式来进行记忆,它依赖于散列和函数调用使用相同语法的事实:

1
2
3
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

而已。它从头开始缓存(记忆)fib [0]和fib [1],并根据需要缓存其余部分。模式匹配函数调用的规则是这样的,它总是在使用更通用的定义之前始终使用更具体的定义。


Wes Dyer的博客是C#程序员用于递归,局部查询,计算,记忆化以及其类似功能的另一种绝佳资源,尽管他未曾发布过。他很好地解释了记忆,并在此处提供了可靠的代码示例:
http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx


对于这种事情,缓存通常是个好主意。由于斐波那契数是恒定的,因此您可以在计算出结果后将其缓存。快速的c / pseudocode示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

这会非常慢,因为每次递归都会导致3次查找,但是这应该可以说明总体思路


这是什么语言?它不会在C中溢出任何东西...
另外,您可以尝试在堆上创建查找表,或使用映射


正如其他张贴者所指出的那样,记忆是一种以内存换取速度的标准方法,以下是一些用于实现任何功能记忆的伪代码(前提是该功能没有副作用):

初始功能代码:

1
2
3
 function (parameters)
      body (with recursive calls to calculate result)
      return result

这应该转换为

1
2
3
4
5
6
7
 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]

@lassevk:

这太棒了,这正是我在阅读了Highper Perl中的记忆后脑子里一直在想的。 我认为有两点有用的补充:

  • 一个可选参数,用于指定用于生成高速缓存密钥的静态或成员方法。
  • 更改缓存对象的一种可选方式,以便您可以使用磁盘或数据库支持的缓存。
  • 不知道如何使用Attributes来做这种事情(或者,即使使用这种实现也可以做到),但我计划尝试找出。

    (非主题:我试图将其发布为评论,但我没有意识到评论的允许长度太短,因此这实际上不适合作为"答案")


    顺便说一句,Perl拥有一个备注模块,可为您指定的代码中的任何功能执行此操作。

    1
    2
    3
    4
    5
    6
    # Compute Fibonacci numbers
    sub fib {
          my $n = shift;
          return $n if $n < 2;
          fib($n-1) + fib($n-2);
    }

    为了记住该功能,您要做的就是使用以下命令启动程序

    1
    2
    3
    4
    use Memoize;
    memoize('fib');
    # Rest of the fib function just like the original version.
    # Now fib is automagically much faster ;-)

    如果您正在使用具有一流功能(如Scheme)的语言,则可以添加备注,而无需更改初始算法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    (define (memoize fn)
      (letrec ((get (lambda (query) '(#f)))
               (set (lambda (query value)
                      (let ((old-get get))
                        (set! get (lambda (q)
                                    (if (equal? q query)
                                        (cons #t value)
                                        (old-get q))))))))
        (lambda args
          (let ((val (get args)))
            (if (car val)
                (cdr val)
                (let ((ret (apply fn args)))
                  (set args ret)
                  ret))))))


    (define fib (memoize (lambda (x)
                           (if (< x 2) x
                               (+ (fib (- x 1)) (fib (- x 2)))))))

    第一块提供记忆功能,第二块是使用该功能的斐波那契数列。现在,它具有O(n)运行时(与没有记忆的算法的O(2 ^ n)相对)。

    注意:提供的备忘录功能使用闭包链来查找先前的调用。最坏的情况是O(n)。但是,在这种情况下,所需值始终位于链的顶部,从而确保了O(1)查找。


    The problem with this code is that it will generate stack overflow error for any number greater than 15 (in most computers).

    真?您正在使用什么计算机?在44点花费很长时间,但是堆栈没有溢出。实际上,在堆栈溢出之前,您要获得的值可能大于整数(约40亿个无符号,约20亿个有符号)(Fibbonaci(46))。

    这将适合您想做的事情(运行速度很快)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Program
    {
        public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
        static void Main(string[] args)
        {
            Console.WriteLine(Fibbonacci(46).ToString());
            Console.ReadLine();
        }

        public static int Fibbonacci(int number)
        {
            if (number == 1 || number == 0)
            {
                return 1;
            }

            var minus2 = number - 2;
            var minus1 = number - 1;

            if (!Items.ContainsKey(minus2))
            {
                Items.Add(minus2, Fibbonacci(minus2));
            }

            if (!Items.ContainsKey(minus1))
            {
                Items.Add(minus1, Fibbonacci(minus1));
            }

            return (Items[minus2] + Items[minus1]);
        }
    }


    推荐阅读