[Haskell-cafe] Implementation of the Floyd-Warshall algorithm

[Bulat Ziganshin]

Hello frederic,

Friday, July 28, 2006, 10:44:51 AM, you wrote:

> much slower than the C version.  I would be very grateful if someone
> cared to explain why this is unefficient and how to make it faster

update :: STUArray s (Int, Int) Double -> Int -> Int -> Int -> ST s ()
update arr i j k = do aij <- readArray arr (i, j)

try

update arr i j k | arr `seq` i `seq` j `seq` k `seq` True = do aij <- readArray arr (i, j)

and make the same changes in other update functions. we has
http://haskell.org/haskellwiki/Performance page, you should read it

second problem is bounds checking in readArray. if you want better
speed, you should use unsafeRead/unsafeWrite and compute index with
something like (i*count+j)

btw, 'newArray ((0, 0), (10, 10))' creates array with 121 elements. is
this what you really need?

also, "foreach=flip mapM_" will be useful for you. i also recommend
you to read http://haskell.org/haskellwiki/IO_inside - ST monad
differs from IO one only in what its operations are restricted to
array/reference ones


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