[Haskell-cafe] Memoizing in parallel
lrpalmer at gmail.com
Sun Nov 8 08:08:35 EST 2009
On Sun, Nov 8, 2009 at 2:51 AM, Pierre-Etienne Meunier
<pierreetienne.meunier at gmail.com> wrote:
> I'm designing an algorithm that uses dynamic programming. I've written it
> with an array, and it works, but it is still very slow and needs way too
> much memory.
> Then I realized that the array was very sparse (at most a O(\sqrt(n)) of its
> size is actually used). Now I want to rewrite it with a Data.Map, but since
> I do not know a priori what the keys are, I need a mutable ref somewhere.
I don't know how you drew that conclusion.
In fact, no mutable ref is necessary. Your keys are (or can be mapped
to) integers, since you used an array. A solution is to use a trie of
integers. You could, for example, store the values at the nodes of
an infinite tree that looks like:
3 4 5 6
7 8 9 10 11 12 13 14
There are various implementations of this around. For a quick
solution, though, you can try the data-memocombinators package:
import qualified Data.MemoCombinators as Memo
let f = Memo.integral go
go = ... f ...
See how that performs. It has asymptotically better space performance
for sparse usage, but the devil can be in the constant factors.
More information about the Haskell-Cafe