Created
April 6, 2014 15:02
-
-
Save nh2/10007205 to your computer and use it in GitHub Desktop.
Benchmark for finding the k-smallest element in a list in Haskell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Criterion.Main | |
import Data.List (sort) | |
import Data.Vector (Vector, fromList, unsafeThaw) | |
import qualified Data.Vector.Mutable as VM | |
import Data.Vector.Algorithms.Heap (select) | |
import Control.Monad.ST (runST) | |
import Data.Maybe (fromJust) | |
kSmallest1 :: Int -> [Int] -> Int | |
kSmallest1 k l = sort l !! k | |
kSmallest2 :: Int -> [Int] -> Int | |
kSmallest2 k l = runST $ do | |
vec <- unsafeThaw (fromList l :: Vector Int) | |
select vec k | |
VM.read vec k | |
secondSmallest :: [Int] -> Int | |
secondSmallest l = go l maxBound maxBound | |
where | |
go [] _ s2 = s2 | |
go (x:xs) s1 s2 | x < s1 = go xs x s1 | |
| x < s2 = go xs s1 x | |
| otherwise = go xs s1 s2 | |
secondSmallestMaybe :: [Int] -> Maybe Int | |
secondSmallestMaybe [] = Nothing | |
secondSmallestMaybe [_] = Nothing | |
secondSmallestMaybe l = Just $ go l maxBound maxBound | |
where | |
go [] _ s2 = s2 | |
go (x:xs) s1 s2 | x < s1 = go xs x s1 | |
| x < s2 = go xs s1 x | |
| otherwise = go xs s1 s2 | |
main :: IO () | |
main = defaultMain $ | |
[ bench "10000" $ whnf (kSmallest1 0) [1..10000::Int] | |
, bench "20000" $ whnf (kSmallest1 0) [1..20000::Int] | |
, bench "40000" $ whnf (kSmallest1 0) [1..40000::Int] | |
, bench "80000" $ whnf (kSmallest1 0) [1..80000::Int] | |
, bench "160000" $ whnf (kSmallest1 0) [1..160000::Int] | |
, bench "10000" $ whnf (kSmallest2 0) [1..10000::Int] | |
, bench "20000" $ whnf (kSmallest2 0) [1..20000::Int] | |
, bench "40000" $ whnf (kSmallest2 0) [1..40000::Int] | |
, bench "80000" $ whnf (kSmallest2 0) [1..80000::Int] | |
, bench "160000" $ whnf (kSmallest2 0) [1..160000::Int] | |
, bench "10000" $ whnf (kSmallest1 1) [1..10000::Int] | |
, bench "20000" $ whnf (kSmallest1 1) [1..20000::Int] | |
, bench "40000" $ whnf (kSmallest1 1) [1..40000::Int] | |
, bench "80000" $ whnf (kSmallest1 1) [1..80000::Int] | |
, bench "160000" $ whnf (kSmallest1 1) [1..160000::Int] | |
, bench "10000" $ whnf (kSmallest2 1) [1..10000::Int] | |
, bench "20000" $ whnf (kSmallest2 1) [1..20000::Int] | |
, bench "40000" $ whnf (kSmallest2 1) [1..40000::Int] | |
, bench "80000" $ whnf (kSmallest2 1) [1..80000::Int] | |
, bench "160000" $ whnf (kSmallest2 1) [1..160000::Int] | |
, bench "10000 2nd" $ whnf secondSmallest [1..10000::Int] | |
, bench "20000 2nd" $ whnf secondSmallest [1..20000::Int] | |
, bench "40000 2nd" $ whnf secondSmallest [1..40000::Int] | |
, bench "80000 2nd" $ whnf secondSmallest [1..80000::Int] | |
, bench "160000 2nd" $ whnf secondSmallest [1..160000::Int] | |
, bench "320000 2nd" $ whnf secondSmallest [1..320000::Int] | |
, bench "640000 2nd" $ whnf secondSmallest [1..640000::Int] | |
, bench "10000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..10000::Int] | |
, bench "20000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..20000::Int] | |
, bench "40000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..40000::Int] | |
, bench "80000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..80000::Int] | |
, bench "160000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..160000::Int] | |
, bench "320000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..320000::Int] | |
, bench "640000 maybe" $ whnf (fromJust . secondSmallestMaybe) [1..640000::Int] | |
] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment