public
Last active

  • Download Gist
gistfile1.md
Markdown
import Data.List
import qualified Data.Set as Set
import Criterion.Main 
import System.Random
import Control.Applicative



main :: IO ()
main = defaultMain [
    bgroup "input1" [
      bench "nub" $ nfIO $ nub <$> generateInput (0, 100) 1000,
      bench "poorsod1" $ nfIO $ poorsod1 <$> generateInput (0, 100) 1000,
      bench "poorsod2" $ nfIO $ poorsod2 <$> generateInput (0, 100) 1000,
      bench "volkov" $ nfIO $ volkov <$> generateInput (0, 100) 1000,
      bench "scvalex" $ nfIO $ scvalex <$> generateInput (0, 100) 1000
    ],
    bgroup "input2" [
      bench "nub" $ nfIO $ nub <$> generateInput (0, 1000) 1000,
      bench "poorsod1" $ nfIO $ poorsod1 <$> generateInput (0, 1000) 1000,
      bench "poorsod2" $ nfIO $ poorsod2 <$> generateInput (0, 1000) 1000,
      bench "volkov" $ nfIO $ volkov <$> generateInput (0, 1000) 1000,
      bench "scvalex" $ nfIO $ scvalex <$> generateInput (0, 1000) 1000
    ]
  ]



generateInput :: (Int, Int) -> Int -> IO [Int]
generateInput range amount = 
  sequence $ replicate amount $ randomRIO range



poorsod1 :: Eq a => [a] -> [a]
poorsod1 = rdHelper []
    where rdHelper seen [] = seen
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs
              | otherwise = rdHelper (seen ++ [x]) xs

poorsod2 :: Eq a => [a] -> [a]
poorsod2 = foldl (\seen x -> if x `elem` seen
                              then seen
                              else seen ++ [x]) []

volkov :: Ord a => [a] -> [a]
volkov = rmdups' Set.empty where
  rmdups' _ [] = []
  rmdups' a (b : c) = if Set.member b a
    then rmdups' a c
    else b : rmdups' (Set.insert b a) c

scvalex :: (Ord a) => [a] -> [a]
scvalex = map head . group . sort

Results:

warming up
estimating clock resolution...
mean is 1.195021 us (640001 iterations)
found 105623 outliers among 639999 samples (16.5%)
  40 (6.3e-3%) low severe
  105583 (16.5%) high severe
estimating cost of a clock call...
mean is 54.63436 ns (8 iterations)

benchmarking input1/nub
mean: 1.099596 ms, lb 1.065199 ms, ub 1.139128 ms, ci 0.950
std dev: 188.9475 us, lb 167.9780 us, ub 224.5062 us, ci 0.950
variance introduced by outliers: 92.542%
variance is severely inflated by outliers

benchmarking input1/poorsod1
mean: 1.227700 ms, lb 1.195749 ms, ub 1.269022 ms, ci 0.950
std dev: 185.5354 us, lb 149.6931 us, ub 233.4706 us, ci 0.950
found 11 outliers among 100 samples (11.0%)
  7 (7.0%) high mild
  4 (4.0%) high severe
variance introduced by outliers: 90.433%
variance is severely inflated by outliers

benchmarking input1/poorsod2
mean: 1.160321 ms, lb 1.143508 ms, ub 1.179757 ms, ci 0.950
std dev: 92.10460 us, lb 80.62511 us, ub 109.1521 us, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high mild
variance introduced by outliers: 70.714%
variance is severely inflated by outliers

benchmarking input1/volkov
mean: 402.9525 us, lb 393.9295 us, ub 415.9713 us, ci 0.950
std dev: 55.22468 us, lb 41.38336 us, ub 71.07060 us, ci 0.950
found 9 outliers among 100 samples (9.0%)
  3 (3.0%) high mild
  6 (6.0%) high severe
variance introduced by outliers: 88.341%
variance is severely inflated by outliers

benchmarking input1/scvalex
mean: 739.7402 us, lb 723.3561 us, ub 762.2279 us, ci 0.950
std dev: 97.89011 us, lb 75.05276 us, ub 131.0033 us, ci 0.950
found 6 outliers among 100 samples (6.0%)
  4 (4.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 87.309%
variance is severely inflated by outliers

benchmarking input2/nub
mean: 4.187584 ms, lb 4.147268 ms, ub 4.256735 ms, ci 0.950
std dev: 265.0261 us, lb 173.1619 us, ub 395.4280 us, ci 0.950
found 8 outliers among 100 samples (8.0%)
  2 (2.0%) high mild
  6 (6.0%) high severe
variance introduced by outliers: 59.548%
variance is severely inflated by outliers

benchmarking input2/poorsod1
mean: 6.487255 ms, lb 6.399398 ms, ub 6.604789 ms, ci 0.950
std dev: 518.4923 us, lb 406.8715 us, ub 654.0022 us, ci 0.950
found 11 outliers among 100 samples (11.0%)
  5 (5.0%) high mild
  6 (6.0%) high severe
variance introduced by outliers: 70.732%
variance is severely inflated by outliers

benchmarking input2/poorsod2
mean: 6.797977 ms, lb 6.669138 ms, ub 6.954456 ms, ci 0.950
std dev: 724.6611 us, lb 621.6228 us, ub 893.3407 us, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high mild
variance introduced by outliers: 81.075%
variance is severely inflated by outliers

benchmarking input2/volkov
mean: 688.1596 us, lb 667.0059 us, ub 714.8911 us, ci 0.950
std dev: 121.0162 us, lb 100.1970 us, ub 151.6959 us, ci 0.950
found 10 outliers among 100 samples (10.0%)
  9 (9.0%) high mild
  1 (1.0%) high severe
variance introduced by outliers: 92.563%
variance is severely inflated by outliers

benchmarking input2/scvalex
mean: 1.104686 ms, lb 1.077867 ms, ub 1.130347 ms, ci 0.950
std dev: 134.1601 us, lb 111.9940 us, ub 164.9301 us, ci 0.950
found 9 outliers among 100 samples (9.0%)
  7 (7.0%) low mild
  2 (2.0%) high mild
variance introduced by outliers: 85.216%
variance is severely inflated by outliers

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.