golang 通过内存缓存来提升性能

普通方法的实现思路是, 要计算数列中第 n 个数字, 需要先得到它前面的两个数, 以此类推。这么做的弊端是会产生大量的重复计算, 代码如下所示：

package main
import (
        "fmt"
        "time"
)
func main() {
        result := 0
        start := time.Now()
        for i := 1; i <= 40; i++ {
        result = fibonacci(i)
        fmt.Printf("数列第 %d 位: %d\n", i, result)
        }
        end := time.Now()
        delta := end.Sub(start)
        fmt.Printf("程序的执行时间为: %s\n", delta)
}
func fibonacci(n int) (res int) {
        if n <= 2 {
                res = 1
        } else {
                res = fibonacci(n-1) + fibonacci(n-2)
        }
        return
}

运行结果如下所示：

数列第 1 位: 1

数列第 2 位: 1

数列第 3 位: 2

数列第 4 位: 3

...

数列第 39 位: 63245986

数列第 40 位: 102334155

程序的执行时间为: 2.2848865s

通过运行结果可以看出, 获取第 40 位的数字所需要的时间是 2.2848865 秒

内存缓存的实现方法

内存缓存的实现思路是在计算得到第 n 个数的同时, 将它的值保存到数组中索引为 n 的位置上, 在后续的计算中先在数组中查找所需要的值是否计算过, 如果找到了, 则直接从数组中获取, 如果没找到, 则再进行计算, 代码如下所示：

package main
import (
        "fmt"
        "time"
)
const LIM = 41
var fibs [LIM]uint64 // 数组长度可以使用常量, 但不能使用变量
func main() {
        var result uint64 = 0
        start := time.Now()
        for i := 1; i < LIM; i++ {
        result = fibonacci(i)
        fmt.Printf("数列第 %d 位: %d\n", i, result)
        }
        end := time.Now()
        delta := end.Sub(start)
        fmt.Printf("程序的执行时间为: %s\n", delta)
}
func fibonacci(n int) (res uint64) {
        // 记忆化：检查数组中是否已知斐波那契（n）
        if fibs[n] != 0 {
        res = fibs[n]
        return
        }
        if n <= 2 {
        res = 1
        } else {
        res = fibonacci(n-1) + fibonacci(n-2)
        }
        fibs[n] = res
        return
}

运行结果如下所示：

数列第 1 位: 1

数列第 2 位: 1

数列第 3 位: 2

数列第 4 位: 3

...

数列第 39 位: 63245986

数列第 40 位: 102334155

程序的执行时间为: 0.0149603s

通过运行结果可以看出, 同样获取数列第 40 位的数字, 使用内存缓存后所用的时间为 0.0149603 秒, 对比之前未使用内存缓存时的执行效率, 可见内存缓存的优势还是相当明显的。