Kỹ thuật Memoization trong Javascript

Memoization là một kỹ thuật giúp bạn cải thiện đáng kể tốc độ ứng dụng của bạn.

Nó không phải là một kỹ thuật dành riêng cho Javascript, tuy nhiên tiêu đề bài viết là “trong Javascript” vì tôi sẽ lấy một vài ví dụ bằng ngôn ngữ JS.

Memoization cơ bản

Memoization là một kỹ thuật lập trình, mục đích là làm tăng hiệu suất của một hàm bằng cách lưu trữ (caching) lại những kết quả đã được tính toán trước đó.

Object trong Javascript hoạt động giống như một mảng liên kết (key – value), đây là một ứng cử viên sáng giá cho việc ứng dụng một Object JS như một bộ nhớ đệm – cache.

Một function được áp dụng memoization, khi nó được gọi thì các tham số của nó sẽ được áp dụng để lập các chỉ mục cho bộ đệm. Nếu dữ liệu đã tồn tại trong bộ đệm, thì kết quả sẽ được trả về ngay lập tức thay vì thực hiện toàn bộ function. Tất nhiên, nếu kết quả chưa có trong bộ đệm, thì hàm sẽ được thực thi để lấy kết quả và kết quả đó sẽ được lưu vào bộ đệm.

Điều này có ý nghĩa rất lớn, hãy tưởng tượng bạn có một function, mỗi lần được gọi nó sẽ mất 1 giây để trả về kết quả, nhưng nếu được gọi lại một lần nữa với cùng tham số, nó sẽ chỉ mất 2 ms để trả về kết quả. 😀

Chúng ta sẽ làm một ví dụ, hàm tính giá trị giai thừa của một số tự nhiên (factorial) có sử dụng kỹ thuật memoization. Trong ví dụ, chúng ta sẽ sử dụng immediate function, function này trả lại một function khác (f), function f sẽ được sử dụng để tính giai thừa của một số. Khi function f() được trả về, tính chất closure trong JS vẫn cho phép hàm này truy cập tới đối tượng memo, đối tượng này chứa tất cả các kết quả của function f() đã thực hiện trước đó. Mỗi lần f() được gọi, đầu tiên nó sẽ kiểm tra xem đã tồn tại kết quả trả về  cho giá trị n (tham số tuyền vào). Nếu kết quả có tồn tại thì kết quả được lưu trữ trong memo  sẽ được trả lại, nếu không đoạn code tính giai thừa của một số sẽ được thực thi.

Chú ý: Đối tượng memo  được định nghĩa bên ngoài hàm f() để nó có thể lưu trữ giá trị qua nhiều lần gọi hàm.

Xử lý trường hợp hàm có nhiều tham số

Ở phần trước, function của chúng ta chỉ có một tham số – n. Điều này giúp cho việc triển khai kỹ thuật memoization khá đơn giản. Nhưng cuộc sống không dễ dàng như vậy, hầu hết các function đều có chiều hơn 1 tham số, điều này làm cho việc đánh index của bộ nhớ đêm cache trong kỹ thuật memoization trở nên khó khăn đôi chút.

Để thực hiện kỹ thuật memoization với function có nhiều tham số, bộ nhớ đệm cache của chúng ta sẽ có thể sẽ là một mảng liên kết nhiều chiều, hoặc tìm cách kết hợp các tham số của function để tạo thành một chỉ mục duy nhất cho cache.

Với cách sử dụng mảng liên kết nhiều chiều, bộ nhớ cache sẽ trở thành một hệ thống phân cấp của object thay vì một object đơn lẻ. Mỗi chiều sẽ được đánh chỉ mục bởi một tham số. Chúng ta sẽ nói tới ví dụ cache là một mảng nhiều chiều, áp dụng với function factorial(). Trong ví dụ này, factorial() sẽ nhận thêm một tham số – “x”, tham số này không “không để làm gì cả”. Mỗi lần hàm được gọi, trong code chúng ta sẽ kiểm tra xem “x” có tồn tại trong cache hay chưa, nếu chưa thì khởi tạo nó là một đối tượng “rỗng”. Từ đó chiều “x” của cache được sử dụng để lưu trữ các kết quả của hàm với tham số “n”. Kết quả là khi gọi factorial(“xbox”, 3) và factorial(“ps4”, 3) không được coi là kết quả tương tự.

Để thay thế cho việc phải thiết kế bộ nhớ đệm cache nhiều chiều, chúng ta có thể sử dụng một đối tượng cache với chỉ số là sự kết hợp của tất cả các tham số của function. Ví dụ được trình bày dưới đây mô tả việc chuyển đổi đối tượng arguments thành một array và sử dụng mảng đó làm chỉ số cho bộ nhớ đệm cache. Mỗi function trong JS luôn có một đối tượng build-in là “arguments”, đối tượng này chứa tất cả các tham số truyền vào khi gọi hàm. Một “arguments” có kiểu giống như một đối tượng array. Đối tượng này giống như một Array, nhưng lại không thể dùng để làm chỉ số cho bộ nhớ đệm. Chính vì thế, việc đầu tiên chúng ta phải làm là chuyển đối tượng này thành một array thực sự. Chúng ta có thể thực hiện việc này bằng phương thức slice() của array (có nhiều cách khác để thực hiện việc này).

Chú ý: Chúng ta có thêm một biến – “slice”, biến được định nghĩa để ánh xạ tới phương thức slice của Array, bằng việc tạo ra biến này chúng ta tránh được việc hàm liên tục gọi tới phương thức Array.prototype.slice . Phương thức call() được sử dụng để phương thức slice() áp dụng lên đối tượng “arguments”.

Tham số là một Object

Tất cả các cách được trình bày ở trên không thể áp dụng khi các tham số truyền vào là một hoặc nhiều object. Khi một object được sử dụng làm chỉ số cho bộ nhớ đệm, đầu tiên hệ thống sẽ chuyển object đó thành string bằng các sử dụng phương thức toString(), string nhận được của mọi object sẽ là “[object Object]”. Đó là lý do nhiều object khác nhau đều trỏ tới một giá trị tương tự trên bộ nhớ đệm. Vấn đề này có thể được sửa bằng cách “chuỗi hóa” các tham số object để làm chỉ số cho bộ nhớ đệm. Nhưng thực hiện việc này có thể làm giảm hiệu năng function của bạn đi một chút. Ví dụ dưới đây mô tả chung cho việc tạo ra một memoization function với tham số là object.

Memoization hóa các function

Ở tất cả các ví dụ trên, các function đã phải sửa lại nội dung để có thể áp dụng memoization. Chúng ta có cách để triển khai memoization mà không phải thay đổi nội dung code của các function. Điều này cực kỳ hữu ích, nó cho phép phần logic của function độc lập với phần memoization code. Việc này được thực hiện bằng các tạo ra một function, function này sẽ nhận một function làm input và áp dụng memoization cho function đó.

Function memoize() sẽ nhận nhận vào một function – “func”, hàm này trả lại một function, function mới có  cấu trúc caching bao quanh hàm “func”.

Chú ý: Hàm này không xử lý các hàm có tham số là đối tượng. Để xử lý loại này có thể các bạn cần một vòng lặp để xử lý từng tham số và chuyển chúng thành một string duy nhất đại diện cho các tham số.

Giới hạn

Với những công việc có tính chất đặc biệt, như truy vấn dữ liệu trong cơ sở dữ liệu, truy vấn tới các dịch vụ khác bằng http request, đọc file hay những hàm “không thuần thúy” có thể không được tối ưu bằng kỹ thuật memoization. Vì thế với những loại công việc đặc trưng, bạn cần tìm cách khác để tối ưu hóa chúng. Hoặc phải chấp nhận sự “kém hiệu quả” của những hàm kiểu này, đôi khi điều này không thể tránh khỏi.