Hi folks

I was on topcoder and came across an interesting problem...

It involved dynamic programming ( storing function results in a map to

avoid repeated computation ) and I ended up having to write 3 functions

that looked pretty much the same, so I thought- "Why not template - ize

the whole thing" and ended up with a generic Memoizer template, which

can be used to memoize any recursive function whose result depends on

multiple recursive invocations of itself.

Most basic case of such a fn is fibonacci

int fib(int n)

{

return n < 2 ? n : fib(n-1) + fib(n -2);

}

this highly stack consuming function will take eternity to compute

fib(50)

a standard memoization would be like

#include <map>

using std::map;

map<int, intfib_memo;

int fibm(int n)

{

map<int,int>::iterator fi = fib_memo.find(n);

if(fi == fib_memo.end())

{

return (fib_memo[n] = fibm(n - 1) + fibm(n - 2));

}

else

return fi->second;

}

but its tedious to do this for every function... what i came up with

lets u express the core computation clearly in the form of helper

classes and get the template class to memoize it for you automatically

thusly :

// define 3 classes needed by the template

class FibCalc

{

public:

void apply(int a, pair<bool, int>& ret)

{

ret.first = a < 2; // fib 0 , 1 =0, 1

ret.second = a;

}

};

class FibGetNextIterArgs

{

public:

void apply(int arg, vector<int>& rets)

{

rets.push_back(arg - 1);

rets.push_back(arg - 2);

}

};

class FibCalcNextIter

{

public:

int apply(vector<int>& rets)

{

return rets[0] + rets[1];

}

};

and call it like this:

Memoize<int, int, FibCalc, FibGetNextIterArgs, FibCalcNextIterfibo;

int i = 1000;

cout << fibo.apply(i);

the Memoize definition is below:

template<typename RET, typename ARG, class CALC, class GETNEXTITERARGS,

class CALCNEXTITER>

class Memoize

{

public:

CALC m_Calc;

GETNEXTITERARGS m_NextIterArgs;

CALCNEXTITER m_CalcNextIter;

map<ARG, RETm_Memo;

RET apply(ARG &a)

{

pair<bool, RETr;

m_Calc.apply(a, r);

if(r.first)

return (m_Memo[a] = r.second);

map<ARG, RET>::iterator mi = m_Memo.find(a);

if(mi != m_Memo.end())

{

return m_Memo[a];

}

else

{

vector<ARGnextIterArgs;

m_NextIterArgs.apply(a, nextIterArgs);

vector<RETnextIterRets;

nextIterRets.reserve(nextIterArgs.size());

for(size_t i = 0; i < nextIterArgs.size(); ++i)

{

nextIterRets.push_back(apply(nextIterArgs[i]));

}

return (m_Memo[a] = m_CalcNextIter.apply(nextIterRets));

}

}

};

Voila ... Auto memoization for functions :D ( I beleive haskell has

that )

If any of you gurus have an idea about improving this tell me.

One immediate thing I can see is to have 1 class instead of 3 and have

3 members in it, maybe make it a struct to get rid of that "public:"

I'm adding it to my topcoder bag of tricks...

Thanks

Vivek