Subject: Re: [boost] Any interest in a framework for memoization?
From: Piotr Wygocki (vwygos_at_[hidden])
Date: 2013-11-23 05:25:16
On 22 November 2013 14:35, Giacomo Drago <giacomo_at_[hidden]> wrote:
> 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.
The std::function is not for free. You gain type erasure but you lose some
performance, you can read about it for example here:
> 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 think in this case it doesn't need major refactoring: each time you use
the underlined type you add template parameter to the function. Maybe I
> * 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
My first thought was specialising the class for the case when
std::is_integral<Key>::value is true.
Unfortunately, I do not have any smart thoughts concerning the thread
> I appreciate your feedback and I'll work on your suggestion, but do you
> think this library may eventually find its place into Boost?
I can only say that I'd like to see library like that in boost but I'm
afraid this is not my decision.
> Thank you for your time.
> Unsubscribe & other changes: http://lists.boost.org/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk