English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
RE: [Caml-list] Efficient and canonical set representation?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-11-12 (06:51)
From: Brian Hurt <bhurt@s...>
Subject: RE: [Caml-list] Efficient and canonical set representation?
On Tue, 11 Nov 2003, Harrison, John R wrote:

> | I've been batting around ideas for ways to do balanced trees so that no 
> | matter what order you add things, you always get the same tree.  But even 
> | assuming you could do this, doing a structural compare is still O(N).  So 
> | you might as well let the trees be different.
> Right, but see my second message --- I'm only interested in canonicity
> up to structural equality and I'm happy with O(N) comparison. So it's
> just the "no matter what order you add things you get the same tree"
> property that I care about. But it's not yet obvious to me whether I
> can even achieve that much.

It feels like that can be done, at the cost of an occassional O(N) 
"massive rebalancing".  Well, it certainly can be done with an O(N) 
insert/delete.  I'll think about it a bit.

"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 

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