[boost] Re: Memoization library

From: Jim Apple (japple_at_[hidden])
Date: 2003-12-14 08:39:47

David Abrahams wrote:

> 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?

You're right.

>    How's the library meant to be used, in algorithm
>    prototyping, or in the final thing, or...

It's meant to be used when readability is more important than 
performance, but exponential performance is not acceptable.

>    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.

That's my feeling as well. Perhaps that means this sort of library is 
not right for boost. Perhaps I should code a bunch of examples first, to 
make it easier for boost-devel to decide if it is right for boost.

As far as readability, I'm sure the memoize functions would be much 
clearer.  I would be looking for the efficiency differences in
memoize vs. dynamic programming vs. manual memoize

> 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?

I don't think I understand your problem. Is the graph a function 
parameter, or a global? Does the graph stay the same through recursive 
calls, but change between top-level invocations, or can it change 
anytime? If it can change anytime, how do you envision memoization helping?

Jim