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