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

Subject: Re: [boost] Any interest in a framework for memoization?
From: Piotr Wygocki (vwygos_at_[hidden])
Date: 2013-11-19 08:33:50

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_at_[hidden]> 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
>