মেমোইজেশন (Memoization) হলো ডাইনামিক প্রোগ্রামিংয়ের ভিত্তিতে একটি টেকনিক যা রিকার্সিভ অ্যালগরिदমের পারফরম্যান্স উন্নত করতে ব্যবহৃত হয়। এটি নিশ্চিত করে যে একই ইনপুট সেটের জন্য মেথডটি একবার से বেশি রান না করে, ইনপুটের জন্য ফলাফল রাখে (এরে তে স্টোর করে)। মেমোইজেশন রিকার্সিভ মেথডের টপ-ডাউন অ্যাপ্রোচ বাস্তবায়ন করে অর্জন করা যায়।
বেসিক ফিবোনাচ্চি উদাহরণ দিয়ে এই পরিস্থিতি বুঝি:
১-D মেমোইজেশন
আমরা একটি রিকার্সিভ অ্যালগরিদম বিবেচনা করব যেটিতে শুধু একটি নন-কনস্ট্যান্ট প্যারামিটার আছে (শুধু একটি প্যারামিটার তার মান বদলায়), তাই এই মেথডটিকে ১-D মেমোইজেশন বলা হয়। নিচের কোডটি N-তম (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
লক্ষ্য করা যায় ২ এবং ৩-এর জন্য ফিবোনাচ্চি সংখ্যা একাধিকবার গণনা হয়েছে। রিকার্সিভ ট্রি আঁকায় ভালো বুঝা যাবে। n=5-এর জন্য ফিবোনাচ্চি সিরিজের রিকার্সিভ ট্রি:
এখানে প্রতিটি নোডের দুটি চাইল্ড রিকার্সিভ কলকে প্রকাশ করে। দেখা যাচ্ছে F(3) এবং F(2) একাধিকবার গণনা হয়েছে যা ক্যাশিং (caching) দিয়ে এড়ানো যায়।
আমরা একটি ইনস্ট্যান্স ভেরিয়েবল 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("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
দেখা যাচ্ছে ২ এবং ৩-এর জন্য ফিবোনাচ্চি সংখ্যা আবার গণনা হয়নি। এখানে আমরা একটি HashMap memoizeSet শুর করেছি যেটি ইতিমধ্যে কম্পিউট করা মানগুলো স্টোর করে। প্রতিটি ফিবোনাচ্চি ক্যালকুলেশনের আগে সেটে চেক করা হয় ইনপুটের জন্য মান কি ইতিমধ্যে কম্পিউট হয়েছে, না হলে সেটি সেটে যোগ করা হয়।
২-D মেমোইজেশন
উপরের প্রোগ্রামে আমাদের শুধু একটি নন-কনস্ট্যান্ট প্যারামিটার ছিল। নিচের প্রোগ্রামে আমরা একটি রিকার্সিভ প্রোগ্রামের উদাহরণ নিব যেটিতে দুটি প্যারামিটার থাকে যেগুলোর মান প্রতিটি রিকার্সিভ কলের পর বদলায়, এবং আমরা দুটি নন-কনস্ট্যান্ট প্যারামিটারে মেমোইজেশন বাস্তবায়ন করব অপ্টিমাইজ করতে। এটাকে ২-D মেমোইজেশন বলা হয়।
উদাহরণস্বরূপ: আমরা স্ট্যান্ডার্ড Longest Common Subsequence (LCS) বাস্তবায়ন করব। যদি কিছু সিকোয়েন্স দেওয়া থাকে, লংগেস্ট কমন সাবসিকোয়েন্স সমস্যা হলো সবচেয়ে বড় দৈর্ঘ্যের একটি কমন সাবসিকোয়েন্স খুঁজে বের করা। সম্ভাব্য কম্বিনেশন হবে 2ⁿ।
উদাহরণ
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 প্রোপার্টি থাকার কারণে, একই সাব-প্রব্লেমের পূর্ব-গণনা (pre-computation) মেমোইজেশন বা ট্যাবুলেশন দিয়ে এড়ানো যায়।
রিকার্সিভ কোডের মেমোইজেশন অ্যাপ্রোচ নিচে দেওয়া হলো:
উদাহরণ
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
অ্যাপ্রোচ
দেখা যাচ্ছে মেথড (calculatelcs)-এ ৪টি আর্গুমেন্ট আছে যার ২টি কনস্ট্যান্ট (যে মেমোইজেশনকে প্রভাবিত করে না) এবং ২টি নন-কনস্ট্যান্ট আর্গুমেন্ট (m এবং n) যেগুলোর মান প্রতিটি রিকার্সিভ মেথড কলের সময় বদলায়। তাই মেমোইজেশন অর্জন করতে আমরা একটি ২-D অ্যারে শুরু করি যেটি lcs(m,n) এর কম্পিউটেড মান arr[m-1][n-1]-এ স্টোর করে। আমরা আর কোনো রিকার্সিভ কল করি না এবং arr[m-1][n-1] রিটার্ন করি যখন একই আর্গুমেন্ট m এবং n দিয়ে ফাংশন কল হয়, কারণ lcs(m, n) এর পূর্বের কম্পিউটেশন ইতিমধ্যে arr[m-1][n-1]-এ স্টোর করা থাকছে, যাতে রিকার্সিভ কলের সংখ্যা কমিয়ে যায়।
৩-D মেমোইজেশন
এটি একটি অপ্রোচ ৩টি নন-কনস্ট্যান্ট আর্গুমেন্ট থাকা রিকার্সিভ প্রোগ্রামের জন্য মেমোইজেশন অর্জন করতে। এখানে আমরা তিনটি স্ট্রিং-এর LCS দৈর্ঘ্য কম্পিউট করার উদাহরণ নিচ্ছি।
এখানে অ্যাপ্রóch হলো দেওয়া স্ট্রিংগুলো için সব সম্ভাব্য সাবসিকোয়েন্স জেনারেট করা (মোট সম্ভাব্য সাবসিকোয়েন্স 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) if (X[N]==Y[M]==Z[K]) maximum(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("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
}
}
আউটপুট
যদি উপরের কোড রান করি তবে নিচের আউটপুট জেনারেট হবে:
Length of LCS is 4
