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
suggestions/examples?
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.
Giacomo