Hello, On Monday 09 Jan 2006 1:11 pm, Christian Maeder wrote:
Hi,
I wonder how well
http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Induct ive-Internal-FiniteMap.html
performs wrt. other Map implementations.
It may be worth replacing this implementation, too.
I suspect it doesn't compare too well with Data.Tree.AVL, though I've never measured it to be honest. It's based on "AVL trees" (or rather trees where left and right sub-tree heights differ by at most 1), but doesn't seem to use the AVL algorithm itself. IIRC it stores (boxed!) height in each tree node, not "balance factor". As well as requiring an extra field (same as Adams) this also causes other inefficiencies. Insertion requires inspection of nodes which aren't on the insertion path to determine the balance factor, which has gotta slow things down. That said, it should still do a pretty good job of balancing and the balancing mechanism itself and node size will have little impact on look up times (for example). It'd be worth a look at to see what functions this provides that weren't provided by the old FiniteMap implementation, and whether or not these are still absent from Data.Map (I believe this was the original motivation for FGL having it's own private implementation in the first place). Regards -- Adrian Hey