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

当在进行大量的计算时,提升性能最直接有效的一种方式就是避免重复计算。通过在内存中缓存和重复利用相同计算的结果,称之为内存缓存。最明显的例子就是生成斐波那契数列的程序(详见第 6.66.11 节):

要计算数列中第 n 个数字,需要先得到之前两个数的值,但很明显绝大多数情况下前两个数的值都是已经计算过的。即每个更后面的数都是基于之前计算结果的重复计算,正如示例 6.11 fibonnaci.go 所展示的那样。

而我们要做就是将第 n 个数的值存在数组中索引为 n 的位置(详见第 7 章),然后在数组中查找是否已经计算过,如果没有找到,则再进行计算。

程序 Listing 6.17 - fibonacci_memoization.go 就是依照这个原则实现的,下面是计算到第 40 位数字的性能对比:

  • 普通写法:4.730270 秒
  • 内存缓存:0.001000 秒

内存缓存的优势显而易见,而且您还可以将它应用到其它类型的计算中,例如使用 map(详见第 7 章)而不是数组或切片(Listing 6.21 - fibonacci_memoization.go):

  1. package main
  2. import (
  3. "fmt"
  4. "time"
  5. )
  6. const LIM = 41
  7. var fibs [LIM]uint64
  8. func main() {
  9. var result uint64 = 0
  10. start := time.Now()
  11. for i := 0; i < LIM; i++ {
  12. result = fibonacci(i)
  13. fmt.Printf("fibonacci(%d) is: %d\n", i, result)
  14. }
  15. end := time.Now()
  16. delta := end.Sub(start)
  17. fmt.Printf("longCalculation took this amount of time: %s\n", delta)
  18. }
  19. func fibonacci(n int) (res uint64) {
  20. // memoization: check if fibonacci(n) is already known in array:
  21. if fibs[n] != 0 {
  22. res = fibs[n]
  23. return
  24. }
  25. if n <= 1 {
  26. res = 1
  27. } else {
  28. res = fibonacci(n-1) + fibonacci(n-2)
  29. }
  30. fibs[n] = res
  31. return
  32. }

内存缓存的技术在使用计算成本相对昂贵的函数时非常有用(不仅限于例子中的递归),譬如大量进行相同参数的运算。这种技术还可以应用于纯函数中,即相同输入必定获得相同输出的函数。

链接