2017年9月23日

[演算法] Fibonacci：善用 cache 和 Memoization 提升程式效能

      , ,  
此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。
Memoization 是一種優化的技巧，透過藉由將函式的回傳值暫存起來，來提升效能，一旦發現有相同的輸入時（same inputs），就直接回傳暫存值出去。這裡的關鍵字就是「相同的輸入（same inputs）」。

前置知識: 費波那契數列（Fibonacci Sequence）

費波那契數列（Fibonacci Sequence）指的是：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
每個數字都是前兩個數字的和，例如 1+1=2, 1+2=3, 2+3=5, 3+5=8, ...，以此類推。

問題描述

建立一個函式 fibonacci 代入參數 position，position 表示的是想要得到 fibonacci sequence 中的第幾個數字的值。
function fibonacci (position) {...}
fibonacci(4)    // 3
fibonacci(9)    // 34

使用遞回函式

這裡一樣可以透過遞回函式來處理，我們先觀察一下 Fibonacci Sequence：
fibonacci(1)   // 1
fibonacci(2)   // 1
fibonacci(3)   // 2 fibonacci(2) + fibonacci(1)
fibonacci(4)   // 3 fibonacci(3) + fibonacci(2)
fibonacci(5)   // 5 fibonacci(4) + fibonacci(3)
fibonacci(6)   // 8 fibonacci(5) + fibonacci(4)
從上面我們可以發現，除了 position 為 1 和 position 為 2 的情況之外，其他的都是前兩個相加，也就是：
fibonacci (position) === fibonacci (position - 1) + fibonacci (position - 2)

初步解法

因此利用遞回函式的概念，可以寫出：
function fibonacci (position) {
  if (position <= 2) {
    // position === 1 || position === 2
    return 1
  } else {
    return fibonacci(position - 1) + fibonacci(position - 2)
  }
}

fibonacci(6)   // 5, fibonacci(4) + fibonacci(3)

Time Complexity

然而，利用這種初步的遞回函式的演算法是屬於 O(n^2)，也就是說當 position 輸入的數值越大時，運算的時間會呈指數（爆炸性的）成長：
fibonacci(3) ，需要執行 3 次該函式
fibonacci(5) ，需要執行 9 次該函式
fibonacci(7) ，需要執行 25 次該函式
fibonacci(10) ，需要執行 109 次該函式
fibonacci(20) ，需要執行 13259 次該函式
fibonacci(30) ，需要執行 1664079 次該函式
因此，可以看得出來單純透過遞回函式並不是解決 Fibonacci Sequence 非常好的演算法。
圖片來源：Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

進階解法：Memoized Fibonacci

在第二的方法中，我們使用到的是 ++Memoization(Tabulation)++，搭配遞回函式：
  • 檢驗數字是否已經存在 cache 當中
  • 如果這個數字已經在 cache 中，則使用這個數字
  • 如果這個數字不在 cache 中，把它算出來後放在 cache 中，因此可以在未來被使用
// cache: an array used as memory
function fibMemo (index, cache) {...}

程式碼

function fibMemo (position, cache = []) {
  if (cache[position]) {
    // 如果在 cache 中有找到該 position 的數值，則直接回傳不用重算
    return cache[position]
  } else {
    // 如果在 cache 中沒有找到該 position 的數值，則計算該 position 的數值，並存到 cache 中
    if (position <= 2) {
      cache[position] = 1
    } else {
      cache[position] = fibMemo(position - 1, cache) + fibMemo(position - 2, cache)
    }
    return cache[position]
  }
}

Time Complexity

利用這種函式的演算法是屬於 O(n)，也就是說當 position 輸入的數值越大時，運算的時間會只會以線性成長：
fibMemo (3) ，需要執行 3 次該函式
fibMemo (5) ，需要執行 7 次該函式
fibMemo (7) ，需要執行 11 次該函式
fibMemo (10) ，需要執行 17 次該函式
fibMemo (20) ，需要執行 37 次該函式
fibMemo (30) ，需要執行 57 次該函式
因此我們可以看出，使用 Memoization 的技巧，將計算好的值存到 cache 裡面，是比較好的演算法。
圖片來源：Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

完整程式碼

/**
 * Fibonacci through recursive function
 * O(n^2) which is not a good algorithm
**/
function fibonacci (position) {
  counter++
  if (position <= 2) {
    // position === 1 || position === 2
    return 1
  } else {
    return fibonacci(position - 1) + fibonacci(position - 2)
  }
}
fibonacci(20)

/**
 * Memorized Fibonacci: save the computed result in cache and reuse it
**/
function fibMemo (position, cache = []) {
  if (cache[position]) {
    /**
     * 如果在 cache 中有找到該 position 的數值，
     * 則直接回傳不用重算
    **/
    return cache[position]

  } else {
    /**
     * 如果在 cache 中沒有找到該 position 的數值，
     * 則計算該 position 的數值，並存到 cache 中
    **/
    if (position <= 2) {
      cache[position] = 1
    } else {
      cache[position] = fibMemo(position-1, cache) + fibMemo(position-2, cache)
    }

    return cache[position]
  }
}

fibMemo(20)
Algorithm: Fibonacci

延伸閱讀 - Memoization

Memoization is an optimization technique that speeds up applications by storing the results of expensive function calls and returning the cached result when the same inputs are supplied again.
適合使用 Memoization 的時機：
  • 對於所有需要昂貴運算資源的函式（expensive function calls, heavy computations）。
  • 經常會用在需要將前一次的值再次帶入的遞迴函式（recursive function）。
Understanding Memoization In JavaScript

資料來源

0 意見:

張貼留言