dict order

A.T.Hofkamp hat at se-162.se.wtb.tue.nl
Wed Jun 18 12:53:51 CEST 2008


On 2008-06-18, Robert Bossy <Robert.Bossy at jouy.inra.fr> wrote:
> Hi,
>
> I wish to know how two dict objects are compared. By browsing the 
> archives I gathered that the number of items are first compared, but if 
> the two dict objects have the same number of items, then the comparison 
> algorithm was not mentioned.

You could consider hashing, if the order of hashing is independent on the end
result and it is fast enough.
Different hash results are different dicts, equal hashes give you no
conclusion.

Then, you are probably down to comparing keys (since keys are unique and the
number of keys in both dicts are the same, one direction of comparing is
enough) and values.

Since dict is designed to be fast in accessing keys, the performance should be
not entirely disastreus.

> domain-specific language where there's a data structure similar to 
> python dict and I need an source of inspiration for implementing 
> comparisons.

If you have a choice in data structures, you may want to have an ordered
dictionary (or sorted dict), where keys are sorted, making it much easier to
decide about equality.
The price you pay at least is less fast dictionary modifications and possibly
also less fast key access although that also depends on the speed of hashing
the key.

There are also discussions about ordered dictionaries in Python (I believe they
are called OrderedDict or SortedDict). There is also a PEP about them.

Sincerely,
Albert



More information about the Python-list mailing list