Hi Dan! You might want to change the following: shuffleRec :: StdGen -> [a] -> [a] shuffleRec g list = x:shuffleArr g' xs where (n,g') = randomR (0,length list-1) g (x:xs') = drop n list xs = take n list ++ xs'
into the following: shuffleRec :: StdGen -> [a] -> [a] shuffleRec g list = x:shuffleRec g' xs where (n,g') = randomR (0,length list-1) g (x:xs') = drop n list xs = take n list ++ xs' Since shuffleRec just called shuffleArr, one would expect them to run in approximately the same time :-) //Tobias 2009/9/22 Dan Rosén <[email protected]>: > Dear haskell-cafe users, > > I am constructing a shuffle function: given an StdGen and a list, return the > list permuted, with all permutations of equal probability. > > There is the simlpe recursive definition: generate a number from 1 to length > list, take this element out from the list, call the function recursively on > the remaining list and then cons the element on the shuffled list. > > A more imperative approach is to make the list an array, and traverse the > array in reverse, swapping the iterated element with an arbitrary element > less than or equal to the iterator. > > These functions are implemented as shuffleRec and shuffleArr, respectively. > > What complexity does these functions have? > > I argue that the shuffleArr function should be O(n), since it only contains > one loop of n, where each loop does actions that are O(1): generating a random > number and swapping two elements in an array. > > I argue that the shuffleRec function should be O(n^2), since for each call, > it creates a new list in O(n), with the drop and take calls, and calls itself > recursively. This yields O(n^2). > > However, they both have the same runnig time (roughly), and through looking > at the plot it _very_ much looks quadratic. > > I am compiling with GHC and I guess there is something in the lazy semantics > that confuses me about the complexities, and maybe I have misunderstood how > STArrays work. > > Any pointers to what's going in is greatly appreciated! > > Best regards, > Dan Rosén, Sweden > > Here is the code: > > module Main where > > import Control.Monad > import Control.Monad.ST > import Data.Array.ST > import Data.STRef > import System.Random > > import Time > import CPUTime > > shuffleArr :: StdGen -> [a] -> [a] > shuffleArr g list = runST $ do > let n = length list > gref <- newSTRef g > arr <- listToArray list > forM_ [n,n-1..2] $ \p -> do > m <- rand (1,p) gref > swap arr m p > getElems arr > where > rand range gref = do > g <- readSTRef gref > let (v,g') = randomR range g > writeSTRef gref g' > return v > > swap a n m = do > [n',m'] <- mapM (readArray a) [n,m] > mapM (uncurry $ writeArray a) [(m,n'),(n,m')] > > listToArray :: [a] -> ST s (STArray s Int a) > listToArray list = let n = length list > in newListArray (1,n) list > > shuffleRec :: StdGen -> [a] -> [a] > shuffleRec g list = x:shuffleArr g' xs > where > (n,g') = randomR (0,length list-1) g > (x:xs') = drop n list > xs = take n list ++ xs' > > -- A somewhat lame attempt to derive the complexities through testing, > -- prints the times for the different functions in a table > main :: IO () > main = do > let times = take 30 $ iterate (+30000) 10000 > answers <- mapM test times > sequence_ [ putStrLn $ concatMap ((++ "\t"). show) [toInteger t,arr,rec] > | (t,(arr,rec)) <- zip times answers > ] > > -- Perform a test of size n, and return the cycles it took for the different > -- algorithms in a pair. Evaluation is enforced by seq on length of the list. > test :: Int -> IO (Integer,Integer) > test n = do > let list = [1..n] > [g1,g2] <- replicateM 2 newStdGen > length list `seq` do > s <- doTime ("shuffleArr " ++ show n) $ > (length $ shuffleArr g1 list) `seq` return () > s' <- doTime ("shuffleRec " ++ show n) $ > (length $ shuffleRec g2 list) `seq` return () > return (s,s') > > -- This is taken from GenUtil from the JHC creator's homepage > doTime :: String -> IO a -> IO Integer > doTime str action = do > start <- getCPUTime > x <- action > end <- getCPUTime > let time = (end - start) `div` 1000000 -- `div` cpuTimePrecision > -- putStrLn $ "Timing: " ++ str ++ " " ++ show time > return time > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Tobias Olausson [email protected] _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
