From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id D53C1BC8E for ; Fri, 25 Feb 2005 23:35:13 +0100 (CET) Received: from ptb-relay01.plus.net (ptb-relay01.plus.net [212.159.14.212]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1PMZDQR011652 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 25 Feb 2005 23:35:13 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay01.plus.net with esmtp (Exim) id 1D4o3F-000ECn-3s for caml-list@yquem.inria.fr; Fri, 25 Feb 2005 22:35:13 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Complexity of Set.union Date: Fri, 25 Feb 2005 22:36:35 +0000 User-Agent: KMail/1.7.1 References: <200502240920.04902.jon@jdh30.plus.com> <200502251947.46657.jon@jdh30.plus.com> <7f8e92aa0502251350202ec368@mail.gmail.com> In-Reply-To: <7f8e92aa0502251350202ec368@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502252236.35567.jon@jdh30.plus.com> X-Miltered: at concorde with ID 421FA821.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 inputs:01 overwritten:01 non-trivial:01 const:01 height:98 height:98 ...:98 frog:98 structures:01 imperative:01 data:02 purely:02 in-place:02 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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