From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 4ACADD560 for ; Wed, 27 Jul 2005 19:32:22 +0200 (CEST) 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 j6RHWLkp021897 for ; Wed, 27 Jul 2005 19:32:22 +0200 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 TAA25646 for ; Wed, 27 Jul 2005 19:32:21 +0200 (MET DST) Received: from wetware.wetware.com (wetware.wetware.com [209.218.58.1]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6RHWKh8006995 for ; Wed, 27 Jul 2005 19:32:21 +0200 Received: from [69.12.155.90] (helo=[10.0.1.5]) by wetware.wetware.com with esmtp (Exim 4.43) id 1DxplT-0005k7-SS for caml-list@inria.fr; Wed, 27 Jul 2005 10:32:19 -0700 Mime-Version: 1.0 (Apple Message framework v733) In-Reply-To: <3746DD19-1AD1-43A9-9A8C-2D934E543C4D@wetware.com> References: <200507271012.02020.jon@ffconsultancy.com> <133225B6-7E0E-4FAE-9EFA-4AE9650BDD3E@wetware.com> <3746DD19-1AD1-43A9-9A8C-2D934E543C4D@wetware.com> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <46A5845F-0614-4C7C-9610-7DA749A8DBE7@wetware.com> Content-Transfer-Encoding: 7bit From: james woodyatt Subject: Re: [Caml-list] Set union/inter/diff efficiency Date: Wed, 27 Jul 2005 10:32:18 -0700 To: Ocaml Trade X-Mailer: Apple Mail (2.733) X-Miltered: at concorde with ID 42E7C525.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42E7C524.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; woodyatt:01 jhw:01 wetware:01 caml-list:01 woodyatt:01 sequences:01 seq:01 heap:01 heap:01 sequences:01 unify:01 intersection:01 jhw:01 wetware:01 2005,:98 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On 27 Jul 2005, at 10:00, james woodyatt wrote: > On 27 Jul 2005, at 09:04, james woodyatt wrote: >> >> Load into a queue. >> While queue is not empty, > > Okay, a queue is the wrong idea. The right idea would be somewhat > trickier loop over the sequence of element sequences to catch the > union elements in the right order. And I neglected to mention that > you'd need to build the result set with [Cf_set.of_incr_list]. Dammit. I can't do anything right this morning. I'm pretty sure you can get what you want with a combination of different things in my Cf library, e.g. Cf_seq, Cf_heap and Cf_set. For union: Convert the sets into a heap of element sequences. Loop through the heap to unify into a single element sequence. Build a new set from the unified element sequence. For difference and intersection: I'd have to think about it some more. -- j h woodyatt markets are only free to the people who own them.