dict order

[A.T.Hofkamp]

On 2008-06-18, Robert Bossy <Robert.Bossy at jouy.inra.fr> wrote:
> Lie wrote:
>>> Whoops, I think I misunderstood the question. If what you're asking
>>> whether two dictionary is equal (equality comparison, rather than
>>> sorting comparison). You could do something like this:
>>>     
> Testing for equality and finding differences are trivial tasks indeed. 
> It is the sort order I'm interested in. The meaning of the order is not 
> really an issue, I'm rather looking for a consistent comparison function 
> (in the __cmp__ sense) such as:
>     if d1 > d2 and d2 > d3,
>     then d1 > d3
>
> I'm not sure the hashing method suggested by Albert guarantees that.

I read the post as the desire to test equality between dictionary-like data
structures. With some care (see below) (and the ability to compute the hash
fast), you could use hashing as way to decide that two such structures are not
equal.

Afaik you cannot use hashing for testing order ('<' or '>'). If I gave that
impression, sorry; it was not my intention.


In the equality case, you need special care with computing the hash
value of the keys (and values), since you want to have the same hash result
of the dictionary independent of the order of the keys.
One way of achieving that is to use XOR (^) to combine hash-values of the
elements. Unfortunately, XOR may not always produce good hash values.



If you want ordered dictionaries (as in you can compare dictionaries with each
other, and decide which is larger), I'd suggest to keep the keys of the
dictionaries sorted. Dictionary comparing can then be done by comparing keys in
increasing order (for example). If you encounter two non-equal keys, you
immediately can use the order of those two keys as the order of the
dictionaries.
(ie the order of two dictionaries is decided by the order of the first
non-equal keys). This gives you the transitive property (d1 > d2 and d2 > d3
implies d1 > d3).

(and len() is a cheap first order filter here; dictionaries are ordered by
length first, and by first non-equal keys second then.)

I have used this trick to define ordered sets (which are basically dictionaries
without value part). It worked like a charm.

Sincerely,
Albert