Tree Wars, IntMap strikes back.

[JP Bernardy]

--- Simon Marlow <simonmar at microsoft.com> wrote:

> Interesting, I get pretty much the same results as
> you, except that
> DData.Map is now quicker on the lookup test than
> both FiniteMap and AVL
> (0.120 vs. 0.134 and 0.138 respectively).

Ok, so that means that I should merge in the last
change by Daan (and in IntSet too)? 

(patch in extenso at the end of the message)

> I'm not going to investigate this any further,
> because it'll take
> forever to get to the bottom of.  I think we've
> arrived at a reasonable
> conclusion, that the old FiniteMap is definitely
> superceded but there
> isn't a clear choice between the others, so we
> should provide them all.
> 
> How about the following modules:
> 
>   Data.Map      -- a default implementation of maps,
> eg. DData.Map
>   Data.Map.AVL  -- same interface, based on AVL
> trees
>   Data.Map.Int  -- current DData.IntMap

DData.IntMap isn't exactly a drop in replacement for
DData.Map. It can't have the same interface, if only
because the data types are not the same kind.
So, I'm not sure it should be treated the same as AVL.

Cheers,
JP.

----------------------------------------------

hunk ./DData/IntMap.hs 263
+  = let nk = natFromInt k  in seq nk (lookupN nk t)
+
+lookupN :: Nat -> IntMap a -> Maybe a
+lookupN k t
hunk ./DData/IntMap.hs 269
-        | nomatch k p m -> Nothing
-        | zero k m      -> lookup k l
-        | otherwise     -> lookup k r
+        | zeroN k (natFromInt m) -> lookupN k l
+        | otherwise              -> lookupN k r
hunk ./DData/IntMap.hs 272
-        | (k==kx)   -> Just x
-        | otherwise -> Nothing
+        | (k == natFromInt kx)  -> Just x
+        | otherwise             -> Nothing
hunk ./DData/IntMap.hs 1102
+zeroN :: Nat -> Nat -> Bool
+zeroN i m = (i .&. m) == 0
+
hunk ./Makefile 52
+Test.o : Test.hs
+Test.o : ./DData/IntSet.hi
}





	
		
__________________________________
Do you Yahoo!?
Friends.  Fun.  Try the all-new Yahoo! Messenger.
http://messenger.yahoo.com/