[Haskell-cafe] Memoizing in parallel

[Luke Palmer]

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