Hello This post meant to be literate haskell.
I found that perfomace of indexU is very poor and it is not fast O(1) operation which is very surprising. Here is some benchmarcking I've done. Everything compiled with -O2 Code below converts square 2D array to list of 1D arrays. Summation of array contents is done in force evaluation > import Control.Monad > import Control.Monad.ST > import Data.Array.Vector > import System > > arr :: Int -> UArr Double > arr n = toU $ map fromIntegral [1 .. n*n] > This is fastest function. It slice arrays along another direction and used mainly as upper bound of speed > sliceY :: Int -> UArr Double -> [UArr Double] > sliceY n a = map (\i -> sliceU a (i*n) n) [0 .. n-1] > Naive implementation using lists and index lookup. 2.15 second for 200*200 array > sliceXlist :: Int -> UArr Double -> [UArr Double] > sliceXlist n a = map mkSlice [0 .. n-1] > where > mkSlice x = toU $ map (\y -> indexU a (x + y*n)) [0 .. n-1] Similar implementation in ST monad and it uses indexU too. 2.14 seconds for 200*200 array > sliceXst :: Int -> UArr Double -> [UArr Double] > sliceXst n a = map mkSlice [0 .. n-1] > where > mkSlice x = runST $ do arr <- newMU n > forM_ [0 .. n-1] $ \y -> writeMU arr y (indexU a > (y*n + x)) > unsafeFreezeAllMU arr This implementation avoids use of indexU by copying entire 2D array into mutable array and using it for lookup. Surprisingly it outperform previsious implementations for sufficiently big n 1.19 seconds for 200*200 array > sliceXcopy :: Int -> UArr Double -> [UArr Double] > sliceXcopy n a = map mkSlice [0 .. n-1] > where > mkSlice x = runST $ do arr <- newMU n > cp <- newMU (n*n) > copyMU cp 0 a > forM_ [0 .. n-1] $ \y -> writeMU arr y =<< > readMU cp (y*n + x) > unsafeFreezeAllMU arr This is another implementation with lists which convert whole array to list and picks appropriate element it. It is fastest implementation so far. 0.039 seconds for 200*200 array > sliceXlistfast :: Int -> UArr Double -> [UArr Double] > sliceXlistfast n a = map mkSlice [0 .. n-1] > where > takeEvery n [] = [] > takeEvery n (x:xs) = x : takeEvery n (drop (n-1) xs) > mkSlice x = toU $ takeEvery n . drop x $ fromU a > > > ---------------------------------------------------------------- > main :: IO () > main = do > [str,a] <- getArgs > let n = read str > case a of > "y" -> print $ sum $ map sumU (sliceY n (arr n)) > "list" -> print $ sum $ map sumU (sliceXlist n (arr n)) > "lf" -> print $ sum $ map sumU (sliceXlistfast n (arr n)) > "st" -> print $ sum $ map sumU (sliceXst n (arr n)) > "copy" -> print $ sum $ map sumU (sliceXcopy n (arr n)) _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
