Memoization คืออะไร และคุณจะ implement มันอย่างไร?

Question

Accepted Answer

**Memoization** คือการแคชผลลัพธ์ของฟังก์ชันโดยใช้อาร์กิวเมนต์เป็น key ดังนั้นการเรียกซ้ำด้วย input เดิมจะคืนผลลัพธ์ที่แคชไว้ทันทีแทนที่จะคำนวณใหม่ มันเป็นการแลก **หน่วยความจำเพื่อความเร็ว** และใช้ได้เฉพาะกับฟังก์ชันแบบ **pure** เท่านั้น (input เดิม → output เดิม ไม่มี side effect)

## ตัวห่อ (wrapper) memoize แบบทั่วไป

```js
function memoize(fn) {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args); // build a cache key from the arguments
    if (cache.has(key)) {
      return cache.get(key);          // cache hit — skip the work
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowSquare = n => { /* expensive */ return n * n; };
const fastSquare = memoize(slowSquare);
fastSquare(4); // computes → 16
fastSquare(4); // cached → 16 instantly
```

## ตัวอย่างคลาสสิกที่ได้ผล: Fibonacci แบบ recursive

```js
const fib = memoize(n => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// turns exponential O(2^n) into roughly O(n) by caching subproblems
```

## ข้อแลกเปลี่ยนและข้อควรระวัง

- **กลยุทธ์ในการสร้าง cache key**: `JSON.stringify` ใช้ไม่ได้กับฟังก์ชัน และลำดับของ key มีผลกับอ็อบเจกต์ สำหรับอาร์กิวเมนต์ที่เป็นอ็อบเจกต์ การใช้ `WeakMap` (ที่ key เป็น reference) จะช่วยหลีกเลี่ยง memory leak
- **การเติบโตแบบไม่จำกัด**: แคชจะไม่เคยหดเล็กลง — ใช้แคชแบบ **LRU** สำหรับโปรเซสที่ทำงานยาวนาน
- ควรทำ memoize เฉพาะเมื่อการคำนวณใหม่มีต้นทุนสูงจริง ๆ และ input เกิดซ้ำ

## ทำไมจึงสำคัญ

Memoization อยู่ทุกที่: `useMemo`/`React.memo` ของ React, selector ของ Reselect, และ dynamic programming

แนวคิด (แคชผลลัพธ์แบบ pure ตาม input) เหมือนกันทั้งหมด ศิลปะอยู่ที่การเลือก key และการจำกัดขนาดของแคช