Generic function Memo-izer template class

[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, intfib_memo;
int fibm(int n)
{
map<int,int>::i terator 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 FibGetNextIterA rgs
{
public:
void apply(int arg, vector<int>& rets)
{
rets.push_back( arg - 1);
rets.push_back( arg - 2);
}
};

class FibCalcNextIter
{
public:
int apply(vector<in t>& rets)
{
return rets[0] + rets[1];
}
};

and call it like this:

Memoize<int, int, FibCalc, FibGetNextIterA rgs, FibCalcNextIter fibo;
int i = 1000;
cout << fibo.apply(i);

the Memoize definition is below:

template<typena me 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<ARGnextI terArgs;
m_NextIterArgs. apply(a, nextIterArgs);

vector<RETnextI terRets;
nextIterRets.re serve(nextIterA rgs.size());
for(size_t i = 0; i < nextIterArgs.si ze(); ++i)
{
nextIterRets.pu sh_back(apply(n extIterArgs[i]));
}

return (m_Memo[a] = m_CalcNextIter. apply(nextIterR ets));
}
}
};


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

[Alan Johnson]

Re: Generic function Memo-izer template class


rep_movsd wrote:

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>::i terator 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 FibGetNextIterA rgs
{
public:
void apply(int arg, vector<int>& rets)
{
rets.push_back( arg - 1);
rets.push_back( arg - 2);
}
};
>
class FibCalcNextIter
{
public:
int apply(vector<in t>& rets)
{
return rets[0] + rets[1];
}
};
>
and call it like this:
>
Memoize<int, int, FibCalc, FibGetNextIterA rgs, FibCalcNextIter fibo;
int i = 1000;
cout << fibo.apply(i);
>
the Memoize definition is below:
>
template<typena me 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<ARGnextI terArgs;
m_NextIterArgs. apply(a, nextIterArgs);
>
vector<RETnextI terRets;
nextIterRets.re serve(nextIterA rgs.size());
for(size_t i = 0; i < nextIterArgs.si ze(); ++i)
{
nextIterRets.pu sh_back(apply(n extIterArgs[i]));
}
>
return (m_Memo[a] = m_CalcNextIter. apply(nextIterR ets));
}
}
};
>
>
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

Using map to store the history bothers me a little, just because it
makes the runtime different (worse) than what many would expect for
some algorithms. Using Fibonacci as an example, you should be able to
calculate each successive member of the sequence in constant time
(assuming constant time operations on integers), so computing the first
N members of the sequence should require O(N) time.

Storing the results in a map, though, only gives you a guarantee that
you'll be able to lookup elements in O(lg N) time, so computing the
first N members of the sequence has time in O(N lg N).

I assume you chose a map to conserve space in algorithms where not
every index is used. I would suggest somehow expanding your template
to allow the client to decide the space/speed trade off, perhaps by
supplying a container type as a template parameter.

--
Alan Johnson

[rep_movsd]

Re: Generic function Memo-izer template class

Alan Johnson wrote:

Using map to store the history bothers me a little, just because it
makes the runtime different (worse) than what many would expect for
some algorithms. Using Fibonacci as an example, you should be able to
calculate each successive member of the sequence in constant time
(assuming constant time operations on integers), so computing the first
N members of the sequence should require O(N) time.

While a tail recursive or iterative fibonacci can be written to run in
O(n) time, that is not the point of this.

The point is that there are some algorithms which are much easily
expressed in a recursive fashion and this technique helps to express
the solution in a recursive paradigm and still get solutions which do
not have exponential space and time requirements.

In such cases, the invocation of the function with argument x would
depend on N number of recursive invocations with x1 to xN.
In such situations, memoization is the only way to beat the clock.
Haskell is one language where functions are memoized automatically.

Take for example this function to calculate the number of possible k
digit numbers which consist of the digits 1 to n and where the digits
are all in non-ascending order :

eg for k = 2 , n = 3

11
21
22
31
32
33

are all non ascending.


Heres the raw recursive implementation

int getNonDescCombo s(int k, int n)
{
if(k == 1)
return n;

int total = 0;
for(int i = 1; i <= n; ++i)
{
total += getNonDescCombo s(k - 1, i);
}
return total;
}

While its working is clear, No prizes for guessing that this will
overflow the stack for even modest values of n and k.

now look at the memoized version :

map<pair<int, int>, intnonDescCombo s;
int getNonDescCombo s(pair<int, intarg)
{
int k = arg.first;
int n = arg.second;
if(k == 1)
return n;

map<pair<int, int>, int>::iterator mi = nonDescCombos.f ind(arg);
if(mi == nonDescCombos.e nd())
{
int total = 0;
for(int i = 1; i <= n; ++i)
{
total += getNonDescCombo s(make_pair(k - 1, i));
}
return (nonDescCombos[arg] = total);
}
else
{
return mi->second;
}
}

getNonDescCombo s( make_pair(100, 9) );
Runs with good space and time charecteristics , but is much more
complicated and the logic is more opaque.

now generalized with memoizer template...

class GetDescCombosCa lc
{
public:
void apply(pair<int, int&p, pair<bool, int>& ret)
{
ret.first = p.second == 1;
ret.second = p.first;
}
};

class GetDescCombosGe tNextIterArgs
{
public:
void apply(pair<int, int>& arg, vector<pair<int , int& rets)
{
for(int i = 1; i <= arg.first; ++i)
{
rets.push_back( make_pair(i, arg.second - 1));
}
}
};

class GetDescCombosCa lcNextIter
{
public:
int apply(vector<in t>& rets)
{
int total = 0;
for(size_t i = 0; i < rets.size(); ++i)
{
total += rets[i];
}

return total;
}
};

Definitely more verbose, but the logic of the recursive version is
preserved...
the first class does the job of calculating the simplest cases..
the second gives a collection of values (x1 to xN) for which the
function has to be computed before computing f(x).
The last one computes f(x) given f(x1) to f(xN) computed from the
previous results.
A large number of algorithms can readily be genralized to this pattern
with clear logic.

Finally the invocation becomes as simple as....

Memoize<int, pair<int, int>, GetDescCombosCa lc,
GetDescCombosGe tNextIterArgs, GetDescCombosCa lcNextIterm;
int n = 100;
int k = 29;
m.apply(make_pa ir(k, n));

Storing the results in a map, though, only gives you a guarantee that
you'll be able to lookup elements in O(lg N) time, so computing the
first N members of the sequence has time in O(N lg N).
I assume you chose a map to conserve space in algorithms where not
every index is used. I would suggest somehow expanding your template
to allow the client to decide the space/speed trade off, perhaps by
supplying a container type as a template parameter.

One option would be to use a hash_map maybe, and anyway the Memoize
class is opaque so changing the implementation would make no difference
to the code for the computation, as long as the logic were same the
intermediate results could be stored any which way.

Regards
Vivek

[Greg Buchholz]

Memoizing fixed point combinator (was: Generic function Memo-izer template class)

rep_movsd wrote:

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.

// You might also like to try something like a memozied fixed point
// combinator. ( http://en.wikipedia.org/wiki/Y_combinator )

#include<iostre am>
#include<map>

std::map<int,in tmemo_table;

struct Fix
{
int (*f)(int,Fix);

int operator()(int x, Fix g)
{
return (memo_table.fin d(x) != memo_table.end( ))
? memo_table[x]
: memo_table[x] = g.f(x,g);
};
};

int fib(int n, Fix f) { return n < 2 ? n : f(n-1,f) + f(n-2,f); }

int main(int argc, char *argv[])
{
Fix g = {fib};
std::cout << g(40,g) << std::endl;
return 0;
}

[Alf P. Steinbach]

Re: Memoizing fixed point combinator

* Greg Buchholz:

>
#include<iostre am>
#include<map>
>
std::map<int,in tmemo_table;
>
struct Fix
{
int (*f)(int,Fix);
>
int operator()(int x, Fix g)
{
return (memo_table.fin d(x) != memo_table.end( ))
? memo_table[x]
: memo_table[x] = g.f(x,g);
};
};
>
int fib(int n, Fix f) { return n < 2 ? n : f(n-1,f) + f(n-2,f); }
>
int main(int argc, char *argv[])
{
Fix g = {fib};
std::cout << g(40,g) << std::endl;
return 0;
}

What's the point of the argument passing when Fix uses a global table?
Fix is just a bug waiting to happen. E.g., after using Fix g = {fib},
try using Fix h = {identityFuncti on}.

And what's the point of caching (which for some reason a lot of people
now call "memoizatio n") when that involves completely rewriting the
function, which can be much more easily rewritten to be efficient?

Finally, what's the point of filling in the cache at run-time when that
will result in all values up to (n, f(n)) being placed in the cache?

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[rep_movsd]

Re: Memoizing fixed point combinator

What's the point of the argument passing when Fix uses a global table?

Fix is just a bug waiting to happen. E.g., after using Fix g = {fib},
try using Fix h = {identityFuncti on}.

And what's the point of caching (which for some reason a lot of people
now call "memoizatio n") when that involves completely rewriting the
function, which can be much more easily rewritten to be efficient?

Well you cannot express some algorithms iteratively no matter how
cleverly you code, you will end up using an explicit stack.

Finally, what's the point of filling in the cache at run-time when that
will result in all values up to (n, f(n)) being placed in the cache?

Well the whole point of memoization is that it forms the base of
"dynamic" programming problems where divide-and-conquer changes to
divide-and-conquer-memoize-to-avoid-reconquer.

I humbly suggest http://en.wikipedia.org/wiki/Dynamic_programming

Regards
Vivek

[Alf P. Steinbach]

Re: Memoizing fixed point combinator

* rep_movsd:

>What's the point of the argument passing when Fix uses a global table?
>Fix is just a bug waiting to happen. E.g., after using Fix g = {fib},
>try using Fix h = {identityFuncti on}.

>
>

>And what's the point of caching (which for some reason a lot of people
>now call "memoizatio n") when that involves completely rewriting the
>function, which can be much more easily rewritten to be efficient?

>
Well you cannot express some algorithms iteratively no matter how
cleverly you code, you will end up using an explicit stack.

So?

>Finally, what's the point of filling in the cache at run-time when that
>will result in all values up to (n, f(n)) being placed in the cache?

>
Well the whole point of memoization is that it forms the base of
"dynamic" programming problems where divide-and-conquer changes to
divide-and-conquer-memoize-to-avoid-reconquer.

Again, so? AFAICS, again there's no relevance to my question.

I humbly suggest http://en.wikipedia.org/wiki/Dynamic_programming

Well.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?