Boost logo

Boost :

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?


Boost list run by bdawes at, gregod at, cpdaniel at, john at