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

19 Nov 2013

      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  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 prereqs) {
    if (i == 0) return 0;
    if (i <= 2) return 1;
    return prereqs(i-1) + prereqs(i-2);
}
cppmemo::CppMemo 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

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

Piotr Wygocki