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