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?
> 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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk