Skip to content

@nikita-volkov /gist:5451343
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.