Daniel Fischer's modifications to my original program lead to a 400 %
speed boost !!!
(It now runs in 22 seconds on my machine)
He avoided unecessary calls to 'length', uses Array instead of Map,
refactored 'search' function (details below)
I've put up his version on hpaste : http://hpaste.org/2452#a1
Manu
On Aug 26, 2007, at 10:56 PM, Daniel Fischer wrote:
Without much thinking I can spped it up by a factor of 4 (from 280s
to 60s).
The most important things are:
- don't use length unless you need it
instead of
newV2 <- case length newCell of
0 -> Nothing
...
and
case length dPlaces of
0 -> ...
use
case newCell of
[] -> Nothing
[d'] -> ...
and
case dPlaces of
[] -> Nothing
[s'] -> ...
- let dPlaces = [ s' | u <- lookup s units, s' <- u, elem d (lookup
s' newV2)]
is bad
let dPlaces = [s' | s' <- lookup s peers, elem d (lookup s' newV2)]
scans each peer only once
- search is really bad, you lookup all squares several times,
potentially
compute all lengths multiple times...
much better is
search :: Grid -> Maybe Grid
search g = case [(l,a) | a@(_,xs) <- M.assocs g, let l = length xs,
l /= 1] of
[] -> return g
ls -> do let (_,(s,ds)) = minimum ls
msum [assign g (s,d) >>= search | d <- ds]
(I also changed the type, and instead of foldl' you should use
foldr, since
"some" is lazy in the second argument, further, since Maybe is a
MonadPlus,
it's "mplus" and 'foldr mplus Nothing' is msum)
- Maps aren't good here, too slow lookup and you know the keys, so
use arrays
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
