Boost logo

Boost :

Subject: Re: [boost] Any interest in a framework for memoization?
From: Giacomo Drago (giacomo_at_[hidden])
Date: 2013-11-22 08:35:57

> Hi Giacomo, thank you for your contribution.
> I'm interested in this kind of library, particularly I often implement
> dynamic programs. I've got some remarks/questions.
> * In your implementation you use std::function adaptor. You can remove it
> by making some of the member functions templates( e.g. getValue).

I see. Out of curiosity, what is the reason to do so (maybe
performance)? I chose std::function over template parameters as I find
it quite convenient, e.g. I can pass nullptr to the function and then
check this condition inside the function body.
Turning getValue into a template function will imply major refactoring:
Surely I will do it if it's required, and if you have some spare time,
I'd appreciate insights based on the actual code.

> * I'm interested in the case when Key type is integral. In this case one
> can make the following optimization. Let density be the "the number of
> elements in map" / "the largest element in map" ratio. If the density is
> large, it is much better to use vector instead of hash map. The idea is to
> measure the density and when it exceeds certain threshold switch from
> hashmap to vector. Did you consider this optimization? (I'm aware this is
> not as easy as I described). This makes sense when you consider the
> unbounded knapsack problem. In UKP it is not clear (you have to decide in
> runtime) if you should use vector/ or hashmap strategy . IMO the "integral
> Key" case covers many standard dynamic programs.

Interesting. How would you do it, with a template specialization for
int/long/etc... and maybe std::pair<int, int> keys? This would be
relatively easy, what I find tricky is to dynamically switch from the
hashmap to the vector while preserving thread safety. Do you have any

I appreciate your feedback and I'll work on your suggestion, but do you
think this library may eventually find its place into Boost?

Thank you for your time.

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