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 QAA06592; Fri, 7 Nov 2003 16:44:31 +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 QAA06556 for ; Fri, 7 Nov 2003 16:44:30 +0100 (MET) Received: from mailhost.trusted-logic.fr (mailhost.trusted-logic.fr [194.250.150.5]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA7FiT110716 for ; Fri, 7 Nov 2003 16:44:29 +0100 (MET) Received: from ouessant.trusted-logic.fr (ouessant.trusted-logic.fr [192.168.1.201]) by mailhost.trusted-logic.fr (Postfix) with ESMTP id 1EC5DE0 for ; Fri, 7 Nov 2003 16:44:29 +0100 (CET) Received: (from lacas@localhost) by ouessant.trusted-logic.fr (8.9.3/8.9.3) id QAA32008 for caml-list@inria.fr; Fri, 7 Nov 2003 16:44:29 +0100 Date: Fri, 7 Nov 2003 16:44:28 +0100 From: Samuel Lacas To: caml-list@inria.fr Subject: Re: [Caml-list] Efficient and canonical set representation? Message-ID: <20031107164428.B11780@ouessant.trusted-logic.fr> References: Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0pre3us In-Reply-To: X-Send-From: ouessant.trusted-logic.fr X-Operating-System: Linux ouessant.trusted-logic.fr 2.2.19 X-Loop: caml-list@inria.fr X-Spam: no; 0.00; samuel:01 lacas:01 samuel:01 lacas:01 caml-list:01 -fred:01 hash:01 arrays:01 arrays:01 ecrit:01 nov:01 binary:02 objects:02 objects:02 canonical:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Fred Smith a écrit 2.2K le Fri, Nov 07, 2003 at 10:27:25AM -0500: # # 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. # # -Fred Hmm, except that, if I'm not wrong, it was required the structure to hold any kind of object. Sorted arrays require the elements to be sortable. Using the hash of the objects may be an answer ? sL ------------------- 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