Memoization là gì và bạn cài đặt nó như thế nào?

Question

Accepted Answer

**Memoization** lưu vào cache các kết quả của một hàm theo khóa là các đối số của nó, nên các lần gọi lặp lại với cùng đầu vào sẽ trả về kết quả đã cache ngay lập tức thay vì tính toán lại. Nó đánh đổi **bộ nhớ lấy tốc độ** và chỉ hoạt động với các hàm **thuần (pure)** (cùng đầu vào → cùng đầu ra, không có side effect).

## Một wrapper memoize tổng quát

```js
function memoize(fn) {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args); // xây khóa cache từ các đối số
    if (cache.has(key)) {
      return cache.get(key);          // cache hit — bỏ qua công việc
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowSquare = n => { /* tốn kém */ return n * n; };
const fastSquare = memoize(slowSquare);
fastSquare(4); // tính toán → 16
fastSquare(4); // từ cache → 16 ngay lập tức
```

## Một chiến thắng kinh điển: Fibonacci đệ quy

```js
const fib = memoize(n => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// biến O(2^n) hàm mũ thành xấp xỉ O(n) bằng cách cache các bài toán con
```

## Đánh đổi và lưu ý

- **Chiến lược khóa cache**: `JSON.stringify` thất bại với hàm, và thứ tự khóa quan trọng với object. Với đối số là object, một `WeakMap` (khóa theo tham chiếu) tránh được rò rỉ bộ nhớ.
- **Tăng trưởng không giới hạn**: cache không bao giờ co lại — dùng một cache **LRU** cho các tiến trình chạy lâu.
- Chỉ memoize khi việc tính toán lại thực sự tốn kém và đầu vào lặp lại.

## Tại sao điều này quan trọng

Memoization có ở khắp nơi: `useMemo`/`React.memo` của React, các selector của Reselect, quy hoạch động (dynamic programming).

Khái niệm (cache các kết quả thuần theo đầu vào) là như nhau; nghệ thuật nằm ở việc chọn khóa và giới hạn cache.