A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could involve the use of memoization, which stores calculated values so they don’t need to be recalculated later. He hadn’t dealt with memoization much, so I wrote up two little sampler programs to demonstrate the value it can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better since it wouldn’t require all those stack frames, but this is just to prove a point).
First, here is the non-memoized form:
#include <iostream>
class Fibber
{
private:
std::map<unsigned int, double> _fibs;
public:
double fib_of(unsigned int idx)
{
if(idx <= 2)
{
return 1;
}
return fib_of(idx - 1) + fib_of(idx - 2);
}
};
int main()
{
Fibber x;
for(int i = 1; i <= 100; i++)
{
std::cout << x.fib_of(i) << std::endl;
}
}
Now, if we take that same program but add memoization:
#include <iostream>
#include <map>
class Fibber
{
private:
std::map<unsigned int, double> _fibs;
public:
double fib_of(unsigned int idx)
{
if(idx <= 2)
{
return 1;
}
double ret = 0;
std::map<unsigned int, double>::iterator loc_iter = _fibs.find(idx);
if(loc_iter != _fibs.end())
{
ret = loc_iter->second;
}
else
{
double calculated = fib_of(idx - 1) + fib_of(idx - 2);
_fibs.insert(std::pair<unsigned int, double>(idx, calculated));
ret = calculated;
}
return ret;
}
};
int main()
{
Fibber x;
for(int i = 1; i <= 100; i++)
{
std::cout << x.fib_of(i) << std::endl;
}
}
The difference in performance between the two is night-and-day.
The non-memoized variety will slow to an unresponsive crawl in very short order, because it has to calculate all the values leading up to the current value, repeatedly for each value; it forgets all the interim values on the way.
The memoized version remembers the interim values, and therefor only calculates them once, storing each in the cache.