[Haskell-beginners] Memoization

[Daniel Fischer]

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.