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