• API
• FAQ
• Tools
• Archive
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)
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.

Top