缓存递归计算

内存缓存适合快速复用结果的场景。在递归求解过程中，原问题与子问题的求解思路一致，缓存其上一步结果，能极大提高 使用递归的计算性能。本文以斐波那契数列求解，涉及go数组，反射，函数变量，变长参数等技能点，适合新手入门。

需求分析

• 计算性能通常需要时间开销，用到time包
• 在求解已知变量指向的函数名，采用反射reflect包

斐波那契数列的前几个数字是这样的：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

通过这些数字的排列规律总结出对应的计算公式：

F(1) = 0
F(2) = 1
...
F(n) = F(n-1) + F(n-2)

反射获取函数名

 func GetFunctionName(i interface{}, seps ...rune) string {
     //  获取函数名
     fn := runtime.FuncForPC(reflect.ValueOf(i).Pointer()).Name()

     // 用seps用进行分割
     fields := strings.FieldsFunc(fn, func(sep rune) bool {
         for _, s := range seps {
             if sep == s {
                 return true
             }
         }
         return false
     })

     if size := len(fields); size > 0 {
         return fields[size-1]
     }
     return ""
 }

时间开销

参数f为函数变量，其签名是一个斐波那契数列函数 func(int) int

 func spend_time(n int, f func(int) int) {
     start := time.Now()
     num := f(n)
     // time.Since方法与下面等价
     // end := time.Now()
     // consume := end.Sub(start).Seconds()
     consume = time.Since(start)
     fmt.Printf("Running function is: %s\n", GetFunctionName(f))
     fmt.Printf("The %dth number of fibonacci sequence is %d\n", n, num)
     fmt.Printf("It takes %f seconds to calculate the number\n\n", consume)
 }

递归求解

下面为不使用缓存和使用缓存中间结果来求斐波那契数列求解的两个函数

 func no_cache(n int) int {
     if n == 1 {
         return 0
     }
     if n == 2 {
         return 1
     }
     return no_cache(n-1) + no_cache(n-2)
 }

 func fibonacci(n int) int {
     if n == 1 {
         return 0
     }
     if n == 2 {
         return 1
     }

     index := n - 1
     // 读取缓存
     if fibs[index] != 0 {
         return fibs[index]
     }
     num := fibonacci(n-1) + fibonacci(n-2)
     // 缓存子问题的计算结果，避免重复计算
     fibs[index] = num
     return num
 }

入口主体

package main

 import (
     "fmt"
     "reflect"
     "runtime"
     "strings"
     "time"
 )

 const MAX = 100
 var fibs [MAX]int

 func main() {
     spend_time(30, no_cache)
     spend_time(30, fibonacci)
 }

效果比对

Running function is: main.no_cache
The 30th number of fibonacci sequence is 514229
It takes 0.007108 seconds to calculate the number

Running function is: main.fibonacci
The 30th number of fibonacci sequence is 514229
It takes 0.000001 seconds to calculate the number

结论

大量的重复递归计算堆积，最终导致程序执行缓慢
通过缓存中间计算结果来避免重复计算，对递归程序性能有指数级的提高

本作品采用《CC 协议》，转载必须注明作者和本文链接