iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 12
0
Software Development

One Punch 一拳搞定前後端面試系列 第 12

[One Punch 一拳搞定前後端面試] DAY-12 - 記憶化

記憶化(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));
    }

}

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

此篇文章同步發佈於好讀版


上一篇
[One Punch 一拳搞定前後端面試] DAY-11 - 費氏數列
下一篇
[One Punch 一拳搞定前後端面試] DAY-13 - Queue
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言