---
url: /blog-program/improve-speed-using-memoization.md
description: 最近遇到從大矩陣資料找出指定資料的需求，是時候使用 memoization 來提升效能了。੭ ˙ᗜ˙ )੭
---

![improve-speed-using-memoization](/improve-speed-using-memoization.webp){.cover}

# 你是個成熟的 function 了，該自己記得結果了

```js
const data = [
  { name: 'A', color: 'red', condition: () => 'A' },
  { name: 'B', color: 'blue', condition: () => 'B' },
  { name: 'C', color: 'green', condition: () => 'C' },
  { name: 'D', color: 'yellow', condition: () => 'D' },
  { name: 'E', color: 'black', condition: () => 'E' },
  // ... 200 多個
]
```

想要取得符合條件的資料，最直覺的方式就是用 `filter`，例如：

```ts
function getData(color: string) {
  return data.filter((item) => item.color === color)
}
```

由於 `data` 不會變動，output 只與 input 相關。

此 function 又會大量使用，可以預期有非常多重複的運算。

這時候就可以使用 memoization 這個技巧，透過記憶化來提升計算效能。

## 什麼是 memoization

Memoization 是一種簡單的技巧，透過記憶化來提升計算效能。

當 function 被呼叫時，會先檢查是否有相同的輸入值，如果有就直接回傳記憶的結果，而不是重新計算。

就是一個使用空間換時間的概念。%◝( •ω• )◟%

使用 Vue 的朋友們，如果有用過 `computed`，其實都用過 memoization 了。

有興趣的朋友們可以看看我先前的文章「[善用 computed](https://codlin.me/blog-vue/make-good-use-of-computed)」，裡面有詳細探討。

## Lodash memoize

這次我直接使用 Lodash 提供的 [`memoize`](https://www.lodashjs.com/docs/lodash.memoize) 來實現 memoization。

口說無憑，讓我們實際跑跑看 benchmark，看看實際上差多少。

使用 [BenchJS](https://benchjs.com/) 這個酷炫的網站，可以直接在 Web 跑 benchmark，非常方便。

首先在 Code 分頁中，準備資料並撰寫實作。

首先在 `setup.ts` 裡面建立測試資料，export 後就可以在各實作中共用。

`setup.ts`

```ts
function generateTestData(size: number) {
  return Array.from({ length: size }, (_, i) => ({
    key: `${i}`,
    value: i
  }))
}
export const length = 200
export const data = generateTestData(length)
```

接著在 implementations 中建立兩個檔案，檔名與實作相同。

`implementations/memoize.ts`

```ts
import { memoize } from 'lodash'

const getData = memoize((key: string) =>
  data.find((datum) => datum.key === key),
)

export function run() {
  getData(`${length - 1}`)
}
```

`implementations/no-memoize.ts`

```ts
const getData = (key: string) => data.find((datum) => datum.key === key)

export function run() {
  getData(`${length - 1}`)
}
```

可以看到資料與實作都一樣，只差在 `memoize.ts` 的 `getData` 有 memoize。

現在讓我們到 Compare 分頁，按下 Run All。

BenchJS 會開始跑 `run` 的內容，並且計算時間。

![compare-result](/improve-speed-using-memoization/compare-result.png)

可以看到 `memoize` 比 `no-memoize` 快非常多。

不難理解，因為原本的操作之時間複雜度是 O(n)，而 memoize 後只需要 O(1)。

[範例網址](https://benchjs.com/playground#/N4IgzgLghhCmIC5QDdYCcwEsD2A7RAjADQiYC2ADgDaxmy7QQ65iIDaomAJoiAEoAjAGa40AYwBeADQBaABRkCAksgDuABgCcADwC0ADgCKIEkMw1cUOrzplsmCbAB0EViTF44DXuQrY0EAAEwIG29o6BAL6BQmjYZIEA5FTYXFBgABaJADq4uR4sQQDmsBAAIjBQgQC8obThsAAUjQDWsACeCIGQaJi4RQCUNQB8uYGBadBOZrhczZMArmRD1cMTMEtObe011bXbA0S5A7m5sNp+ATELuGJMeIFoN41DwGOBJeWVjQAGACTACxFCAZQK6QIESI-E64SIgSJETg8BDgMSwABW2AEACYFmg+FB9AAxAASLRk6QA8pgKCYQGYLFZ4CjcNhdGEHM5XHSCl4ILwCpAPqUKtAaoFWh0uj0+oMRuspjM5o1Fst5aqth1dvsOjCzhd-EEhDc7sxHs9Xu9PqKoL8AUCQWCIVCYXDIgBdEhQU2oAAqUGUyPApQWFBcbmDEFDAGFUsz6Sb7rhhbh0DBYL7YJAbY0sI4urglgJ0Jbk48Q2hkwBBNBoKDtaZxMiNEIOjLSzlRIgSgD63cwKzWLfe422XX+wEwUKOZfGyCgVAWsC6mHekQGrv1lyCgqCbfF2PU6i3hsCu4VVVqJVTdbgmez3zbAzpYBDFDKvoAyrwuLAxFQoDQWAPhSAQF2Cd5f3-QDgPPfdakPdQAG5IL-ACgLPPAhUmKAujeWdxkCMduggXp+hQgi5wXJcCyLdAKPGSI2HdBjAlySJTlTA0rmASIkLpICoC4OhYwYeh+RRABiQJDAWTAxBaQJP2gK4AHE5N-TjJOkolzGA5SnjuPFYFycFXyjMNXC6T830w39AggbBAgoICKBgi9uzEQS4ECDJYCoCh0GuW4kzAbtSjEJxTMCXwaDoBgYGYMAAHoAConGAVwiHRMBIi6JRKDi8TEoeBks0whK+llQJi1uDIyEAloiTyFrtMCAB1XomH6QIACF6DEerGrATiCCcJTbNzN9wwGBBOIAUVQNB2hBar2mwBZAnObdAlUcwqBq4CoHncwAxoQJ0gukCsXAoR-C271QVi2hiqTKKWp+T6IHaQKwC8mkIFyZLkrPbyjtmLbuKCOBsMqE8rnPHDxRrOsG1ieIW0CNsugII91C7Xt+0HGKBgo7bT3PMAlnFRpALQWiyGLNBmOJumnCArgFjRZooG7ARWcCABqGru3UUnck+n5OOxcaCuoF6EtCiVziseWZrmlq5aKxXmF0MBArETAzDEOzgKKbByr8oDuygCH1s21NYC4BynPJq4qmNEKzUsOhncSJ5cESd6Ja+n6s3+ihAa4nbzwDmnifw8YgKjSsL3Zp2uaaKmyFF8XYRDqX8BIKhMAEOteizdhQB9+MUjSTJ4XdBEQCWrA8EISIgA)

## 為甚麼不要都 memoization 就好？

因為實作 memoization 也需要額外的計算與記憶體。

在資料很少、計算負荷極低的情況下，可能沒什麼差別，甚至可能比較慢。

在這次的例子中，把 `length` 改成 5，再跑一次 benchmark。

```txt
memoize.ts     141,218,403   (-0.7%)
no-memoize.ts  142,192,549   Best
```

會看到結果很接近，甚至 `no-memoize` 還比 `memoize` 快一點。

所以實際上要看情況使用，不是所有情況都適合使用 memoization。

真的遇到性能瓶頸，需要進行改善時，再來評估改進方案。

記得要跑 benchmark，有多少證據，說多少話喔。%( ´ ▽ \` )ﾉ%

## 總結 🐟

* memoization 可以提升效能，透過記憶化來避免重複計算。
* 不是所有情況都適合使用 memoization，要看情況使用。
* 記得要跑 benchmark，才能確定是否真的有提升效能。