Memoization là kỹ thuật dựa trên quy hoạch động (dynamic programming) dùng để cải thiện hiệu suất của thuật toán đệ quy bằng cách đảm bảo phương thức không chạy cho cùng một tập đầu vào nhiều hơn một lần, bằng cách lưu trữ kết quả cho các đầu vào đã cung cấp (lưu trong mảng). Memoization có thể đạt được bằng cách triển khai 접근 top-down của phương pháp đệ quy.
Hãy hiểu kịch bản này qua ví dụ cơ bản Fibonacci.
1-D Memoization
Chúng ta xét thuật toán đệ quy chỉ có một tham số không hằng (chỉ một tham số thay đổi giá trị) nên gọi là 1-D memoization. Đoạn code sau tìm số Fibonacci thứ N (tất cả các số hạng đến N).
Ví dụ: Fibonacci đệ quy không tối ưu
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("Calculating fibonacci number for: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
Đầu ra
Chạy với n=5 cho đầu ra:
Calculating fibonacci number for: 5 Calculating fibonacci number for: 4 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2 Calculating fibonacci number for: 2 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2
Giá trị Fibonacci cho n=5: 5
Nhận thấy Fibonacci cho 2 và 3 được tính nhiều hơn một lần. Hiểu rõ hơn bằng cây đệ quy cho n=5. Hai con của node đại diện cho lời gọi đệ quy. F(3) và F(2) tính lặp lại và có thể tránh bằng cách cache kết quả sau mỗi bước.
Ta dùng biến instance memoizeSet (HashMap) để cache kết quả. Trước hết kiểm tra n có trong memoizeSet không, nếu có trả về giá trị, nếu không tính toán và thêm vào set.
Ví dụ: Fibonacci có Memoization
import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
public int fibMemoize(int input) {
if (input == 0)
return 0;
if (input == 1)
return 1;
if (this.memoizeSet.containsKey(input)) {
System.out.println("Getting value from computed result for " + input);
return this.memoizeSet.get(input);
}
int result = fibMemoize(input - 1) + fibMemoize(input - 2);
System.out.println("Putting result in cache for " + input);
this.memoizeSet.put(input, result);
return result;
}
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("Calculating fibonacci number for: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
public static void main(String[] args) {
TutorialPoint tutorialPoint = new TutorialPoint();
System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
}
}
Đầu ra
Adding result in memoizeSet for 2 Adding result in memoizeSet for 3 Getting value from computed result for 2 Adding result in memoizeSet for 4 Getting value from computed result for 3 Adding result in memoizeSet for 5 Fibonacci value for n=5: 5
Như thấy, Fibonacci cho 2 và 3 không tính lại. HashMap memoizeSet lưu giá trị đã tính, trước mỗi lần tính Fibonacci kiểm tra trong set.
2-D Memoization
Chương trình trên chỉ có một tham số không hằng. Dưới đây là ví dụ chương trình đệ quy có hai tham số thay đổi giá trị sau mỗi lời gọi đệ quy, triển khai memoization trên hai tham số không hằng này. Đây gọi là 2-D Memoization.
Ví dụ: Triển khai bài toán Longest Common Subsequence (LCS) chuẩn. Nếu một tập hợp chuỗi cho trước, bài toán LCS là tìm chuỗi con chung dài nhất của tất cả chuỗi. Các tổ hợp khả thi là 2ⁿ.
Ví dụ: LCS đệ quy không tối ưu
class TP {
static int computeMax(int a, int b) {
return (a > b) ? a : b;
}
static int longestComSs(String X, String Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + longestComSs(X, Y, m - 1, n - 1);
else
return computeMax(longestComSs(X, Y, m, n - 1), longestComSs(X, Y, m - 1, n));
}
public static void main(String[] args) {
String word_1 = "AGGTAB";
String word_2 = "GXTXAYB";
System.out.print("Length of LCS is " + longestComSs(word_1, word_2, word_1.length(), word_2.length()));
}
}
Đầu ra
Length of LCS is 4
Trong cây đệ quy nửa trên, lcs("AXY", "AYZ") được giải quyết nhiều hơn một lần.
Do tính chất Overlapping Substructure, tính toán trước các sub-problem trùng lặp có thể tránh bằng Memoization hoặc Tabulation.
Cách tiếp cận Memoization của code đệ quy:
Ví dụ: LCS có Memoization (2-D)
import java.io.*;
import java.lang.*;
class testClass {
final static int maxSize = 1000;
public static int arr[][] = new int[maxSize][maxSize];
public static int calculatelcs(String str_1, String str_2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (arr[m - 1][n - 1] != -1)
return arr[m - 1][n - 1];
if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
return arr[m - 1][n - 1];
} else {
int a = calculatelcs(str_1, str_2, m, n - 1);
int b = calculatelcs(str_1, str_2, m - 1, n);
int max = (a > b) ? a : b;
arr[m - 1][n - 1] = max;
return max;
}
}
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
arr[i][j] = -1;
}
}
String str_1 = "AGGTAB";
String str_2 = "GXTXAYB";
System.out.println("Length of LCS is " + calculatelcs(str_1, str_2, str_1.length(), str_2.length()));
}
}
Đầu ra
Length of LCS is 4
Phân tích
Trong phương thức calculatelcs có 4 đối số, 2 hằng (không ảnh hưởng memoization) và 2 không hằng (m, n) thay đổi mỗi lời gọi đệ quy. Để memoization, ta đưa vào mảng 2-D lưu giá trị đã tính của lcs(m,n) tại arr[m-1][n-1]. Không thực hiện thêm lời gọi đệ quy, trả về arr[m-1][n-1] khi hàm với cùng m,n được gọi lại, vì tính toán trước đã lưu, giảm thiểu lời gọi đệ quy.
3-D Memoization
Đây là cách tiếp cận memoization cho chương trình đệ quy có 3 tham số không hằng. Ví dụ tính độ dài LCS cho ba chuỗi.
Cách tiếp cận: sinh tất cả các subsequence có thể (tổng 3ⁿ) cho các chuỗi cho trước và tìm subsequence chung dài nhất.
Ta đưa vào bảng 3-D để lưu giá trị đã tính. Xét các subsequence:
- A1[1...i], i < N
- A2[1...j], j < M
- A3[1...k], k < K
Nếu tìm thấy ký tự chung (X[i]==Y[j]==Z[k]) thì đệ quy phần còn lại. Ngược lại tính max của các trường hợp:
- Bỏ X[i] đệ quy phần khác
- Bỏ Y[j] đệ quy phần khác
- Bỏ Z[k] đệ quy phần khác
Công thức đệ quy:
f(N,M,K) = {
1 + f(N-1,M-1,K-1) nếu (X[N]==Y[M]==Z[K])
maximum(f(N-1,M,K), f(N,M-1,K), f(N,M,K-1)) ngược lại
}
- f(N-1,M,K) = Bỏ X[i] đệ quy phần khác
- f(N,M-1,K) = Bỏ Y[j] đệ quy phần khác
- f(N,M,K-1) = Bỏ Z[k] đệ quy phần khác
Ví dụ: LCS 3 chuỗi có Memoization (3-D)
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
public static int[][][] arr = new int[100][100][100];
static int calculatelcs(String str_1, String str_2, String str_3, int m, int n, int o) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
arr[i][j][0] = 0;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= o; j++) {
arr[0][i][j] = 0;
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= o; j++) {
arr[i][0][j] = 0;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= o; k++) {
if (str_1.charAt(i - 1) == str_2.charAt(j - 1) && str_2.charAt(j - 1) == str_3.charAt(k - 1)) {
arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
} else {
arr[i][j][k] = calculateMax(arr[i - 1][j][k], arr[i][j - 1][k], arr[i][j][k - 1]);
}
}
}
}
return arr[m][n][o];
}
static int calculateMax(int a, int b, int c) {
if (a > b && a > c)
return a;
if (b > c)
return b;
return c;
}
public static void main(String[] args) {
String str_1 = "clued";
String str_2 = "clueless";
String str_3 = "xcxclueing";
int m = str_1.length();
int n = str_2.length();
int o = str_3.length();
System.out.print("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
}
}
Đầu ra
Length of LCS is 4