[boost] Re: Memoization library

From: Jim Apple (japple_at_[hidden])
Date: 2003-12-12 21:30:50

Let me try again.

Memoizing a function involves stoing all calls and results in a table. 
Dynamic programming involves building a table of results along the way.

A dynamic programming approach to computing fibonacci numbers would look 
like:

int fib(int n) {
   vector<int> ans;
   ans.push_back(1);
   ans.push_back(1);
   for(unsigned i = 2; i <=n; ++i)
     ans.push_back(ans[i-1] + ans[i-2]);
   return ans[n];
}

A memoized approach would be

int fib(int n) {
   static std::map<int,int> memo;
   if (memo.find(n) == memo.end()) {
     int result = fib(n-1) + fib(n-2);
     memo[n] = result;
     return result;
   } else {
     return (memo.find(n)->second);
   }
}

Notes:
1. As you pointed out, neither one of these is the smart way to do it. 
Some of the examples in the last message were more approprite candidates 
for memoization or dynamic programming; I can write one or two up in 
code, if desired.
2. This is not smart use of std::map.  I chose this use for 
demonstration purposes only.

David Abrahams wrote:
> Example?  I always think of dynamic programming as creating the cache
> implicitly, too.

I think the literature disagrees with you, but I'm not really attached 
to any name for the concept.  We could call it as-need dynamic 
programming to be more clear.

A danger of this library is that it encourages lazy solutions, like 
memoizing fibonacci, when merely implementing it with zero static 
storage and zero recursive calls is possible.

Jim