Home > memoization

Memoization

A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could relate to memoization, which stored calculated values with the intent of not needing to recalculate them later. He had never heard of memoization, so I wrote up two little sampler programs to demonstrate the value that memoization can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better, 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;
            }
            else
            {
                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;
            }
            else
            {
                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. Try it out!

Posted: January 6th, 2011 | Author: | Filed under: benlakey.com | Tags: , , | No Comments »