On Sun, Nov 8, 2009 at 2:51 AM, Pierre-Etienne Meunier
<[email protected]> wrote:
> Hi,
>
> 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:
0
1 2
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
where
go = ... f ...
See how that performs. It has asymptotically better space performance
for sparse usage, but the devil can be in the constant factors.
Luke
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
