On Sun, Nov 8, 2009 at 2:51 AM, Pierre-Etienne Meunier <pierreetienne.meunier@gmail.com> 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