Cách sử dụng tính năng Memoize vào bộ nhớ của JavaScript và tăng tốc độ đoạn code của bạn

Bài dịch từ trang Medium Function là một phần của chương trình. Chúng modularity hóa và khả năng sử dụng lại cho code của chúng ta. Nó khá phổ biến để chia chương trình của chúng ta thành các khối bằng cách sử dụng các function mà chúng tôi có thể gọi sau để thực hiện một số hành động hữu ích. Đôi khi, một function có thể trở nên tốn kém để gọi nhiều lần (một function để tính factorial của một số). Nhưng có một cách chúng ta có thể tối ưu hóa các function như vậy và làm cho chúng chạy nhanh hơn: bộ nhớ đệm.

Ví dụ: giả sử chúng ta có một hàm để trả về giai thừa của một số:

function factorial(n) {
    // Calculations: n * (n-1) * (n-2) * ... (2) * (1)
    return factorial
}

Tuyệt vời, bây giờ hãy tìm giai thừa (50). Máy tính sẽ thực hiện tính toán và trả lời cho chúng ta câu trả lời cuối cùng! Khi đó xong, hãy tìm factorial (51). Máy tính lại thực hiện một số tính toán và cho chúng ta kết quả, nhưng bạn có thể nhận thấy rằng chúng tôi đã lặp lại một số bước mà bạn có thể tránh được. Một cách tối ưu hóa sẽ là:

factorial(51) = factorial(50) * 51

Nhưng function của chúng ta thực hiện tính toán từ đầu mỗi khi nó được gọi là:

factorial(51) = 51 * 50 * 49 * ... * 2 * 1

Nó sẽ tốt hơn nếu function giai thừa của chúng ta có thể nhớ các giá trị từ các tính toán trước đó của nó và sử dụng chúng để tăng tốc độ thực hiện? Trong memoization, một cách cho function của chúng ta để nhớ (cache) kết quả. Bây giờ bạn đã có một sự hiểu biết cơ bản về những gì chúng tôi đang cố gắng để đạt được, dưới đây là một định nghĩa chính thức:

*Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again *

Dưới đây là những gì một memoized function đơn giản:

// a simple function to add something
const add = (n) => (n + 10);
add(9);
// a simple memoized function to add something
const memoizedAdd = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
// returned function from memoizedAdd
const newAdd = memoizedAdd();
console.log(newAdd(9)); // calculated
console.log(newAdd(9)); // cached

Memoization takeaways

Một vài điều rút ra từ đoạn code trên:

• MemoizedAdd trả về một function được gọi sau. Điều này có thể xảy ra bởi vì trong JavaScript, các function là các đối tượng lớp đầu tiên cho phép chúng ta sử dụng chúng như hàm bậc cao hơn và trả về một hàm khác.
• Bộ nhớ cache có thể nhớ các giá trị của nó kể từ khi hàm trả về có một closure trên nó.
• Điều thiết yếu là memoized function là "pure". Một pure function sẽ trả lại kết quả tương tự cho một đầu vào cụ thể không kể bao nhiêu lần nó được gọi, làm cho bộ nhớ cache hoạt động như mong đợi.

Writing your own memoize function

Các đoạn code trước đây hoạt động tốt nhưng nếu chúng ta muốn chuyển bất kỳ function vào một memoized function? Dưới đây là cách viết memoized function của riêng bạn:

// a simple pure function to get a value adding 10
const add = (n) => (n + 10);
console.log('Simple call', add(3));
// a simple memoize function that takes in a function
// and returns a memoized function
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];  // just taking one argument here
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
// creating a memoized function for the 'add' pure function
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3));  // calculated
console.log(memoizedAdd(3));  // cached
console.log(memoizedAdd(4));  // calculated
console.log(memoizedAdd(4));  // cached

Tuyệt! Memoize function đơn giản này sẽ bao bọc bất kỳ Memoize function thành một bản ghi nhớ tương đương. Code sẽ hoạt động tốt với các functions đơn giản và nó có thể dễ dàng tinh chỉnh để xử lý bất kỳ số lượng các đối số theo nhu cầu của bạn.

Memoizing recursive functions

Nếu bạn cố gắng truyền một hàm đệ quy tới memoize function ở trên hoặc memoize từ Lodash, kết quả sẽ không như mong đợi vì hàm đệ quy trên các cuộc gọi tiếp theo của nó sẽ kết thúc tự gọi mình thay vì chức năng ghi nhớ, do đó không sử dụng của bộ nhớ cache. Chỉ cần chắc chắn rằng hàm đệ quy của bạn đang gọi memoize function. Đây là cách bạn có thể điều chỉnh một ví dụ điển hình của sách giáo khoa

// same memoize function from before
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];
    if (n in cache) {
      console.log('Fetching from cache', n);
      return cache[n];
    }
    else {
      console.log('Calculating result', n);
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
const factorial = memoize(
  (x) => {
    if (x === 0) {
      return 1;
    }
    else {
      return x * factorial(x - 1);
    }
  }
);
console.log(factorial(5)); // calculated
console.log(factorial(6)); // calculated for 6 and cached for 5

Một vài điểm cần lưu ý:

• Hàm chức năng là đệ quy gọi một phiên bản được ghi nhớ của chính nó.
• Chức năng ghi nhớ là lưu trữ các giá trị của các giai thừa trước đó giúp cải thiện đáng kể tính toán vì chúng có thể được sử dụng lại (6) = 6 * factorial (5)

Is memoization same as caching?

Memoization thực sự là một loại bộ nhớ đệm cụ thể. Trong khi bộ nhớ đệm có thể tham khảo chung cho bất kỳ kỹ thuật lưu trữ nào (như bộ nhớ đệm HTTP) để sử dụng trong tương lai, ghi nhớ đặc biệt liên quan đến việc lưu trữ các giá trị trả về của một hàm.

When to memoize your functions

Mặc dù nó có thể giống như memoization có thể được sử dụng với tất cả các chức năng, nó thực sự có một số trường hợp nên sử dụng hạn chế:

• Để ghi nhớ một function, nó phải là pure để các giá trị trả lại là như nhau cho cùng một đầu vào mỗi lần
• Memoizing là một sự cân bằng giữa không gian bổ sung và tốc độ được thêm vào và do đó chỉ có ý nghĩa đối với các function có một dải đầu vào giới hạn để các giá trị được lưu trữ có thể được sử dụng thường xuyên hơn.
• Nó có thể giống như bạn nên ghi nhớ các cuộc gọi API của bạn tuy nhiên nó không cần thiết vì trình duyệt tự động lưu trữ chúng cho bạn. Xem Bộ nhớ đệm HTTP để biết thêm chi tiết
• Các trường hợp sử dụng tốt nhất tôi tìm thấy cho các chức năng memoized là cho các chức năng tính toán nặng mà có thể cải thiện đáng kể hiệu suất (factorial và fibonacci không phải là thực sự tốt ví dụ thế giới thực)
• Nếu bạn vào React / Redux bạn có thể kiểm tra lại lựa chọn sử dụng một bộ nhớ memoized để đảm bảo rằng tính toán chỉ xảy ra khi một sự thay đổi xảy ra trong một phần liên quan của cây trạng thái.