मेमोराइजेशन डायनामिक प्रोग्रामिंग पर आधारित एक तकनीक है जिसका उपयोग रिकर्सिव एल्गोरिदम के प्रदर्शन को बेहतर बनाने के लिए किया जाता है, यह सुनिश्चित करके कि मेथड दिए गए इनपुट्स के समान सेट के लिए एक से अधिक बार न चले, प्रदान किए गए इनपुट्स के परिणामों का रिकॉर्ड रखकर (एक ऐरे में संग्रहीत)। मेमोराइजेशन को रिकर्सिव मेथड के टॉप-डाउन दृष्टिकोण को लागू करके प्राप्त किया जा सकता है।
आइए इस परिदृश्य को बुनियादी फिबोनाची उदाहरण की मदद से समझते हैं।
1-D मेमोराइजेशन
हम केवल एक नॉन-कॉन्स्टेंट पैरामीटर वाले रिकर्सिव एल्गोरिदम पर विचार करेंगे (केवल एक पैरामीटर अपना मान बदलता है) इसलिए इस मेथड को 1-D मेमोराइजेशन कहा जाता है। निम्न कोड फिबोनाची श्रृंखला में Nवीं (N तक के सभी पद) को ढूंढने के लिए है।
उदाहरण
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("फिबोनाची संख्या की गणना कर रहे हैं: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
आउटपुट
यदि हम n=5 के साथ उपरोक्त कोड चलाते हैं, तो यह निम्न आउटपुट उत्पन्न करेगा।
फिबोनाची संख्या की गणना कर रहे हैं: 5 फिबोनाची संख्या की गणना कर रहे हैं: 4 फिबोनाची संख्या की गणना कर रहे हैं: 3 फिबोनाची संख्या की गणना कर रहे हैं: 2 फिबोनाची संख्या की गणना कर रहे हैं: 2 फिबोनाची संख्या की गणना कर रहे हैं: 3 फिबोनाची संख्या की गणना कर रहे हैं: 2
n=5 के लिए फिबोनाची मान: 5
ध्यान दिया गया कि 2 और 3 के लिए फिबोनाची संख्या एक से अधिक बार गणना की गई है। आइए n=5 के लिए उपरोक्त शर्त यानी फिबोनाची श्रृंखला के लिए एक रिकर्सिव ट्री बनाकर बेहतर ढंग से समझते हैं।
यहां नोड के दो बच्चे उसके द्वारा किए गए रिकर्सिव कॉल को दर्शाते हैं। जैसा कि देखा जा सकता है F(3) और F(2) एक से अधिक बार गणना किए गए हैं और प्रत्येक चरण के बाद परिणामों को कैश करके इससे बचा जा सकता है।
हम कैशिंग परिणाम के लिए एक इंस्टेंस वेरिएबल memoize Set का उपयोग करेंगे। पहले जांचा जाता है कि n पहले से ही memoize Set में मौजूद है या नहीं, यदि हां तो मान वापस कर दिया जाता है, और यदि नहीं तो मान की गणना की जाती है और सेट में जोड़ा जाता है।
उदाहरण
import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
private Map 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("गणना परिणाम से मान प्राप्त कर रहे हैं " + input);
return this.memoizeSet.get(input);
}
int result = fibMemoize(input - 1) + fibMemoize(input - 2);
System.out.println("कैश के लिए परिणाम डाल रहे हैं " + 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("फिबोनाची संख्या की गणना कर रहे हैं: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
public static void main(String[] args) {
TutorialPoint tutorialPoint = new TutorialPoint();
System.out.println("n=5 के लिए फिबोनाची मान: " + tutorialPoint.fibMemoize(5));
}
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
memoizeSet के लिए परिणाम जोड़ रहे हैं 2 memoizeSet के लिए परिणाम जोड़ रहे हैं 3 2 के लिए गणना परिणाम से मान प्राप्त कर रहे हैं memoizeSet के लिए परिणाम जोड़ रहे हैं 4 3 के लिए गणना परिणाम से मान प्राप्त कर रहे हैं memoizeSet के लिए परिणाम जोड़ रहे हैं 5
n=5 के लिए फिबोनाची मान: 5
जैसा कि देखा जा सकता है 2 और 3 के लिए फिबोनाची संख्या फिर से गणना नहीं की गई है। यहां हम एक HashMap memoizeSet पेश करते हैं जो उन मानों को संग्रहीत करता है जो पहले से गणना किए गए हैं। हर फिबोनाची गणना से पहले सेट में जांचा जाता है कि इनपुट के लिए मान गणना किया गया है या नहीं और यदि नहीं तो विशेष इनपुट के लिए मान सेट में जोड़ा जाता है।
2-D मेमोराइजेशन
उपरोक्त प्रोग्राम में हमारे पास केवल एक नॉन-कॉन्स्टेंट पैरामीटर था। नीचे दिए गए प्रोग्राम में हम एक रिकर्सिव प्रोग्राम का उदाहरण लेंगे जिसमें दो पैरामीटर हैं जो हर रिकर्सिव कॉल के बाद अपना मान बदलते हैं, और हम दो नॉन-कॉन्स्टेंट पैरामीटर्स पर मेमोराइजेशन लागू करके इसे ऑप्टिमाइज़ करेंगे। इसे 2-D मेमोराइजेशन कहा जाता है।
उदाहरण के लिए: हम मानक लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) लागू करने जा रहे हैं। यदि अनुक्रमों का एक सेट दिया जाता है, तो लॉन्गेस्ट कॉमन सबसीक्वेंस समस्या सभी अनुक्रमों के एक सामान्य सबसीक्वेंस को ढूंढना है जो अधिकतम लंबाई का हो। संभावित संयोजन 2^n होंगे।
उदाहरण
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("LCS की लंबाई है " + longestComSs(word_1, word_2, word_1.length(), word_2.length()));
}
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है
उपरोक्त आधे रिकर्सिव ट्री में, lcs("AXY", "AYZ") एक से अधिक बार हल किया गया है।
इस समस्या के ओवरलैपिंग सबस्ट्रक्चर गुण के परिणामस्वरूप, समान सब-प्रॉब्लम्स की पूर्व-गणना को मेमोराइजेशन या टेबुलेशन का उपयोग करके टाला जा सकता है।
रिकर्सिव कोड का मेमोराइजेशन दृष्टिकोण निम्नानुसार लागू किया गया है।
उदाहरण
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("LCS की लंबाई है " + calculatelcs(str_1, str_2, str_1.length(), str_2.length()));
}
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है
दृष्टिकोण
यह देखा गया है कि मेथड (calculatelcs) में 4 आर्गुमेंट्स हैं जिनमें 2 कॉन्स्टेंट (जो मेमोराइजेशन को प्रभावित नहीं करते) और 2 नॉन-कॉन्स्टेंट आर्गुमेंट्स (m और n) हैं जो हर रिकर्सिव मेथड कॉलिंग में अपना मान बदलते हैं। इसलिए मेमोराइजेशन प्राप्त करने के लिए हम एक 2-D ऐरे पेश करते हैं जो arr[m-1][n-1] पर lcs(m,n) के गणना किए गए मानों को संग्रहीत करता है। जब भी समान आर्गुमेंट्स m और n के साथ फ़ंक्शन को फिर से बुलाया जाता है तो हम कोई और रिकर्सिव कॉल नहीं करते और arr[m-1][n-1] वापस कर देते हैं, क्योंकि lcs(m, n) की पिछली गणना पहले से ही arr[m-1][n-1] में संग्रहीत की जा चुकी है, इस प्रकार रिकर्सिव कॉल्स की संख्या को कम किया जाता है।
3-D मेमोराइजेशन
यह 3 नॉन-कॉन्स्टेंट आर्गुमेंट्स वाले रिकर्सिव प्रोग्राम के लिए मेमोराइजेशन प्राप्त करने का एक दृष्टिकोण है। यहां हम तीन स्ट्रिंग्स के लिए LCS की लंबाई की गणना का उदाहरण ले रहे हैं।
यहां दृष्टिकोण दिए गए स्ट्रिंग्स के लिए सभी संभावित सबसीक्वेंस उत्पन्न करना है (कुल संभावित सबसीक्वेंस 3^n हैं) और उनमें से सबसे लंबे सामान्य सबसीक्वेंस से मिलान करना है।
हम गणना किए गए मानों को संग्रहीत करने के लिए एक 3-D टेबल पेश करेंगे। सबसीक्वेंस पर विचार करते हुए।
A1[1...i] i < N
A2[1...j] j < M
A3[1...k] 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) यदि (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(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("LCS की लंबाई है " + calculatelcs(str_1, str_2, str_3, m, n, o));
}
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है
