From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 257B6D17A for ; Wed, 27 Jul 2005 11:43:00 +0200 (CEST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6R9gxm9022700 for ; Wed, 27 Jul 2005 11:43:00 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id j6R9gt22096131 ; Wed, 27 Jul 2005 11:42:55 +0200 (CEST) X-Ids: 164 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id LAA43878 ; Wed, 27 Jul 2005 11:39:07 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id LAA2289784 ; Wed, 27 Jul 2005 11:42:22 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Wed, 27 Jul 2005 11:42:21 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Set union/inter/diff efficiency In-Reply-To: <200507271012.02020.jon@ffconsultancy.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.164]); Wed, 27 Jul 2005 11:42:55 +0200 (CEST) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at nez-perce with ID 42E75723.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 42E7571F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 caml-list:01 filliatre:01 lazy:01 intersection:01 pointers:01 intersection:01 implements:01 sml:01 haskell:01 quicker:98 ...:98 ...:98 overlap:01 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 Bonjour, > Does anyone have any ideas or references on how the union/inter/diff > functions of the Set module could be optimised by accepting a > sequence of sets rather than a pair at a time ? No. > For example, if A overlaps B overlaps C but A does not overlap C > then it is probably quicker to compute the union "(A U C) U B" > rather than "A U B U C". I remember having discussed with Jean-Christophe Filli=E2tre of the [compare] implementation of Xavier Leroy. He noticed that it was a smart lazy linearization of both sets. In other words you can see it as if one had put a zipper on each set and one calls when needed the [next] function. A =3D 3 -> 5 -> 6 -> 7 -> 10 B =3D 3 -> 6 -> 8 -> 13 You can say that A < B at the second call of [next] I suppose you could do a similar thing for union and intersection with several sets A =3D 3 -> 5 -> 6 -> 7 -> 10 B =3D 3 -> 6 -> 8 -> 13 C =3D 2 -> 4 -> 5 -> 6 You can call [next] in such a way that the pointers "jump" to an interesting point. Here, it would be something like max/min =3D 3 C -> 4 (first integer >=3D 3) max/min =3D 4 A -> 5 (first integer >=3D 4) max/min =3D 5 B -> 6 (first integer >=3D 5) max/min =3D 6 C -> 6 (...) A -> 6 (...) =3D> output 6 in the intersection > Better still, does anyone have a replacement Set module which > implements this functionality? I am not aware of any in Caml, SML or Haskell but I may be wrong. Diego Olivier