Tìm Hiểu Kỹ Thuật Memoization

Khi tìm kiếm thông tin trên Internet, bạn có thể bắt gặp nhiều thuật ngữ liên quan đến memoization trong JavaScript như 'Memoization in JS', 'How to use Memoize in JS', hay 'Improve performance using Memoization'. Bài viết này sẽ giúp bạn hiểu rõ về kỹ thuật memoization (ghi nhớ) và cách ứng dụng nó để cải thiện tốc độ xử lý của các hàm hoặc thuật toán trong JavaScript.

Memoization Là Gì?

Memoization là một kỹ thuật lưu trữ (cache) kết quả tính toán của một hàm để tiết kiệm thời gian xử lý trong các lần gọi hàm tiếp theo với cùng tham số. Ví dụ, khi bạn gọi một hàm đọc tệp tin với tham số là tên tệp, hàm sẽ đọc dữ liệu từ tệp đó. Nếu bạn yêu cầu đọc lại tệp đó lần nữa, thay vì đọc lại từ đầu, kỹ thuật memoization sẽ cho phép hàm trả về kết quả đã được lưu trữ, từ đó cải thiện hiệu suất đáng kể.

Ứng Dụng Kỹ Thuật Memoization Trong Tính Toán Dãy Số Fibonacci

Dãy số Fibonacci là một dãy số mà mỗi số sau là tổng của hai số liền trước, bắt đầu từ 1 và 1. Hãy xem xét hai cách thông dụng để tính dãy Fibonacci: bằng vòng lặp và đệ quy.

Cách 1: Sử Dụng 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];
}

Cách 2: Sử Dụng Đệ Quy

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

Mặc dù cách dùng đệ quy có vẻ dễ hiểu, nhưng hiệu suất của nó lại không cao. Độ phức tạp thuật toán của phương pháp đệ quy là O(2^N), dẫn đến thời gian tính toán lâu hơn.

Để khắc phục vấn đề này, chúng ta sẽ áp dụng kỹ thuật memoization vào hàm đệ quy tính toán Fibonacci như sau:

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

Trong đoạn mã trên, chúng ta định nghĩa một đối tượng cache để lưu kết quả tính toán. Nếu tham số đã có trong cache, chúng ta chỉ cần trả về kết quả đó mà không cần thực hiện thêm tính toán.

So Sánh Thời Gian Thực Hiện

Chúng ta sẽ tiến hành so sánh thời gian thực hiện giữa cách dùng đệ quy, vòng lặp và đệ quy với memoization cho giá trị num bằng 10:

• Đệ quy: ~1877 ms
• Vòng lặp: ~647 ms
• Đệ quy với memoization: ~511 ms

Đoạn mã sử dụng memoization cho thấy rõ hiệu suất tốt hơn nhiều so với hai phương pháp còn lại.

Tạo Hàm Memoizer Chung

Chúng ta có thể viết một hàm memoizer để sử dụng cho bất kỳ hàm nào cần memoization:

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

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

Sử dụng như sau:

let numberFibAtTen = memoizer(fibonacci)(10);
console.log(numberFibAtTen); // 55

Khái niệm này có thể hơi phức tạp nhưng nếu bạn quen với closure trong JavaScript, bạn sẽ thấy dễ hiểu. Tổng quan, hàm này kiểm tra xem có giá trị đã lưu cho tham số không, nếu có thì trả về trực tiếp, nếu chưa có thì tính toán và lưu vào cache.

Phương Pháp Khác Tính Dãy Fibonacci

Một phương pháp khác để tính dãy Fibonacci là sử dụng công thức Binet như sau:

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

Kết Luận

Bài viết này đã giúp bạn hiểu rõ hơn về kỹ thuật memoization và cách ứng dụng nó để cải thiện hiệu suất xử lý của các thuật toán trong JavaScript. Nếu bạn có bất kỳ câu hỏi nào hay muốn bổ sung thêm, hãy để lại bình luận bên dưới nhé! Cảm ơn bạn đã đọc bài.
source: viblo