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 BAA25997; Wed, 12 Nov 2003 01:21:02 +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 BAA26227 for ; Wed, 12 Nov 2003 01:21:01 +0100 (MET) Received: from caduceus.jf.intel.com (fmr06.intel.com [134.134.136.7]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hAC0Kx117495 for ; Wed, 12 Nov 2003 01:21:00 +0100 (MET) Received: from petasus.jf.intel.com (petasus.jf.intel.com [10.7.209.6]) by caduceus.jf.intel.com (8.12.9-20030918-01/8.12.9/d: outer.mc,v 1.66 2003/05/22 21:17:36 rfjohns1 Exp $) with ESMTP id hAC0L7vn012374 for ; Wed, 12 Nov 2003 00:21:08 GMT Received: from orsmsxvs041.jf.intel.com (orsmsxvs041.jf.intel.com [192.168.65.54]) by petasus.jf.intel.com (8.11.6-20030918-01/8.11.6/d: inner.mc,v 1.35 2003/05/22 21:18:01 rfjohns1 Exp $) with SMTP id hAC0F7I03705 for ; Wed, 12 Nov 2003 00:15:07 GMT Received: from orsmsx332.amr.corp.intel.com ([192.168.65.60]) by orsmsxvs041.jf.intel.com (NAVGW 2.5.2.11) with SMTP id M2003111116205506142 ; Tue, 11 Nov 2003 16:20:55 -0800 Received: from orsmsx409.amr.corp.intel.com ([192.168.65.58]) by orsmsx332.amr.corp.intel.com with Microsoft SMTPSVC(5.0.2195.5329); Tue, 11 Nov 2003 16:20:55 -0800 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 Subject: RE: [Caml-list] Efficient and canonical set representation? Date: Tue, 11 Nov 2003 16:20:55 -0800 Message-ID: <3C4C3612EC443546A33E57003DB4F0F914C273@orsmsx409.jf.intel.com> Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOnjwp30JaqHqZ7SIO3d9diyCVX8wBG0EJQ From: "Harrison, John R" To: "Diego Olivier Fernandez Pons" Cc: , "Harrison, John R" X-OriginalArrivalTime: 12 Nov 2003 00:20:55.0955 (UTC) FILETIME=[D6E60630:01C3A8B2] X-Scanned-By: MIMEDefang 2.31 (www . roaringpenguin . com / mimedefang) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 johnh:01 hash:01 hashing:01 worst-case:01 red-black:01 pons:01 caml-list:01 hash:01 hypothesis:01 bug:01 faq:01 faq:01 beginner's:01 beginners:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk That seems to be the best suggestion so far. I guess it would work well in practice. But theoretically it still doesn't give O(log n) lookup and insertion without the kinds of assumptions you noted about the distribution of elements w.r.t. the hash function. And relying on polymorphic hashing seems a bit of a hack. So I still can't help wondering if there's an elegant solution with the desired worst-case behaviour, preferably relying only on pairwise comparison. Is it just a coincidence that the numerous varieties of balanced tree (AVL, 2-3-4, red-black, ...) all seem to be non-canonical? Or is it essential to their efficiency? (Perhaps this is a question for another forum.) John. -----Original Message----- From: owner-caml-list@pauillac.inria.fr [mailto:owner-caml-list@pauillac.inria.fr]On Behalf Of Diego Olivier Fernandez Pons Sent: Monday, November 10, 2003 5:25 AM To: Harrison, John R Cc: caml-list@inria.fr Subject: RE: [Caml-list] Efficient and canonical set representation? Bonjour, > After your remarks and Brian's, I'm starting to wonder if it is > possible at all to do what I want. Maybe I should be looking for an > impossibility proof instead... Patricia sets seem to be what you are looking for. (1). Efficient usual operations (lookup, insertion, union) (2). Structural equality Their only problem is that they cannot handle polymorphic orderable types but only integers... Hash the data, use this key to insert it in a patricia map and solve the collisions by chaining in an ordered list (with the polymorphic [compare] function). (1) and (2) still hold under usual hypothesis on the rate of collisions. A few changes to JCF's implementation should be enough. Diego Olivier ------------------- 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 ------------------- 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