Re: [Caml-list] Complexity of Set.union

[Jon Harrop <jon@jdh30.plus.com>]

On Friday 25 February 2005 21:50, Radu Grigore wrote:
> > > Did you mean "of two equal height sets such that all elements of the
> > > first set are smaller than all elements of the second set"?
> >
> > Yes, that's what I meant. :-)
>
> In that case the current Set.union simply adds elements repeatedly
> from the set with small height to the set with big height.

Yes, I agree with everything you said.

> > Having said that, wouldn't it take the Set.union function O(log n + log
> > N) time to prove that the inputs are non-overlapping, because it would
> > have to traverse to the min/max elements of both sets?
>
> I agree. Also, such a check looks ugly to me (for a standard library).

I think I agree here too. Assuming that such special cases cannot be handled 
without incurring a performance cost (which I'm not sure about), I'd 
definitely go for the simplest code.

Regarding Don's question about what an imperative programmer would have to do 
to write efficient code. My interpretation is now that they would have to 
work out which of the data structures they could destroy. Then they would 
have to convert the purely functional implementation into one which performs 
in-place operations.

This is fairly easy in the case of my "nth" program because the main function 
"accumulates" its result and, therefore, this accumulator can be overwritten. 
I can imagine it quickly becoming a headache though. For example, if there 
were any non-trivial branches in the middle of the function.

Whilst writing the C++ implementation I remembered how I first became 
interested in functional programming - I noticed that I could only write 
correct C++ programs when I littered everything with "const". :-)

I'll post my detailed performance analysis when its done...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://ffconsultancy.com