FiniteMap performance

[Daan Leijen]

Dear Magnus,

> I wonder what the performance of
> the FiniteMap type is in Haskell. Lookup is of course done in O(log n)
> but is insertion done in O(n) or O(log n)?
...
> If it belongs to O(n), aren't the maps really really useless?
> If it belongs to O(log n), how is this achieved?
>   (my guess is that it is O(n) of course : )

I have once been thinking the same, but you can rest assured,
insert is O(log n)   (for a balanced tree map implementation).

A pure language must indeed copy its values (since it is a new one) but
it can also *share* values that stay the same. In the case of the
balanced tree, the "path" to the inserted node will be copied since they
consist of new and different nodes, but all the subtrees of this path stay
the same and will be shared among all new insertions. It is rather mind-boggling
when you start thinking about how the actual heap looks after a while, but
fortunately, you never have to think about that in Haskell :-) 
(btw. This is really fun to watch if you got a tool like the graphical Hood).

All the best,
    Daan.

ps. I have written a fairly extensive (and documented) data structure library 
called DData that has efficient Maps, Sets, Bags etc. Also works well with 
Hugs and other haskell98 compilers. http://www.cs.uu.nl/~daan/ddata.html



> 
> For example, does the function
> 
> addToFM :: Ord key => FiniteMap key elt ->
>                       key -> elt  -> FiniteMap key elt
> 
> belong to O(n) or O(log n) (where n is the size of the map) ?
> 
> If it belongs to O(n), aren't the maps really really useless?
> If it belongs to O(log n), how is this achieved?
>   (my guess is that it is O(n) of course : )
> 
> Best regards,
>   Magnus Lindberg
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
> 
>