Skip to content

Instantly share code, notes, and snippets.

@mbrcknl
Last active August 29, 2015 14:06
Show Gist options
  • Save mbrcknl/a998a97aa1dcf4b9adfd to your computer and use it in GitHub Desktop.
Save mbrcknl/a998a97aa1dcf4b9adfd to your computer and use it in GitHub Desktop.
-- Is Set.union better than O(n+m) in some cases?
import Criterion.Main (Benchmark, bench, bgroup, defaultMain, env, whnf)
import Data.Set (Set, fromList, union)
main :: IO ()
main = defaultMain [ bgroup "union" $ map benchUnion sizes ]
-- Grow Set size exponentially, under the hypothesis that
-- Set.union will be O(log n) in this special case.
sizes :: [(Int,Int)]
sizes = take 10 $ zip [0..] $ iterate (*2) 2048
-- We take the special case where the largest element in
-- the first set is smaller than the smallest element in
-- the second set. In this case, union should reduce to
-- concatenation and rebalance.
inputs :: Int -> IO (Set Int, Set Int)
inputs n = return (fromList [1..n], fromList [n+1..2*n])
-- Be careful to fully construct the input sets before
-- we start measuring.
benchUnion :: (Int,Int) -> Benchmark
benchUnion (i,n) = env (inputs n) $ bench (show i) . whnf (uncurry union)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment