Hello,
On Mon, 2008-04-21 at 09:38 +0200, Milan Straka wrote:
It is difficult to measure these things in Haskell for me (just adding a SPECIALIZE of increasing/decreasing heap size can change order of execution time), but anyway, here are times of 50000 sequential inserts, then 800000 lookups and 50000 deletes (the source is attached for the freaks): Data.Set with \delta=4 180 300 72 Data.Set with \delta=5 208 304 76 Data.Map with \delta=4 212 328 84 Data.Map with \delta=5 256 324 88 IntSet 56 356 48 IntMap 56 360 48
Sorry, I'm confused, what are the columns here exactly?
Sorry, I should made myself more clear. The first column is the time of 50000 sequential inserts ([1..50000]), the second column is the time of 800000 lookups [bigger number because they are fast, 800k=16*50k], the third column is the time od 50000 sequential deletes ([1..50000]). Everything is measured in ms. One can think of a test with random sequence -- the source can be modified easily to support it. The results are (in the same formatting) Random seq; Data.Set with \delta=4 300 636 256 Random seq; Data.Set with \delta=5 300 644 256 Random seq; Data.Map with \delta=4 372 692 268 Random seq; Data.Map with \delta=5 376 700 272 Random seq; IntSet 216 572 168 Random seq; IntMap 228 584 176 As one should expect, they are inconclusive. Thats because when the data inserted are truly random, the rebalancing is not really needed. (What is more interesting is the time bloat of all tests. I think it might be caused by being able to inline [1..50000] better than random list... Maybe a list fusion? I do not really know.) Hello, Milan PS: Here is a diff of the random test: --- Test.hs 2008-04-21 09:33:55.000000000 +0200 +++ TestNew.hs 2008-04-21 13:17:21.000000000 +0200 @@ -8,10 +8,17 @@ import System.CPUTime +import System.Random force_list list = sum list {-# SPECIALIZE force_list::[Int]->Int #-} +gen_rnd n = rnd (mkStdGen 42) (Map4.fromList [(b,0)|b<-[1..n]]) where + rnd g m | Map4.null m = [] + rnd g m = let n = Map4.size m + (i,g') = randomR (0,n-1) g + in fst (Map4.elemAt i m) : rnd g' (Map4.deleteAt i m) + test::Int->c->(Int->c->c)->(Int->c->Bool)->(Int->c->c)->(c->[Int])->IO () @@ -20,23 +27,23 @@ test n cs insert find delete tolist = do - let ls=[1..n] + let ls=gen_rnd n ts<-force_list ls `seq` getCPUTime