[boost] Re: Memoization library

From: David Abrahams (dave_at_[hidden])
Date: 2003-12-12 21:58:56

Jim Apple <japple_at_[hidden]> writes:

> 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);
>    }
> }

OK, I think I understand this difference.

Jim Apple <japple_at_[hidden]> writes:

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

Does the literature have a clear meaning for "implicit"?

> but I'm not really attached to any name for the concept.  We could
> call it as-need dynamic programming to be more clear.

OK, I think I understand the meaning.

> A danger of this library is that it encourages lazy solutions

You say that like it's a *bad* thing.  Lazy is good ;-)

BTW, is it threadsafe?

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com