This is fun to play with! I know it’s not a real benchmark but still, it’s interesting to implement various algorithms and then check whether you guessed the complexity right.
This time, I wanted to test various sorting implementations:
-
Data.List.sort: should be O(n log n) with small constant because it uses several optimizations
- Naive
QuickSort: should be O(n log n) on a random list
- Top-down
mergeSort with the split in the middle: should be O(n log n) with big constant
- Top-down
mergeSort with split by even-odd: should be O(n log n) with smaller constant
- Bottom-up
mergeSort: should be O(n log n)
- Sort based on
IntMap: should be close to O(n)
Suprisingly, the results are not deterministic, and different runs produce different asymptotics. So I run every algorithm twice from GHCi:
-- Data.List.sort
ghci> fit $ mkFitConfig (Data.List.sort . mkList) (10, 10000)
7.0969e-9 * x * log ^ 2 x
ghci> fit $ mkFitConfig (Data.List.sort . mkList) (10, 10000)
1.0800e-7 * x ^ 1.1837
-- Quick Sort
ghci> fit $ mkFitConfig (quickSort . mkList) (10, 10000)
2.8411e-7 * x * log x
ghci> fit $ mkFitConfig (quickSort . mkList) (10, 10000)
2.8529e-7 * x * log x
-- Merge Sort (with split in the middle)
ghci> fit $ mkFitConfig (mergeSortWithLength . mkList) (10, 10000)
4.7956e-7 * x * log x
ghci> fit $ mkFitConfig (mergeSortWithLength . mkList) (10, 10000)
5.6328e-8 * x * log ^ 2 x
-- Merge Sort (with the split by even-odd)
ghci> fit $ mkFitConfig (mergeSortEvenOdd . mkList) (10, 10000)
5.2711e-7 * x * log x
ghci> fit $ mkFitConfig (mergeSortEvenOdd . mkList) (10, 10000)
6.1624e-8 * x * log ^ 2 x
-- Merge Sort (bottom up)
ghci> fit $ mkFitConfig (mergeSortBottomUp . mkList) (10, 10000)
4.1648e-7 * x * log x
ghci> fit $ mkFitConfig (mergeSortBottomUp . mkList) (10, 10000)
8.2759e-7 * x ^ 1.1684
-- Int Sort
ghci> fit $ mkFitConfig (intSort . mkList) (10, 10000)
6.3846e-8 * x * log x
ghci> fit $ mkFitConfig (intSort . mkList) (10, 10000)
2.3924e-7 * x ^ 1.0959
And here’s full code:
{-# OPTIONS_GHC -O0 #-}
module Main where
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import Data.List (sort, partition, foldl')
import Test.Tasty.Bench.Fit (fit, mkFitConfig)
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x : xs) =
let (less, greater) = partition (< x) xs
in quickSort less ++ (x : quickSort greater)
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x : xs) (y : ys) = case compare x y of
EQ -> x : y : merge xs ys
LT -> x : merge xs (y : ys)
GT -> y : merge (x : xs) ys
mergeSortWithLength :: Ord a => [a] -> [a]
mergeSortWithLength [] = []
mergeSortWithLength [x] = [x]
mergeSortWithLength xs =
let (l, r) = splitAt (length xs `div` 2) xs
in merge (mergeSortWithLength l) (mergeSortWithLength r)
mergeSortEvenOdd :: Ord a => [a] -> [a]
mergeSortEvenOdd [] = []
mergeSortEvenOdd [x] = [x]
mergeSortEvenOdd xs =
let (l, r) = splitEvenOdd id id xs
in merge (mergeSortWithLength l) (mergeSortWithLength r)
where
splitEvenOdd :: ([a] -> [a]) -> ([a] -> [a]) -> [a] -> ([a], [a])
splitEvenOdd mkL mkR [] = (mkL [], mkR [])
splitEvenOdd mkL mkR [x] = (mkL [x], mkR [])
splitEvenOdd mkL mkR (x : y : xs) = splitEvenOdd (mkL . (x :)) (mkR . (y :)) xs
mergeSortBottomUp :: Ord a => [a] -> [a]
mergeSortBottomUp = mergeLists . map (:[])
where
mergeLists :: Ord a => [[a]] -> [a]
mergeLists [] = []
mergeLists [x] = x
mergeLists xs = mergeLists $ mergePairs xs
mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs [x] = [x]
mergePairs (x : y : ys) = merge x y : mergePairs ys
intSort :: [Int] -> [Int]
intSort = unfold . compress
where
compress :: [Int] -> IntMap Int
compress = foldl' (\acc x -> IntMap.insertWith (+) x 1 acc) mempty
unfold :: IntMap Int -> [Int]
unfold = concatMap (\(x, frequency) -> replicate frequency x) . IntMap.toAscList
mkList :: Int -> [Int]
mkList n = take n $ iterate (\n -> n * 6364136223846793005 + 1) n
