Memoization vs Tabulation
Memoization vs Tabulation in DP
This is an article about the comparison between Memoization and Tabulation methods, especially about the famous coding problems of dynamic programming. Here we have discussed what is actually Memoization and what is tabulation, and then a comparative study between these two methods, the pros and the cons of both of them.
Memoization vs Tabulation | PrepInsta
What is Memoization?
Suppose we are solving a problem with Dynamic programming, using recursive function calling. Let’s say we are finding the fibonacci number of n. So, when we are finding the nth fibonacci number, we have to calculate the n-1th and n-2th fibonacci number. Similarly, when we need n+1th fibonacci numbers we need n and n-1th fibonacci numbers. So here we can see, the n-1th prime number will be calculated twice. And that is what we mean by overlapping subproblems.
So, If we want to reuse the value of Function (3), we have to store the value somewhere. Let us make an array or a hashmap to store the values. So everytime we recursively call Function (n), we store it in a lookup table, so that by any chance if we need the value once again, we will get it from there. So we add a hashmap, let’s say LookUP[n] and before returning the value we store it in that position. The value is now in the memory of the system. It is called Memoization.
Here with a code we have shown what happenes if you don’t do Memoization in the code of fibbonacci in compare to the iterative way of coding it..
#include <iostream>
using namespace std;
int Rec=0,It=0;
int Recursive_Fibonacci(int n)
{
Rec++;
if(n==0|n==1) return n;
int a=Recursive_Fibonacci(n-1)+Recursive_Fibonacci(n-2);
return a;
}
int Iterative_Fibonacci(int n)
{
int a=0,b=1,c;
for(int i=0;i<n-1;i++)
{
c=a+b;
a=b;
b=c;
It++;
}
return c;
}
int main()
{
cout<<"This is Now the 10th Fibonacci Number in Recursive way: ";
cout<<Recursive_Fibonacci(10);
cout<<"\nWith number of iterations: "<<Rec<<endl;
cout<<"\nThis is Now the 10th Fibonacci Number in Iterative way: ";
cout<<Iterative_Fibonacci(10);
cout<<"\nWith number of iterations: "<<It<<endl;
}Output
This is Now the 10th Fibonacci Number in Recursive way: 55 With number of iterations: 177 This is Now the 10th Fibonacci Number in Iterative way: 55 With number of iterations: 9
We go from the big values to the small values from the first call. When Function (n) is calling Function (n-1) and Function (n-2), The Function (n-1) gets in the stack and then Function (n-1) calls Function (n-2) and Function (n-3) and so on. When Function (n-1) returns for Function (n), the next is Function (n-2) but that is already present in the lookup table. So, the time complexity drastically changes, in this case it gets linear. It goes from bigger values to smaller values, that is why it is called Top-Down.
What is Tabulation?
Suppose we are solving the same problem with Dynamic programming, Fibonacci series. But here we are using a different algorithm, with a different direction. If we see, the first and second fibonacci numbers are 0 and 1. So, if we start storing the values in a container where we can look up to, and which can store the values of the nth fibonacci numbers to nth indexes or so, we can use n-1 th and n-2 th values to get n th values. That means, we are starting from the lowest values and going to the higher values, usually iteratively. This is why the method can be called Bottom Up, and this process of storing the previous smaller values to get higher ones is called Tabulation. Here unlike the memoization, making the look up table gets more priority.
The algorithm is simple, to get the values for lowest base cases, and then iterate the next values as the result for larger values depends on the lower ones, like in this case, value for n depends on value of n-1 and n-2.
#include <bits/stdc++.h>
using namespace std;
int Rec=0,It=0;
map<int,int> RecLookUp, ItLookUp;
int Recursive_Fibonacci(int n)
{
if(n==0|n==1) return RecLookUp[n]=n;
if(RecLookUp[n]) return RecLookUp[n];
Rec++;
return RecLookUp[n]=Recursive_Fibonacci(n-1)+Recursive_Fibonacci(n-2);
}
int Iterative_Fibonacci(int n)
{
ItLookUp[0]=0;
ItLookUp[1]=1;
for(int i=2;i<=n;i++)
{
ItLookUp[i]=ItLookUp[i-1]+ItLookUp[i-2];
It++;
}
return ItLookUp[n];
}
int main()
{
cout<<"This is Now the 10th Fibonacci Number in Recursive way: ";
cout<<Recursive_Fibonacci(10);
cout<<"\nWith number of iterations: "<<Rec<<endl;
cout<<"\nThis is Now the 10th Fibonacci Number in Iterative way: ";
cout<<Iterative_Fibonacci(10);
cout<<"\nWith number of iterations: "<<It<<endl;
}
Output
This is Now the 10th Fibonacci Number in Recursive way: 55 With number of iterations: 9 This is Now the 10th Fibonacci Number in Iterative way: 55 With number of iterations: 9
Memoization
Pros of Memoization:
- Memoization is greatly easy to interpret.
- The recursive function or enhanced recursive function can be easily written logically.
- And the base conditions can be given in the proper place before the recursive function calling can be easily comprehensible.
Cons of Memoization:
- Storing the values in the lookup table takes space, increasing space complexity.
- Also it is actually recursive function calling, for larger values and larger dimensions of dynamic programming problems it will increase stack occupancy exponentially resulting in segmentation faults or runtime errors.
Tabulation
Pros of Tabulation:
- Storing the values surely takes space, but no use of stack or other spaces.
- Also this is iterative and simple for machines and the time complexity also decreases for that. Also, for some kind of problems (Like this fibonacci problem too) we can just use a sliding pattern and do the whole problem in constant O(1) space.
Cons of Tabulation:
- Tabulation most of the time may get complicated to understand or implement logically.
- The logic of the code must be understood properly before trying to implement it.
- Also, tabulation completes calculation for all possible questions in the given ranges, including all overlapping subproblems. Now there may be possibilities where the time needed is more by this process than it can actually be done.
Login/Signup to comment