Tìm hiểu memoization trong Javascript

Khi các ứng dụng của chúng ta phát triển và bắt đầu thực hiện các tác vụ tính toán nặng hơn, nhu cầu về tốc độ xử lý ngày càng tăng, và việc tối ưu hóa các quy trình trở nên cần thiết. Khi chúng ta bỏ qua điều này (tối ưu hóa code của mình), chúng ta sẽ nhận được các chương trình tiêu tốn rất nhiều thời gian và sử dụng một khối tài nguyên hệ thống khủng khiếp trong quá trình thực thi.

Memoization là gì?

Memoization là một kỹ thuật tối ưu hóa, giúp tăng tốc các ứng dụng bằng cách lưu trữ kết quả của các lệnh gọi hàm (mà các hàm này được gọi là expensive function) và trả về kết quả được lưu trong bộ nhớ cache khi có cùng một đầu vào yêu cầu (đã được thực thi ít nhất 1 lần trước đó rồi).

expensive function là gì?

Đừng nhầm lẫn, chúng ta không có tiêu tiền ở đây. Trong bối cảnh của các chương trình máy tính, hai tài nguyên chính chúng ta có là thời gian và bộ nhớ. Do đó, một gọi hàm đắt tiền là gọi một hàm tiêu thụ khối lượng lớn của hai tài nguyên này trong khi thực hiện do tính toán nặng (code lởm hoặc yêu cầu phức tạp chẳng hạn).

Đối với điều này, momoization sử dụng bộ nhớ đệm để lưu trữ kết quả của các lần gọi hàm, để có thể truy cập nhanh chóng và dễ dàng sau này.

Bộ đệm chỉ đơn giản là một kho lưu trữ dữ liệu tạm thời chứa dữ liệu, để dữ liệu đó có thể được phục vụ nhanh hơn cho các yêu cầu trong tương lai.

Tại sao memoization lại cần thiết?

Chúng ta có 1 ví dụ như sau:

Hãy tưởng tượng bạn đang đọc một cuốn tiểu thuyết mới với bìa sách được trang trí khá là hấp dẫn tại công viên. Mỗi khi một người đi qua, họ bị thu hút bởi bìa cuốn sách, vì vậy họ hỏi tên của cuốn sách và tác giả của nó. Lần đầu tiên câu hỏi được đặt ra, bạn lật trang bìa, đọc tiêu đề và tên của tác giả. Bây giờ, ngày càng có nhiều người tiếp tục dừng lại và hỏi cùng một câu hỏi. Bạn là một người rất rất tốt, vì vậy bạn trả lời tất cả họ

=> Bạn có thể lật bìa, đọc tiêu đề và tên tác giả cho mỗi người trong số họ, hoặc bạn sẽ bắt đầu ghi nhớ thông tin và phản hồi lại họ bằng cái đầu (thay vì lật cái bìa để đọc =)) ) Giúp bạn tiết kiệm thời gian hơn? (mà vẫn làm 1 nice person :v)

Đây là một ví dụ do tác giả đặt ra, giả thiết có 1 anh chàng đọc sách mà không nhớ nổi tên sách và tên tác giả, nhưng thật ra là mình cũng thế, cuốn sách mình đọc lại nhiều lần nhất là Rừng Nauy, nhớ hết tên nhân vật nhưng lại không nhớ nổi tên tác giả, mình nói vậy là để chứng minh cái ví dụ của tác giả bài viết này không buồn cười lắm

Nhận thấy sự giống nhau chứ? Với tính năng memoization (ghi nhớ), khi một hàm được cung cấp đầu vào, nó sẽ thực hiện tính toán cần thiết và lưu kết quả vào bộ đệm trước khi trả về giá trị. Nếu cùng một đầu vào được nhận trong tương lai, nó sẽ không phải làm đi làm lại nhiều lần mà chỉ đơn giản là cung cấp kết quả từ bộ nhớ cache luôn.

Memoization làm việc như thế nào?

Khái niệm memoization trong JavaScript được xây dựng chủ yếu trên hai khái niệm:

• Closures
• Higher Order Functions (returning functions from functions)

Đoạn này tác giả giới thiệu khái niệm về scope, closure, return function nhưng khá là khó để hình dung cụ thể, vì cơ bản là mấy cái khái niệm này trong js cũng khá là lằng nhằng, thế nên là mình bê 1 vài đoạn của 1 bài viết khác, của 1 tác giả khác vào đây

• Scope là nơi mà biến hoặc hàm có thể truy cập vào và sử dụng/ tham chiếu được qua tên trực tiếp. Và ở ngoài scope đó thì biến hoặc hàm đó sẽ không thể nhìn được một cách trực tiếp nữa.
• Closure là một hàm hoặc một tham chiếu (hay còn gọi là một cái bao đóng) đi kèm với cái môi trường mà nó tham chiếu đến (khá là xoắn).

Như chúng ta vừa nói ở trên, scope là khái niệm qui định "visibility" và "lifetime" của variable. Thông thường, ví dụ như C thì scope sẽ là block scope, tức là những biến tạo ra trong block sẽ chỉ được nhìn thấy trong block đấy thôi, và khi ra ngoài block đấy thì những variable nằm trong block sẽ được giải phóng ( như trong C là các biến tạo ra trong stack sẽ được free khi ra khỏi block), và không nhìn thấy được nữa.

Tuy nhiên rất buồn là javascript của chúng ta lại không có cái scope dễ hiểu đến thế, mà nó lại là function block. Function block ở đây là gì: tức là những gì bạn tạo ra trong một function sẽ available ở trong function đó. Vì javascript cũng là block syntax, nên sẽ hơi dễ confusing, chúng ta sẽ dùng ví dụ dễ hiểu này:

function scope() {
  if (true) {
    var test = 1;
  }
  alert(test); #=> 1
}
scope();

Nói đến đây chắc chắn có bạn sẽ nghĩ đến điều gì xảy ra khi chúng ta có nested function. Let's try:

function outer() {
  var outer_var = 2;
  function inner() {
    alert(outer_var);
  }
  inner();
}
outer(); #=> 2

Từ ví dụ trên ta có thể dễ dàng thấy là inner function có thể access được outer function variable. Từ ví dụ này chúng ta có thể thấy là inner function có thể inherit biến của outer function, hay nói cách khác, inner function chứa(contain) scope của outer function.

A closure is an expression (typically a function) that can have free variables together with an environment that binds those variables (that "closes" the expression).

Chắc có bạn sẽ thắc mắc, environment ở đây là gì. Để hình dung một cách dễ hiểu, thì environment ở đây trong phần lớn các trường hợp chính là cái outer function mà chung ta vừa thử ở ví dụ về scope ở trên. Một đặc điểm rất hay của closure là closure sẽ giữ tham chiếu đến các biến nằm bên trong nó, hoặc được gọi đến bên trong nó. Điều này dẫn đến việc gì? Chắc sẽ có bạn nghĩ đến một trường hợp rất đặc biệt là khi bạn muốn context của một function được giữ lại sau khi hàm đó đã được execute xong . Hãy bắt đầu bằng một ví dụ:

function outside(x) {
  function inside(y) {
    return x + y;
  }
  return inside;
}
fn_inside = outside(3); 
result = fn_inside(5); // #=> 8

result1 = outside(3)(5); // #=> 8

Bạn có nhận thấy điều gì đặc biệt ở trên? Điều đặc biệt nằm ở hàm fn_inside : hàm fn_inside được tạo ra bởi kết quả trả về của hàm outside() với parameter là 3, và bạn có thể nhận thấy hàm fn_inside vẫn giữ tham chiếu đến cái parameter 3 đó ngay cả khi hàm outside() đã được execute xong. Chắc các bạn sẽ thấy mâu thuẫn với cái lý thuyết về function scope chúng ta đã nói đến ở trên, khi mà mọi thứ được tạo ra trong function của js chỉ nhìn thấy và sử dụng được ở trong đó, và sẽ được giải phóng hoặc không nhìn thấy khi ra ngoài function đó. Thực tế là không hề mâu thuẫn chút nào cả, chính vì cái gọi là closure của js . Nói một cách cụ thể hơn: fn_inside khi được tạo ra đã đồng thời cũng tạo ra một cái closure (bao đóng), trong cái bao đó, giá trị 3 được truyền vào, và cái bao của fn_inside sẽ vẫn giữ cái giá trị 3 đó cho dù outside() function có execute xong.

=> đây là mấu chốt vấn đề để chúng ta tìm hiểu thêm phần tiếp theo.

Đoạn trên được copy từ bài viết Closure và scope trong javascript

Case Study: dãy số Fibonacci

Dãy số Fibonacci là gì?

• là dãy số bắt đầu từ 0 hoặc 1, và các số tiếp theo chính là tổng của 2 số đứng kề phía trước nó.
• ví dụ:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
// hoặc
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Bài toán kinh điển là: viết hàm tìm số thứ n của dãy số.

Và đầu tiên chúng ta nghĩ ngay tới 1 hàm đệ quy:

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

Súc tích và rất chính xác! Nhưng, có một vấn đề. Lưu ý rằng trong việc giảm liên tục kích thước của bài toán (giá trị của n) cho đến khi đạt được trường hợp kết thúc, sẽ có rất nhiều công việc được thực hiện và mất thời gian để đi đến kết quả cuối cùng, vì có sự tính toán lặp đi lặp lại các giá trị nhất định trong chuỗi. Nhìn vào sơ đồ bên dưới, khi chúng ta cố gắng tính toán fibonacci(5), chúng ta liên tục tìm số Fibonacci tại các chỉ số 0, 1, 2 và 3 trên các nhánh khác nhau. Điều này được gọi là tính toán dư thừa và chính xác là những gì mà memoization loại bỏ.

Bây giờ chúng ta sẽ refactor lại code bằng memoization:

function fibonacci(n,memo) {
    memo = memo || {}
    if (memo[n]) {
        return memo[n]
    }
    if (n <= 1) {
        return 1
    }
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
}

Trong đoạn mã trên, chúng ta điều chỉnh hàm để chấp nhận một tham số tùy chọn được gọi là memo. Chúng ta sử dụng object memo làm bộ nhớ cache để lưu trữ các số Fibonacci với các chỉ số tương ứng của chúng làm khóa, để có thể lấy bất cứ khi nào chúng được yêu cầu trong những lần tính toán kế tiếp.

memo = memo || {}

Ở đây, chúng ta kiểm tra xem memo có được truyền vào hay không. Nếu có, chúng ta sẽ khởi tạo nó để sử dụng, nhưng nếu không, chúng ta sẽ đặt nó thành một object rỗng.

if (memo[n]) {
      return memo[n]
}

Tiếp theo, chúng ta kiểm tra xem có giá trị được lưu trong bộ nhớ cache cho khóa hiện tại n hay không? và trả về giá trị của nó nếu có. Như trong giải pháp trước đây, chúng ta chỉ định trường hợp kết thúc khi n nhỏ hơn hoặc bằng 1.

Cuối cùng, chúng ta gọi đệ quy hàm với giá trị n nhỏ hơn, trong khi đó thì chuyển các giá trị được lưu trong bộ nhớ cache (memo) vào từng hàm, để sử dụng trong quá trình tính toán. Điều này đảm bảo rằng khi giá trị đã được tính toán trước đó và được lưu trong bộ nhớ cache, chúng ta không thực hiện tính toán như vậy lần thứ hai. Chúng ta chỉ đơn giản là lấy giá trị từ bộ nhớ cache. Lưu ý rằng phải thêm kết quả cuối cùng vào bộ cache trước khi trả lại.

Có vẻ ổn rồi đấy, chúng ta thử tính toán kết quả và kiểm tra hiệu năng xem thế nào?

Testing hiệu năng với JSPerf

Đọc How does jsPerf work? để hiểu thêm về jsperf, ops/sec là số phép tính được thực hiện trong 1 giây.

Ở đây chúng ta thực hiện test hiệu năng với tính toán fibo(20)

Chúng ta có thể thấy rất rất là ấn tượng, khi đoạn code đệ quy thuần túy chỉ hoạt động được với tốc độ 1.751 ops/sec, chậm hơn hẳn 99% so với cách sử dụng memoization với 126.762 ops/sec.

Vậy thì để đạt được kết quả ấn tượng như vậy. chúng ta phải thêm bộ nhớ cache memo vào từng hàm, sửa chữa thay đổi chúng 1 chút để đạt được kết quả mong muốn? Không hẳn, chúng ta sẽ sử dụng cái đặc tính returning functions from functions mà đã được đề cập đến ở trên, để memoization bất cứ function nào chúng ta muốn.

A Functional Approach

Trong đoạn mã dưới đây, chúng ta tạo ra một hàm bậc cao hơn được gọi là memoizer. Với hàm này, chúng ta sẽ có thể dễ dàng áp dụng ghi nhớ memoization cho bất kỳ hàm nào khác:

function memoizer(fun) {
    let cache = {}
    return function (n) {
        if (cache[n] != undefined ) {
          return cache[n]
        } else {
          let result = fun(n)
          cache[n] = result
          return result
        }
    }
}

Ở trên, chúng ta chỉ cần tạo một hàm mới gọi là memoizer chấp nhận hàm fun làm tham số. Trong hàm, chúng ta tạo một đối tượng bộ đệm cache để lưu trữ kết quả thực thi hàm, sử dụng lại trong tương lai.

Từ hàm memoizer, chúng ta trả về một function mới có thể truy cập bộ đệm bất kể nó được thực thi ở đâu, do nguyên tắc bao đóng closure như đã thảo luận ở trên. Và tương tự như ví dụ trước, chúng ta tính toán và lưu lại kết quả vào bộ nhớ đệm cache trước khi trả về kết quả.

Testing memoizer function

Chúng ta so sánh kết quả của memoizer với các trường hợp trên, ta có:

Và cách xử lý của memoizer có tốc độ ~42 triệu ops/sec, nhanh hơn xấp xỉ 100% so với các cách khác. (okay)

Rất có thể máy của tác giả lởm, máy tính của mình cho kết quả lên tới 303 triệu ops/sec cơ, dưới đây là kết quả test trên máy của mình (tuy nhiên thì tỷ lệ giữa các cách xử lý vẫn xấp xỉ nhau thôi)

Nên sử dụng memoizer khi nào?

Đây là ba trường hợp trong đó việc memoization sẽ có lợi:

• Đối với các gọi hàm expensive function, tức là các hàm thực hiện các tính toán nặng.
• Đối với các hàm có phạm vi đầu vào hạn chế và định kỳ cao (highly recurring input range), sao cho các giá trị được lưu trong bộ nhớ cache không chỉ ở im đó mà còn không thay đổi gì cả.
• Đối với các hàm đệ quy với các giá trị đầu vào định kỳ (recurring input).
• Đối với các hàm thuần (pure functions), tức là các hàm trả về cùng một đầu ra mỗi lần chúng được gọi với một đầu vào cụ thể.

Thư viện sử dụng memoization

• Lodash Memoize
• Memoizer
• Fast Memoize
• Moize
• Reselect for Redux

Kết luận

• Sửa dụng memoization trong việc giải quyết các vấn đề của chúng ta sẽ tiết kiệm được (nhiều) thời gian và tài nguyên hệ thống.
• Nguồn bài viết Understanding Memoization In JavaScript.
• Tham khảo thêm các định nghĩa về scope, closure tại bài viết Closure và scope trong javascript.
• Link Memoization test tại jsperf.