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'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. Regards, Piotr On 18 November 2013 09:30, Giacomo Drago <giacomo@giacomodrago.com> wrote:
Hi,
I would like to submit a small framework for memoization I am working on ( http://projects.giacomodrago.com/c++memo/). At the moment, it is still in a beta stage and does not comply with Boost guidelines. I would like to know if you might be interested.
The idea is to have a tool for rapid prototyping of software components implementing dynamic programming algorithms or, anyhow, requiring memoization.
I paste here a simple "fibonacci" example:
----------------------
int fibonacci(int i, std::function<int(int)> prereqs) { if (i == 0) return 0; if (i <= 2) return 1; return prereqs(i-1) + prereqs(i-2); } cppmemo::CppMemo<int, int> cppMemo; std::cout << cppMemo.getValue(30, fibonacci) << std::endl;
----------------------
The code will print 832040, without recursive calls to the "fibonacci" function. A stack is managed "under the hood" and appropriate calls are made to the "fibonacci" callback to gather pre-requirements and then call the function again when they are available.
This is just a toy example. There is more to know about, including important caveats (if you are interested, please read the documentation carefully): some defaults for template and method parameters are useful for conciseness but are EVIL if you don't know about them. The framework also provides automatic parallelization (when possible).
It is important to remark that at this moment the framework relies on fcmm (fast concurrent memoization map), a custom hashmap that is optimized for this very purpose. This can be changed quite easily, as fcmm is not exposed to the client. A C++11 compliant compiler is needed.
Thanks for your attention.
Giacomo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost