On Sun, Nov 8, 2009 at 2:51 AM, Pierre-Etienne Meunier
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