[Haskell-cafe] New Benchmark Under Review: Magic Squares

Bulat Ziganshin bulat.ziganshin at gmail.com
Sun Jul 2 02:35:18 EDT 2006


Hello Brent,

Sunday, July 2, 2006, 3:58:11 AM, you wrote:

> We recently began considering another benchmark for the shootout,  
> namely a Magic Square via best-first search.  This is fairly

i've slightly beautified your printMatrix code:

    .....
    where
        showMatrix n grid = join "\n" [ showRow y | y<-[1..n] ]
            where showRow y = join " " [ show $ grid!(x,y) | x<-[1..n] ]

join filler pss = concat (intersperse filler pss)


> inefficient, and we may need to shift to another approach due to the
> extremely large times required to find a solution for larger squares.

it's interesting to see one more compiler-dependent (as opposite to
libraries-dependent) benchmark in shootout. It seems that the devil
hides in the last function, possibleMoves. i tried to replace using of
Data.Set with Data.Set.Enum by David F. Place, but got only 5%
improvement. This procedure heavily uses lists and that is not the
fastest data structure, especially in Haskell where lists are lazy.
One possible solution may be to use lists of strict (and automatically
unboxed) elements and/or lists that are strict in their links. Another
possible solution will be to use unboxed arrays and implement all
the required List routines for them.

About the overall algorithm - it tends to recompute data that is
almost not changed, such as list of already used numbers. It resembles
me sudoku solvers that was discussed here several months ago - its
highly possible that optimization tricks developed for this task will
be appropriate to speed up magic squares too.


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com



More information about the Haskell-Cafe mailing list