Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- fromList :: Ord a => Int -> [a] -> Treap a
- fromList seed xs = foldl insert (empty seed) xs
- empty :: Int -> Treap a
- empty seed = Treap (R.mkStdGen seed) Leaf
- height :: Treap a -> Int
- height = height' . extractBranch
- where
- height' Leaf = 0
- height' (Branch left x y right) = 1 + max (height' left) (height' right)
- buildTreeAndGetData :: [Int] -> R.StdGen -> (Int, Int)
- buildTreeAndGetData arr rng = (h, c)
- where
- (seed, rng') = R.next rng
- tr = fromList seed arr
- h = height tr
- c = member tr $ (fst $ R.next rng) `mod` 1000
- printData :: [Int] -> IO()
- printData arr = do
- rng <- R.newStdGen
- let d@(h, c) = buildTreeAndGetData arr rng
- print d
- runBenchmark :: Int -> IO()
- runBenchmark nodeCount = do
- printData [1..nodeCount]
- main = mapM_ runBenchmark [1000, 2000..10000]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement