Tìm hiểu Memoization - Cải thiện hiệu năng xử lý của function trong JS

Search trên mạng sẽ ra một vài cách gọi khác như như Memoization in JS hoặc How to use Memoize in JS hoặc Improve performance using Memoization nhìn chung tất cả chúng đều đang đề cập tới chủ đề hôm nay Tìm hiểu về kỹ thuật memoization (ghi nhớ), để cải thiện tốc độ xử lý của function hoặc thuật toán trong JS.

Memoization dịch ra là ghi nhớ, ghi nhớ cái gì, đó là ghi nhớ "kết quả tính toán" của function hoặc của một thuật toán nào đó xử lý. Tại sao lại ghi nhớ kết quả này, tính ra kết quả rồi thôi ghi nhớ lại làm chi. Giả dụ, bạn gọi một function (function này làm nhiệm vụ đọc file trả về nội dung file) bạn truyền tham số A (tên file cần đọc), lúc này function sẽ truy cập xuống file A đọc kết quả trả về nhưng một lúc sau bạn lại gọi tiếp function này lại bảo nó đọc tiếp file A, thì có phải mất công nó xuống lấy lên đọc lại lần nữa không. Do đó lúc này mình sẽ áp dụng kỹ thuật memoize vào đây để "lưu lại" (cache) kết quả đọc file A, và nếu lần sau mình lại yêu cầu đọc file A lần nữa thì mình trả về kết quả đã lưu lại mà thôi, không cần đọc file lần nữa, như vậy tốc độ lúc này sẽ nhanh hơn rất nhiều.

Vậy mấu chốt của kỹ thuật này là kết quả tính toán được cache lại, với key dựa trên tham số truyền vào, khi tham số truyền vào giống với tham số lần trước thì không cần đi tính toán nữa, trả về kết quả đã cache.

Ví dụ thực tế

Bây giờ chúng ta sẽ sử dụng kỹ thuật này trong cách tìm dãy số Fibonacci (dãy số fibonacci là dãy số mà số tiếp theo là tổng của hai số liền trước). Ví dụ: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Thông thường để tính Fibonacci chúng ta sẽ hay dùng vòng lặp và đệ quy.

Vòng lặp

function fibonacci(num) {
  let seq = [1, 1];

  for (let i = 2; i < num; i++) {
      seq[i] = seq[i - 1] + seq[i - 2];
  }

  return seq[num - 1];
}

Đệ quy

function fibonacci(num) {
  if (num <= 1) {
    return 1;
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}

Dùng đệ quy nhìn có vẻ dễ hiểu hơn nhưng vấn đề với dùng đệ quy là hiệu suất. Vì độ phức tạp của thuật toán lúc này sẽ tăng lên O(2^N), vấn đề này mình sẽ viết ở một bài khác để nói rõ hơn. Còn hiện tại trong phạm vi bài viết này mình sẽ cài thiện vấn đề hiệu suất này nhé. Chúng ta sẽ áp dụng Memoization vào trong hàm đệ quy tính toán Fibonacci, để xem cái thiện ra sao nhé.

const cache = {};

function fibonacci(num) {
  if(num < 1) {
    return 0;
  }

  if(num < 2) {
    return 1;
  }

  if (num in cache) {
    return cache[num];
  }

  const value = fibonacci(num - 1) + fibonacci(num - 2);

  cache[num] = value;

  return value;
}

console.log(fibonacci(10)); // 55

Chúng ta định nghĩa một object tên là cache cốt để lưu lại kết quả tính toán từ hàm fibonacci với key là num (tham số truyền vào). Sau đó chúng ta check xem liệu num có được cache hay chưa (num in cache) nếu đã cache thì return value về thôi, không tính toán nữa.

Chúng ta sẽ thực hiện benchmark với cách dùng vòng lặp, đệ quy và đệ quy dùng Memoize sẽ tốc độ ra sao nhé. Và dĩ nhiên đệ quy dùng memoize thì nhanh nhất.

Benchmark với num truyền vào là 10:

• Đệ quy: ~1877 ms
• Vòng lặp: ~647 ms
• Đệ quy dùng memoize: ~511 ms

Viết một hàm để có thể dùng bất cứ đâu

Chúng ta sẽ thực hiện common code, viết một hàm để khi cần memoization hàm nào đó thì sẽ gọi mà dùng thôi nè.

function memoizer(fn) {
  let cache = {};

  return function(arg) {
    if (cache[arg]) {
      return cache[arg];
    } else {
      let result = fn(arg);
      cache[arg] = result;
      return result;
    }
  }
}

Và cách dùng như sau:

let numberFibAtTen = memoizer(fibonacci)(10);

console.log(numberFibAtTen); // kết quả là 55

Nhìn thì hơi rối ren, nhưng nếu bạn hiểu khái niệm closure trong js rồi thì rất dễ hiểu. Nhìn chung nó cũng giống như ở trên thôi, key là arg, check xem có cache value nào của key này chưa, có rồi thì return không thì thực hiện gọi function fn để tính toán.

Bonus

Ngoài ra còn có một cách tính dãy Fibonacci nữa, tên là công thức Binet. Mô tả thuật toán này tại đây

Code:

function fibonacci(n) {
  return Math.round(
    (Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow(-2 / (1 + Math.sqrt(5)), n)) / Math.sqrt(5)
  );
}

console.log(fibonacci(8)); // 21 -> chính xác gê :D

Summary

Nói chung bài ni hướng đến áp dụng kỹ thuật memoization vào để cải thiện tốc độ xử lý thuật toán của bạn, vậy nên có gì không hiểu hoặc bổ sung thì đừng ngại comment bên dưới nhé. Thanks bạn đã đọc bài.