Go語言通過記憶體快取來提升效能

前面我們介紹了遞回函數，遞回函數的缺點就是比較消耗記憶體，而且效率比較低，那麼我們要怎樣提高程式的執行效率呢？

當在進行大量計算的時候，提升效能最直接有效的一種方式是避免重複計算，通過在記憶體中快取並重複利用快取從而避免重複執行相同計算的方式稱為記憶體快取。

下面我們以經典的遞迴求斐波那契數列為例，來對比一下普通實現方法和加入記憶體快取後程式的執行情況。

普通的實現方法

普通方法的實現思路是，要計算數列中第 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 位: %dn", i, result)
    }
    end := time.Now()
    delta := end.Sub(start)
    fmt.Printf("程式的執行時間為: %sn", 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 位: %dn", i, result)
    }
    end := time.Now()
    delta := end.Sub(start)
    fmt.Printf("程式的執行時間為: %sn", 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 秒，對比之前未使用記憶體快取時的執行效率，可見記憶體快取的優勢還是相當明顯的。