Re: [boost] Any interest in a framework for memoization?

On 22 November 2013 14:35, Giacomo Drago 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: http://stackoverflow .com/questions/5057382/what-is-the-performance-overhead-of-stdfunction

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 missed something.

* 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 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?

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 safety.

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. Regards, Piotr

Thank you for your time.

Giacomo

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost