From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>
To: johnh@ichips.intel.com
Cc: caml-list@inria.fr
Subject: RE: [Caml-list] Efficient and canonical set representation?
Date: Mon, 10 Nov 2003 14:24:35 +0100 (NFT) [thread overview]
Message-ID: <Pine.A41.4.44.0311101411020.4481052-100000@ibm1.cicrp.jussieu.fr> (raw)
In-Reply-To: <DB873318D1A41648BEAC4B5AAB63B3E101D0B8CD@MESSAGE-AH.ad.mathworks.com>
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
next prev parent reply other threads:[~2003-11-10 13:25 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-11-07 17:27 Fred Smith
2003-11-10 13:24 ` Diego Olivier Fernandez Pons [this message]
2003-11-10 13:49 ` [Caml-list] Rounding mode Christophe Raffalli
2003-11-10 14:10 ` Eric Dahlman
2003-11-10 18:03 ` Brian Hurt
2003-11-10 20:35 ` Eric Dahlman
2003-11-10 23:09 ` Brian Hurt
2003-11-17 21:15 ` Xavier Leroy
2003-11-12 17:19 ` Diego Olivier Fernandez Pons
2003-11-13 15:47 ` Eric Dahlman
2003-11-17 17:03 ` Diego Olivier Fernandez Pons
2003-11-10 21:23 ` Christophe Raffalli
[not found] ` <16305.25815.3793.545198@karryall.dnsalias.org>
2003-11-12 15:35 ` [Caml-list] Rounding mode + extended Christophe Raffalli
2003-11-13 17:35 ` Xavier Leroy
2003-11-10 19:28 ` [Caml-list] Efficient and canonical set representation? Julien Signoles
-- strict thread matches above, loose matches on Subject: below --
2003-11-12 17:18 Harrison, John R
2003-11-12 3:34 Harrison, John R
2003-11-12 7:50 ` Brian Hurt
2003-11-12 0:20 Harrison, John R
2003-11-12 2:04 ` Brian Hurt
2003-11-12 16:16 ` Diego Olivier Fernandez Pons
2003-11-07 15:27 Fred Smith
2003-11-07 15:44 ` Samuel Lacas
2003-11-08 16:50 ` Eray Ozkural
2003-11-07 14:15 Harrison, John R
2003-11-06 16:41 Harrison, John R
2003-11-06 17:04 ` Brian Hurt
2003-11-07 3:43 ` Eray Ozkural
2003-11-07 3:52 ` Eray Ozkural
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.A41.4.44.0311101411020.4481052-100000@ibm1.cicrp.jussieu.fr \
--to=diego.fernandez_pons@etu.upmc.fr \
--cc=caml-list@inria.fr \
--cc=johnh@ichips.intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).