Am Donnerstag 29 Oktober 2009 02:45:35 schrieb Shawn Willden:
Hi,
I've just begun experimenting with Haskell, and I'm having a lot of fun, but my first semi-serious program is in need of some optimization, and based on the results of profiling I think a really good start is to memoize one particular function which is called many, many times (and currently consumes over 80% of the program run time).
The function takes a two-dimensional range and a location within that range and returns a list of the locations vertically and horizontally adjacent to that location and within the bounds
type Bounds = ((Int,Int),(Int,Int)) type Location = (Int,Int) adjacentCells :: Bounds -> Location -> [Location] adjacentCells bounds (col, row) = filter valid cells where valid loc = inRange bounds loc neighborLoc' = [(col-1,row),(col+1,row),(col,row-1),(col,row+1)]
The ranges are fairly small -- certainly no more than 10x10, and each location has an associated list of at most 4 neighbors (edge locations have less). During a given run of the program, the bounds are fixed.
Probably the simplest thing to do is use an array. At the start of your programme let neighbourArray = array bounds [(loc, adjacentCells bounds loc) | loc <- range bounds] and replace calls "adjacentCells bounds loc" with "neighbourArray!loc"
Thanks,
Shawn.