Fibonacci Memoization
In this age its important for developers to understand the use of caching tools and no-sql databases to performance scale your applications.
One such technique is a simple little idea called “memoization” — which is a heuristic of remembering the result of a previous calculation in a recursive methodology so the calculation doesn’t have to be executed again.
Here’s little recursive Fibonacci algorithm that doesn’t use memoization (in my case the strategy is a simple HashMap cache). I ran the sequence to 40 levels.
Non-cached
Run time: 88.60717 seconds
public BigInteger fibCalc(int calcLevel) {
if (calcLevel%10 == 0) {System.out.println("Calculation Level: " + calcLevel);}
if (calcLevel == 1) {
return bi(0);
} else if (calcLevel == 2 || calcLevel == 3) {;
return bi(1);
} else {
BigInteger rtrn = fibCalc(calcLevel-1).add(fibCalc(calcLevel - 2));
return rtrn;
}
}
Cached-Memoization
Run time: 0.00204 seconds
public HashMap<Integer,BigInteger> memoization = new HashMap<Integer,BigInteger>();
public BigInteger fibCalc(int calcLevel) {
if(null != memoization.get(calcLevel)) {
return memoization.get(calcLevel);
} else {
if (calcLevel%10 == 0) {System.out.println("Calculation Level: " + calcLevel);}
if (calcLevel == 1) {
memoization.put(calcLevel,bi(0));
return bi(0);
} else if (calcLevel == 2 || calcLevel == 3) {
memoization.put(calcLevel,bi(1));
return bi(1);
} else {
BigInteger rtrn = fibCalc(calcLevel-1).add(fibCalc(calcLevel - 2));
memoization.put(calcLevel,rtrn);
return rtrn;
}
}
Wow! What a difference. From about 89 seconds to *almost nothing*!!!
On different job sites the architects have always investigated larger caching strategies, but this goes to show you a little ole developer can take a programming idea and leverage it for good. Of course, it should be a reasonable application . . . .