What is Memoization?
Memoization is a programming technique used to speed up calculations and prevent a program from reworking the same sub-problems repeatedly. It’s like caching. When memoizing, you store the results of past operations in a structure where they can be retrieved very quickly. For example, if you were to implement some code to find numbers in the Fibonacci sequence recursively then your function will likely do the same math over and over until it finds the Fibonacci number you specified.
Here’s some recursive java code to find the nth Fibonacci number:
public class Main {
//In the Fibonacci sequence, each number is the sum of the two preceding ones, starting from 0 and 1.
//The next number is found by adding up the two numbers before it.
public static void main(String[] args) {
int nthFibNum = 2;
System.out.println("The fibonacci number at index "+nthFibNum+" is: "+fib(nthFibNum));
}
public static int fib(int n){
if(n == 0 || n == 1){ //these are the smallest numbers in the fibonacci sequence
return n;
}
System.out.println("current n, inside fib method: "+n);
System.out.println();
return fib(n-1)+fib(n-2);
}
}
The rework happens in the recursive calls to find the first few numbers in the sequence. If you run the code above for the 2nd Fibonacci number then you won’t see any rework. Your output would look like this:
current n, inside fib method: 2 The fibonacci number at index 2 is: 1
However, if you run the code above for the 4th number in the sequence then you’ll start to see the rework displayed on the console like this:
current n, inside fib method: 4 current n, inside fib method: 3 current n, inside fib method: 2 current n, inside fib method: 2 The fibonacci number at index 4 is: 3
The number ‘2’ appears twice because it’s calculated in recursive calls for 3 and 2. Why 3 and 2? In the first call to the method, n=4. Once we hit the return statement the math shakes out like this: 4-1 = 3 and 4-2 = 2. The fib method is called again on 3 and 2. The calculation branches from there until you’re adding 1’s and 0’s.
When would you use it?
You would use memoization to simplify the situation above and prevent the exponential growth of rework. Preventing the rework makes your code run much faster as well. When memoizing you’re preventing the branching from happening by recording the results of each recursive call you haven’t already seen. So the next time a call happens in a branch with args that your code has already seen, your code remembers and uses the past results instead of calculating them again. By “remembers” I mean that your code stores the results of the previous calls in a data structure like a map (using n as a key) and then checks the map before each recursive call (potential branch).
Here’s the same code but memoized:
import java.util.HashMap;
public class Main {
//In the Fibonacci sequence, each number is the sum of the two preceding ones, starting from 0 and 1.
//The next number is found by adding up the two numbers before it.
static HashMap memo = new HashMap();
public static void main(String[] args) {
int nthFibNum = 4;
System.out.println("The fibonacci number at index "+nthFibNum+" is: "+fib(nthFibNum));
}
public static int fib(int n){
if(n == 0 || n == 1){ //these are the smallest numbers in the fibonacci sequence
return n;
}
if(memo.containsKey(n)){ //Here we check if we've seen this before
return memo.get(n); //returning here prevents additional branches
}
System.out.println("current n, inside fib method: "+n);
System.out.println();
int result = fib(n-1)+fib(n-2); //Here we find the result
memo.put(n, result);//Here we store it in memory.
return result;
}
}
If you were to run this code you would see output to the console like this:
current n, inside fib method: 4 current n, inside fib method: 3 current n, inside fib method: 2 The fibonacci number at index 4 is: 3
You should notice that the ‘2’ only appears once. By memoizing we have prevented rework.
Why is it valuable?
The immediate value to you is that it makes your code faster. The value to a business is that fast code saves time and computing resources. To a business, time = money and computing resources = money. If your code is fast then you are worth more money to businesses.