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

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

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