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 81361BC75 for ; Fri, 25 Feb 2005 20:46:26 +0100 (CET) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1PJkPiJ027207 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 25 Feb 2005 20:46:26 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay03.plus.net with esmtp (Exim) id 1D4lPs-0007h9-PU for caml-list@yquem.inria.fr; Fri, 25 Feb 2005 19:46:24 +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 19:47:45 +0000 User-Agent: KMail/1.7.1 References: <200502240920.04902.jon@jdh30.plus.com> <200502251730.13003.jon@jdh30.plus.com> <20050225174853.GA25527@yquem.inria.fr> In-Reply-To: <20050225174853.GA25527@yquem.inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502251947.46657.jon@jdh30.plus.com> X-Miltered: at concorde with ID 421F8092.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 derivation:01 stl:01 inserting:01 ocaml:01 ocaml:01 vastly:01 ocaml's:01 corresponds:01 unions:01 trivial:01 achieves:01 intuitively:01 trivial:01 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 17:48, Xavier Leroy wrote: > My hope is that union takes time O(N log N) where N is the sum of the > numbers of elements in the two sets. I'm thoroughly unable to prove > that, though, in particular because the complexity of the "split" > operation is unclear to me. Am I correct in thinking that your derivation of this assumes roughly equal-sized sets and that your complexity could be tightened a bit by using the two different set cardinalities explicitly? I ask this because the STL set_union is probably O(n+N) (inserting an already sorted range into a set is apparently linear) which is worse than the O((n+N) log(n+N)) which you've suggested for OCaml. But my OCaml code is vastly faster, so OCaml's complexity seems to be significantly better than that. At least in the special case of one small and one large set, which my code is bound by. Specifically, the sets have O(1) and O(i^2) elements when looking for the "i"th nearest neighbour. In reality this corresponds to computing the unions of sets containing 4 elements with sets containing 10^4 elements. Hmm, now that I come to think of it, my performance measurements have all been specific to silicon (that's where the 4 comes from). I'll try retiming on some other atomic structures, where the small sets will contain about 12 elements. I predict the OCaml code will do better relative to the C++ code, because the smaller sets won't be so small... > This bound is "reasonable", however, in that the trivial union > algorithm (repeatedly add every element of one of the sets to the > other one) achieves this bound, and the trick with "joining" is, > intuitively, just an optimization of this trivial algorithm. I see. This could be improved in the unsymmetric case, by adding elements from the smaller set to the larger set. But the size of the set isn't stored so you'd have to make do with adding elements from the shallower set to the deeper set. I've no idea what the complexity of that would be... As I know which of the two sets will be the larger and which will be the smaller, I'll try a customized union function which folds Set.add over the smaller set. > > Now, what about best case behaviour: In the case of the union of two > > equal height, distinct sets, is OCaml's union T(1)? > > 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. :-) > That > could indeed run in constant time (just join the two sets with a > "Node" constructor), but I doubt the current implementation achieves > this because of the repeated splitting. 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? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://ffconsultancy.com