Minor inefficiency in Data.Map and Data.Set?

[Neil Mitchell]

Hi Tyson,

Whenever I see the word inefficiency, I look for the benchmark that
proves it :-)

Have you benchmarked these two alternatives? If you can show that
there is a measurable difference I'm sure someone will sit up and take
note. Personally, I know nothing about the code involved, so you'd
need to find someone who did to check your optimisation is valid (if
it makes things go faster)

Thanks, Neil

On Mon, Dec 21, 2009 at 5:38 AM, Tyson Whitehead <twhitehead at gmail.com> wrote:
> I was looking at the Data.Map and Data.Set implementations and I think there
> is a slight inefficiency.  Consider the Data.Map code
>
> {--------------------------------------------------------------------
>  [glue l r]: glues two trees together.
>  Assumes that [l] and [r] are already balanced with respect to each other.
> --------------------------------------------------------------------}
> glue :: Map k a -> Map k a -> Map k a
> glue Tip r = r
> glue l Tip = l
> glue l r
>  | size l > size r = let ((km,m),l') = deleteFindMax l in balance km m l' r
>  | otherwise       = let ((km,m),r') = deleteFindMin r in balance km m l r'
>
> The call to balance should not be needed as subtracting one item from the non-
> smaller of them cannot thrown them out of balance given they are already in
> balance with one another.  The only way they could be made out of balance
> would be to subtract an item for smaller one.  The replacement code is
>
> glue l r
>  | sizeL > sizeR = let ((km,m),l') = deleteFindMax l in Bin sizeX km m l' r
>  | otherwise     = let ((km,m),r') = deleteFindMin r in Bin sizeX km m l r'
>  where
>    sizeL = size l
>    sizeR = size r
>    sizeX = sizeL + sizeR
>
> The Data.Set code is identical except for the key.
>
> Cheers!  -Tyson
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>