[boost] Re: Memoization library

From: David Abrahams (dave_at_[hidden])
Date: 2003-12-14 08:06:33

Jim Apple <japple_at_[hidden]> writes:

> New syntax possible:
>
> int choose(int n, int k) {
>    function<int (int,int)> choose = memoize(choose);
>    if ((k == 0) || (k == n)) {
>      return 1;
>    } else {
>      return choose(n-1,k-1) + choose(n-1,k);
>    }
> }
>
> "memoize" doesn't have to go through its whole creation and binding
> procedure for each recursive call, though, because it is actaully
> memoized.  It need only look up the answer from previous calls.
>
> I could also build in a third parameter with type memo_p_t, with
> default value "memoized."  If choose is called as
>
> choose(x,y,no_memo)
>
> the function<int (int,int)> choose is initialized with the int
> choose(int,int).

Two comments:

1. this "feels" like a very inefficient way to achieve efficiency, if
   you know what I mean.  There's a table lookup for memoize and then
   another one, plus virtual function overhead, for each invocation of
   choose, right?  How's the library meant to be used, in algorithm
   prototyping, or in the final thing, or...  Maybe that's just
   low-level C++ crazy talk.  After all, a quick road to a large big-O
   improvement is probably worth more than those constant time or logN
   overheads cost.  You might have to provide lots of compelling
   examples to get C++ programmers to accept it, though.

2. I've often wanted to use dynamic programming/memoization in a
   system where changes could invalidate part of the cache.  Think of
   a shortest path algorithm where a few pieces of the graph can
   change between invocations.  How would one accomodate that?

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