This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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 (01:05) From: Brian Hurt Subject: RE: [Caml-list] Efficient and canonical set representation?
```On Tue, 11 Nov 2003, Harrison, John R wrote:

> 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.)

I don't think so.

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.  Note that Patricia trees,
as I understand them, don't save you here either.  Mathematically, two
sets A and B are equal if every element in set A is in set B and vice
versa.

Think about it for a moment.  Assume we have a tree strucutre:
type 'a node_t = Node of 'a * 'a node_t * 'a node_t | Empty

Now, assume the code magically keeps the trees balanced exactly the same
way.  How would you do the comparison?

let rec equals a b =
match a, b with
Empty, Empty -> true
| Node(a_data, a_left, a_right), Node(b_data, b_left, b_right) ->
(a_data == b_data) && (equals a_left b_left) &&
(equals a_right b_right)
| _ -> false
;;

This is an O(N) algorithm still.

The only way I can think of to make pointer equivelence meaningfull is to
keep some structure of all the structures currently in use in the
background.  Then you have to search this structure on every insertion or
deletion to see if the new set is equal (using the old O(N) comparison) to
an already existing set.  This structure could be a tree as well, but this
still makes insertion and deletion O(N log M) (where M is the number of
structures currently in use).  Instead of just O(log N).  Much worse.

There are ways you can make comparison faster.  For example, keep the
number of elements handy in the structure (O(1) length operation) and just
compare the lengths before doing anything else.  If you can hash the
objects, you can keep a hash of the entire structure, being the sum of the
hashes of the individual elements (updating the hash is then O(1) on
insert or delete).  If the hashs don't match, the structures are
gaurenteed to be different.  And, obviously, if pointer comparison is
equal, the structures are equal.  Note that you always have cases where
you have to do an O(N) comparison.

I think you're SOL.

--
"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
Brian

-------------------
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

```