# JavaScript - Memoization 記憶函式
###### tags: `JavaScript` `Event Loop` `讀書會`
## 什麼是 Memoization ?
記憶函式 ( Memoization ) 是一種優化程式技巧，把需要大量計算 ( 長遞歸、長迭代操作 ) 的函式將其參數與結果緩存 ( Cache )，若調用記憶函式且給予相同參數時，不須經過計算程序，直接回傳相同結果。
<br>
## 沒有 Cache 機制的程式
假設有一個工人，這位工人需要去倉庫拿工具 ( getTool ) 來完成他的工作 ( task ) :
```javascript
function getTool (task) {
console.log('前往倉庫拿取工具')
return task + '工作完成'
}
```
<br>
但我們會發現，如果工人做同樣的工作 ( task )，他仍然會不斷跑去倉庫拿取工具 :
Day 1：工人 ( 小明 ) 第一天修理大水管，跑到倉庫拿工具。
Day 2：工人 ( 小明 ) 第二天繼續修理大水管，還是跑到倉庫拿工具。
Day 3：工人 ( 小明 ) 第三天繼續修理大水管，還是跑到倉庫拿工具
( 小明 OS : e04，給我工具箱 ! )。
<br>
### 身為哆啦工具夢的我們，來實現小明的願望吧 !
讓我們把拿取工具 ( getTool ) 過程優化 :
```javascript
function getTool (todoTask) {
const doneCache = {} // 已經做過同樣的工作 cache
return function () {
// 工作內容
const taskContent = JSON.stringify(arguments)
// 如果已經有做過同樣的工作
if (doneCache[taskContent]) {
return doneCache[taskContent] // 直接回傳工具對應的工作內容
}
// 如果工具箱沒有工作所需要的工具
else {
// 工作結果
const doTaskResult = todoTask.apply(this, arguments)
// cache 儲存工作結果，並回傳
doneCache[taskContent] = doTaskResult
return doTaskResult
}
}
}
```
然後訂定小明一個工作流程 :
```javascript
const work = getTool((task) => {
console.log('前往倉庫拿工具')
return task + ': 已完成工作'
})
```
<br>
如此一來，當小明做同樣的工作，他就知道已經有拿過工具，直接執行工作內容就可以了 !
<br>
但是當小明每天做不同的工作，他還是得回去倉庫拿給西 ( 工具 ) :
<br>
## 設計一個 Momoized Function
每個功能函式都要寫成 Memoized Function 太麻煩，不妨設計一個 Memoize 工具函式吧 !
```javascript
const memoize = (func) => {
const cache = {}
return (...args) => {
const key = JSON.stringify(args)
if (cache[key] === undefined) {
cache[key] = func(...args)
}
return cache[key]
}
}
```
<br>
## Memoization 使用時機
- 當函式需要消耗大量效能來運算 ( Expensive function calls, heavy computations )。
- 經常會需要將前一次的值再次帶入的遞迴函式 ( Recursive function )。
<br>
## Memoization 需注意的問題
Cache 雖然可以優化執行效能，但 Cache 也會因處理大量資料 ( 有很多不同的資料 ) 時，占用大量記憶體且不會釋放，因此 Memoization 也是一把雙面刃，需要注意使用時機。
<br>
## Vue 也有相同的機制
Vue 也有提供給我們選擇使用 Memoization 或者不使用，也就是 Computed 及 Methods 方法。`computed` 帶有 Cache 機制，也就是在 Computed 它是屬於 Memoization，這也是為什麼 `computed` 都要求一定要 return 結果，否則會報錯，而 `methods` 就沒有 Cache 了，每次呼叫 Methods 的方法時都會重新執行。
此外，主流框架對於 Virtual DOM 渲染基本上都有 Cache 的機制，因此可以時常看見對於效能好的裝置來說，瀏覽有使用 Framework 的網頁時，整體網頁瀏覽較為順暢，但若是效能或記憶體容量較差的裝置來說，瀏覽使用 Framework 的網頁時常會有跑不動 ( Lag ) 的感覺。
<br>
---
## Memoization 運用在 Fibonacci ( 費波那契數列 )
費波納契數列 ( Fibonacci Sequence ) 指的是 :
```javascript
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
```
<br>
建立一個 Fibonacci 查詢函式
```javascript
// n 為查詢費波那契數列第幾筆的值
const fibonacci = n => {
return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
}
```
除了 `n = 1`、`n = 2` 的情況外，可以觀察每個 fibonacci 計算出來的值都是前兩個 fibonacci 相加的結果，也就是
```javascript
fibonacci(n) === fibonacci(n - 1) + fibonacci(n - 2)
```
<br>
### Time Complexity 時間複雜度
然而，利用這種初步的遞迴函式演算法是屬於 O(n^2)，也就是當 n 的值愈大，運算所花費的時間會呈指數 ( 爆炸性 ) 成長 :
```javascript
fibonacci(3) // 執行 3 次函式
fibonacci(5) // 執行 9 次函式
fibonacci(7) // 執行 25 次函式
fibonacci(10) // 執行 109 次函式
fibonacci(20) // 執行 13259 次函式
fibonacci(30) // 執行 1664079 次函式
fibonacci(99) // 你不會想試的
```
圖片來源：[Learning Algorithms in JavaScript from Scratch](https://www.udemy.com/course/learning-algorithms-in-javascript-from-scratch/) by [Eric Traub](https://www.udemy.com/user/eric-traub/) @ Udemy
<br>
### Memoized Fibonacci
我們可以用上面設計的 Momoized Function 來封裝 `fibonacci` :
```javascript
const memoize = (func) => {
const cache = {}
return (...args) => {
const key = JSON.stringify(args)
if (cache[key] === undefined) {
cache[key] = func(...args)
}
return cache[key]
}
}
const fibonacci = memoize((n) => {
return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
})
```
<br>
## Reference
[JavaScript Memoization 故事介紹](https://medium.com/@vx3012564897/javascript-memoization-%E6%95%85%E4%BA%8B%E4%BB%8B%E7%B4%B9-d070b7e8699f)
[JavaScript記憶（Memoization）函數](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/717300/)
[實現 JavaScript 的 Memoization](https://fred-zone.blogspot.com/2017/04/javascript-memorization.html)
[[演算法] Fibonacci：善用 cache 和 Memoization 提升程式效能](https://pjchender.blogspot.com/2017/09/fibonacci-cache-memoization.html)
Sign in with Wallet
Connect another wallet