From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA10483; Fri, 7 Nov 2003 18:27:29 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA10424 for ; Fri, 7 Nov 2003 18:27:25 +0100 (MET) Received: from smtp2.mathworks.com (smtp2.mathworks.com [144.212.95.218]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA7HRN121752 for ; Fri, 7 Nov 2003 18:27:24 +0100 (MET) Received: from mail-vif.mathworks.com (fred-ce0.mathworks.com [144.212.95.18]) by smtp2.mathworks.com (8.11.7/8.11.7) with ESMTP id hA7HRJ826147; Fri, 7 Nov 2003 12:27:19 -0500 (EST) Received: from MESSAGE-AH.ad.mathworks.com (ex-01-ah.mathworks.com [144.212.95.156]) by mail-vif.mathworks.com (8.11.7/8.11.7) with ESMTP id hA7HRJj06184; Fri, 7 Nov 2003 12:27:19 -0500 (EST) X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: RE: [Caml-list] Efficient and canonical set representation? Date: Fri, 7 Nov 2003 12:27:19 -0500 Message-ID: Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOlRx8VdX2S7U1ZRhC1wVHtUQEboQADOmRg From: "Fred Smith" To: "Samuel Lacas" , X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 fsmith:01 mathworks:01 -fred:01 samuel:01 lacas:01 caml-list:01 -fred:01 hash:01 bug:01 faq:01 faq:01 beginner's:01 beginners:01 arrays:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Ocaml has a structural comparison function (<=3D) : 'a -> 'a -> bool. =20 But the bigger problem with this approach (as Jean-Baptiste Rouquier) = kindly pointed out to me is that insertion takes O(n), not O(log(n)) = time. Duh. -Fred > -----Original Message----- > From: owner-caml-list@pauillac.inria.fr=20 > [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Samuel Lacas > Sent: Friday, November 07, 2003 10:44 AM > To: caml-list@inria.fr > Subject: Re: [Caml-list] Efficient and canonical set representation? >=20 >=20 > Fred Smith a =E9crit 2.2K le Fri, Nov 07, 2003 at 10:27:25AM -0500: #=20 > # I guess what you're looking for are sorted arrays: > # 1) O(log n) lookup and insertion via binary search > # 2) O(n) union and intersection are simple > # 3) Equal sets are represented by structurally equivalent objects. > #=20 > # -Fred >=20 > Hmm, except that, if I'm not wrong, it was required the=20 > structure to hold any kind of object. Sorted arrays require=20 > the elements to be sortable. Using the hash of the objects=20 > may be an answer ? >=20 > sL >=20 > ------------------- > To unsubscribe, mail caml-list-request@inria.fr Archives:=20 http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs = FAQ: http://caml.inria.fr/FAQ/ Beginner's list: = http://groups.yahoo.com/group/ocaml_beginners ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners