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 656D2BC75 for ; Fri, 25 Feb 2005 18:48:57 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1PHmuZY012443 for ; Fri, 25 Feb 2005 18:48:57 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA20458 for ; Fri, 25 Feb 2005 18:48:56 +0100 (MET) Received: from yquem.inria.fr (yquem.inria.fr [128.93.8.37]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j1PHmrJB026546; Fri, 25 Feb 2005 18:48:53 +0100 Received: by yquem.inria.fr (Postfix, from userid 18180) id 7DB52BC75; Fri, 25 Feb 2005 18:48:53 +0100 (CET) Date: Fri, 25 Feb 2005 18:48:53 +0100 From: Xavier Leroy To: Jon Harrop Cc: caml-list@inria.fr Subject: Re: [Caml-list] Set union Message-ID: <20050225174853.GA25527@yquem.inria.fr> References: <200502240920.04902.jon@jdh30.plus.com> <7f8e92aa05022502566909d86@mail.gmail.com> <200502251730.13003.jon@jdh30.plus.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200502251730.13003.jon@jdh30.plus.com> User-Agent: Mutt/1.3.28i X-Miltered: at concorde with ID 421F6509.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 421F6505.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 mistaken:01 trivial:01 achieves:01 intuitively:01 trivial:01 ocaml's:01 achieves:01 height:98 height:98 node:01 short:01 constructor:01 behaviour:01 algorithm: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: [ Complexity of Set.union ] > > For other cases > > the process is a bit more complex: take the root of the short tree, > > split the large tree into smaller/larger elements based on that root, > > compute union of "small" trees, "compute union of "large" trees", > > merge them. If I'm not mistaken this is O(m lg n) too. 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. 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. > 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"? 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. - Xavier Leroy