[Haskell-cafe] Memoizing in parallel
pierreetienne.meunier at gmail.com
Sun Nov 8 04:51:28 EST 2009
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.
Which is fine, but... the array solution allowed me to explore the
subsolutions in parallel with Control.Parallel, and use items already
evaluated by other threads in the array, while an STRef forbids it.
Can someone know how to do it (outside IO, and without using
unsafePerformIO, of course) ?
More information about the Haskell-Cafe