Skip to content

Instantly share code, notes, and snippets.

@nh2
Created April 6, 2014 15:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nh2/10007205 to your computer and use it in GitHub Desktop.
Save nh2/10007205 to your computer and use it in GitHub Desktop.
Benchmark for finding the k-smallest element in a list in Haskell
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