RE: [Caml-list] Efficient and canonical set representation?

[Brian Hurt <bhurt@spnz.org>]

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