R
rep_movsd
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, int> fib_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, FibCalcNextIter> fibo;
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, RET> m_Memo;
RET apply(ARG &a)
{
pair<bool, RET> r;
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<ARG> nextIterArgs;
m_NextIterArgs.apply(a, nextIterArgs);
vector<RET> nextIterRets;
nextIterRets.reserve(nextIterArgs.size());
for(size_t i = 0; i < nextIterArgs.size(); ++i)
{
nextIterRets.push_back(apply(nextIterArgs));
}
return (m_Memo[a] = m_CalcNextIter.apply(nextIterRets));
}
}
};
Voila ... Auto memoization for functions ( 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
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, int> fib_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, FibCalcNextIter> fibo;
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, RET> m_Memo;
RET apply(ARG &a)
{
pair<bool, RET> r;
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<ARG> nextIterArgs;
m_NextIterArgs.apply(a, nextIterArgs);
vector<RET> nextIterRets;
nextIterRets.reserve(nextIterArgs.size());
for(size_t i = 0; i < nextIterArgs.size(); ++i)
{
nextIterRets.push_back(apply(nextIterArgs));
}
return (m_Memo[a] = m_CalcNextIter.apply(nextIterRets));
}
}
};
Voila ... Auto memoization for functions ( 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