SHARE
TWEET

mergetest

tdct Nov 19th, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-# LANGUAGE ScopedTypeVariables #-}
  2. {-# LANGUAGE ViewPatterns #-}
  3.  
  4. import Data.List (unfoldr)
  5. import System.Random (randomR, StdGen, split, newStdGen)
  6. import Control.Monad (replicateM)
  7. import Control.Parallel.Strategies
  8. import Criterion.Main
  9. import Data.Foldable(foldr')
  10.  
  11. randGens :: Int -> IO([StdGen])
  12. randGens n = let
  13.    f 0 _ = Nothing
  14.    f n (split -> (x, x')) = Just (x, (n - 1, x'))
  15.    in do
  16.        seed <- newStdGen
  17.        return $ unfoldr (uncurry f) (n, seed)
  18.  
  19.  
  20. randomList :: Int -> StdGen -> [Int]
  21. randomList n s
  22.    | n == 0 = []
  23.    | otherwise = r : randomList (n - 1) s' where
  24.         (r, s') = randomR (0, n) s
  25.  
  26.  
  27. main :: IO ()
  28. main = do
  29.    seeds <- ([7..] `zip`) <$> randGens 17
  30.    let xs = map (\(i, g) -> randomList (2 ^ i) g) seeds
  31.    defaultMain [
  32.            bgroup "mergesort" $ map (\x -> bench (show $ 2 ^ (7 + x)) $ whnf sort $ xs !! x) [0..16]
  33.        ,   bgroup "mergesort(s)" $ map (\x -> bench (show $ 2 ^ (7 + x)) $ whnf sort' $ xs !! x) [0..16]
  34.         ]
  35.  
  36.  
  37. merge :: (Ord a) => [a] -> [a] -> [a]
  38. merge xs [] = xs
  39. merge [] ys = ys
  40. merge (x:xs) (y:ys)
  41.     | x <= y =  x : merge xs (y:ys)
  42.     | otherwise = y : merge (x:xs) ys
  43.  
  44.  
  45. pairList :: [[a]] -> [([a], [a])]
  46. pairList (x1:x2:xs) = (x1, x2) : pairList xs
  47. pairList (x:xs) = [(x, [])]
  48. pairList [] = []
  49.  
  50.  
  51. sort :: (Ord a) => [a] -> [a]
  52. sort xs = k . map (:[]) $ xs where
  53.     f = parMap rpar (uncurry merge)
  54.     k [x] = x
  55.     k xs = k . f . pairList $ xs
  56.  
  57.  
  58. sort' :: (Ord a) => [a] -> [a]
  59. sort' xs = k . map (:[]) $ xs where
  60.     f = map (uncurry merge)
  61.     k [x] = x
  62.     k xs = k . f . pairList $ xs
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top