記憶化(Memoization)

上一篇費氏數列的遞迴比較慢，但是遞迴可不可以加速呢？

答案是可以的，我們可以使用 記憶化(Memoization) 技術。

這會在面試時，當面試官看到你寫出遞迴寫法，他極有可能會請你加速這個遞迴方法，這時就可以用記憶化(Memoization)。

記憶化 (Memoization) 簡單說明

記憶化是電腦科學常用的最佳化技術，主要用來加速方法或函式之間的呼叫，把之前呼叫過的方法所回傳的東西先記憶起來，就不用每次都從新呼叫一次。

費氏數列遞迴的 Memoization 寫法

我們來解決上一篇的費氏數列遞迴寫法多次呼叫同樣方法的問題。

比如： fib(5)

fib(5) 會去做 fib(4)與 fib(3)

fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0) -> 1
       -> fib(1) -> 1
       
       -> fib(2) -> fib(1), fib(0) -> 1

fib(3) -> fib(2) -> fib(1), fib(0) -> 1
       -> fib(1) -> 1

fib(2), fib(3) 跟 fib(1) 都重複呼叫了，因此我們只要把他們呼叫過回傳的值記憶化，就不用重新再呼叫一次。

我們先創一個 memoizedMap ，之後把呼叫過的方法(函式)丟進去，後面再呼叫就直接 return 值，而不需重複呼叫。

實作如下。

JavaScript 寫法

function memoize(fn) {
  const memoizedMap = {};
  return function(...args) {
    if (memoizedMap[args]) {
      return memoizedMap[args];
    }

    const result = fn.apply(this, args);
    memoizedMap[args] = result;

    console.log(result)
    return result;
  };
}

function fib1(n) {
  if (n < 2) {
    return n;
  }

  return fib1(n - 1) + fib1(n - 2);
}

const fib = memoize(fib1);

// 測試 fib(10)
fib(10)

Java 寫法

public class FibonacciEx2 {
    
    private static int fib(int n) {
       HashMap<Integer, Integer> memoizedMap = new HashMap<>();

       memoizedMap.put(0, 0);
       memoizedMap.put(1, 1);

       return fib(n, memoizedMap);
    }

    private static int fib(int n, Map<Integer, Integer> map) {
        if (map.containsKey(n))
            return map.get(n);

        int fibFromN = fib(n - 1, map) + fib(n - 2, map);

        // 記憶化算過的值，並放入 Map 物件。
        map.put(n, fibFromN);

        return fibFromN;
    }

    // 測試 fib(10)   
    public static void main(String[] args) {
        System.out.println(fib(10));
    }

}

這樣就可以加快我們的遞迴了，下次被問到就知道有這個方法解囉！

此篇文章同步發佈於鐵人賽。