การท่องจำเป็นเทคนิคที่อิงจากการเขียนโปรแกรมแบบไดนามิกซึ่งใช้เพื่อปรับปรุงประสิทธิภาพของอัลกอริธึมแบบเรียกซ้ำ โดยทำให้แน่ใจว่าเมธอดจะไม่ทำงานสำหรับอินพุตชุดเดียวกันมากกว่าหนึ่งครั้งโดยเก็บบันทึกผลลัพธ์สำหรับอินพุตที่ให้มา (เก็บไว้ใน อาร์เรย์) การท่องจำสามารถทำได้โดยใช้วิธีการแบบเรียกซ้ำจากบนลงล่าง
ให้เราเข้าใจสถานการณ์นี้ด้วยความช่วยเหลือของตัวอย่างฟีโบนักชีพื้นฐาน
การท่องจำ 1 มิติ
เราจะพิจารณาอัลกอริธึมแบบเรียกซ้ำที่มีพารามิเตอร์ไม่คงที่เพียงตัวเดียว (พารามิเตอร์เดียวเท่านั้นที่เปลี่ยนค่าของมัน) ดังนั้นวิธีนี้จึงเรียกว่าการท่องจำ 1 มิติ รหัสต่อไปนี้คือการหา N’th (เงื่อนไขทั้งหมดจนถึง N) ในอนุกรมฟีโบนักชี
ตัวอย่าง
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));
} ผลลัพธ์
หากเราเรียกใช้โค้ดด้านบนด้วย n=5 มันจะสร้างผลลัพธ์ต่อไปนี้
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
ค่าฟีโบนักชีสำหรับ n=5:5
จะสังเกตว่าตัวเลขฟีโบนักชีสำหรับ 2 และ 3 ถูกคำนวณมากกว่าหนึ่งครั้ง ให้เราเข้าใจมากขึ้นโดยการวาดแผนภูมิแบบเรียกซ้ำสำหรับชุดฟีโบนักชีของเงื่อนไขข้างต้น นั่นคือ n=5
ที่นี่ลูกสองคนของโหนดจะเป็นตัวแทนของการเรียกแบบเรียกซ้ำ อย่างที่เห็น F(3) และ F(2) มีการคำนวณมากกว่าหนึ่งครั้งและสามารถหลีกเลี่ยงได้ด้วยการแคชผลลัพธ์หลังจากแต่ละขั้นตอน
เราจะใช้ตัวแปรอินสแตนซ์ memoize Set สำหรับการแคชผลลัพธ์ โดยจะมีการตรวจสอบก่อนว่ามี n อยู่ในชุด memoize หรือไม่ ถ้าใช่ ค่าจะถูกส่งคืน และถ้าไม่ใช่ค่าจะถูกคำนวณและเพิ่มลงในชุด
ตัวอย่าง
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));
}
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
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
ค่าฟีโบนักชีสำหรับ n=5:5
ดังจะเห็นได้ว่าเลข Fibonacci สำหรับ 2 และ 3 จะไม่ถูกคำนวณอีก ในที่นี้ เราขอแนะนำ HashMap ที่จดจำเพื่อเก็บค่าที่คำนวณไว้แล้วก่อนการคำนวณ Fibonacci ทุกครั้งจะได้รับการตรวจสอบในชุดหากสำหรับอินพุต ค่าที่ได้รับคำนวณแล้ว และหากไม่ใช่ค่าสำหรับอินพุตเฉพาะจะถูกเพิ่มเข้าไปในชุด
การท่องจำ 2 มิติ
โปรแกรมข้างต้นเรามีพารามิเตอร์ไม่คงที่เพียงตัวเดียว ในโปรแกรมด้านล่าง เราจะยกตัวอย่างของโปรแกรมแบบเรียกซ้ำที่มีพารามิเตอร์สองตัวซึ่งจะเปลี่ยนค่าของมันหลังจากการเรียกซ้ำทุกครั้ง และเราจะใช้การท่องจำกับพารามิเตอร์ที่ไม่คงที่สองตัวเพื่อปรับให้เหมาะสม สิ่งนี้เรียกว่าการท่องจำ 2 มิติ
ตัวอย่างเช่น:- เราจะใช้ลำดับรองร่วมที่ยาวที่สุดมาตรฐาน(LCS) . หากกำหนดชุดของลำดับไว้ ปัญหาของลำดับย่อยทั่วไปที่ยาวที่สุดคือการค้นหาลำดับย่อยร่วมของลำดับทั้งหมดที่มีความยาวสูงสุด ชุดค่าผสมที่เป็นไปได้จะเป็น 2n
ตัวอย่าง
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()));
}
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
Length of LCS is 4
ในแผนผังการเรียกซ้ำครึ่งทางด้านบน lcs("AXY", "AYZ") จะได้รับการแก้ไขมากกว่าหนึ่งครั้ง
เนื่องด้วยคุณสมบัติ Overlapping Substructure ของปัญหานี้ ทำให้สามารถหลีกเลี่ยงการคำนวณล่วงหน้าของปัญหาย่อยเดียวกันได้โดยใช้ Memorization หรือ Tabulation
วิธีการท่องจำของโค้ดแบบเรียกซ้ำมีการใช้งานดังนี้
ตัวอย่าง
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 arr[m - 1][n - 1];
}
}
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()));
}
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
Length of LCS is 4
แนวทาง
จะเห็นได้ว่าใน method(calculatelcs) มี 4 อาร์กิวเมนต์ที่มีค่าคงที่ 2 ตัว (ซึ่งไม่มีผลกับการท่องจำ) และอาร์กิวเมนต์ที่ไม่คงที่ 2 อาร์กิวเมนต์ (m และ n) ซึ่งเปลี่ยนค่าในการเรียกวิธีการแบบเรียกซ้ำทุกรายการ ดังนั้นเพื่อให้เกิดการท่องจำ เราจึงแนะนำอาร์เรย์ 2 มิติเพื่อเก็บค่าที่คำนวณได้ของ lcs(m,n) ที่ arr[m-1][n-1] เราไม่ทำการเรียกซ้ำอีกต่อไปและส่งคืน arr[m-1][n-1] เมื่อใดก็ตามที่มีการเรียกฟังก์ชันที่มีอาร์กิวเมนต์เดียวกัน m และ n อีกครั้ง เนื่องจากการคำนวณก่อนหน้าของ lcs(m, n) ได้เกิดขึ้นแล้ว เก็บไว้ใน arr[m-1][n-1] ซึ่งช่วยลดจำนวนการโทรซ้ำ
การท่องจำ 3 มิติ
นี่เป็นแนวทางเพื่อให้เกิดการท่องจำสำหรับโปรแกรมแบบเรียกซ้ำซึ่งมีอาร์กิวเมนต์ที่ไม่คงที่ 3 อาร์กิวเมนต์ ต่อไปนี้คือตัวอย่างการคำนวณความยาวของ LCS สำหรับสามสตริง
แนวทางที่นี่คือการสร้างลำดับย่อยที่เป็นไปได้ทั้งหมด (ลำดับย่อยที่เป็นไปได้ทั้งหมดคือ 3ⁿ) สำหรับสตริงที่กำหนดและจับคู่สำหรับลำดับย่อยทั่วไปที่ยาวที่สุดในบรรดาสตริงเหล่านั้น
เราจะมาแนะนำตารางสามมิติเพื่อเก็บค่าที่คำนวณได้ พิจารณาตอนต่อไป
-
A1[1...i] ฉัน
-
A2[1...j] j
-
A3[1...k] k
หากเราพบอักขระทั่วไป (X[i]==Y[j]==Z[k]) เราจำเป็นต้องเรียกอักขระที่เหลือซ้ำ มิฉะนั้น เราจะคำนวณค่าสูงสุดของกรณีต่อไปนี้
-
ปล่อยให้ X[i] เกิดขึ้นซ้ำสำหรับผู้อื่น
-
ปล่อยให้ Y[j] เกิดขึ้นซ้ำสำหรับผู้อื่น
-
ปล่อยให้ Z[k] เกิดขึ้นซ้ำสำหรับผู้อื่น
ดังนั้น หากเรากำหนดแนวคิดข้างต้นในฟังก์ชันเรียกซ้ำของเราแล้ว
f(N,M,K)={1+f(N-1,M-1,K-1)if (X[N]==Y[M]==Z[K]สูงสุด(f(N-) 1,M,K),f(N,M-1,K),f(N,M,K-1))}
-
f(N-1,M,K) =ปล่อยให้ X[i] เกิดขึ้นซ้ำสำหรับผู้อื่น
-
f(N,M-1,K) =ปล่อยให้ Y[j] เป็นกิจวัตรสำหรับคนอื่น
-
f(N,M,K-1) =ปล่อยให้ Z[k] เกิดซ้ำสำหรับผู้อื่น
ตัวอย่าง
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(j1) == 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));
}
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
Length of LCS is 4
