dict1 < dict2 <=> len(dict1) <= len(dict2) ?

Tim Peters tim.one at comcast.net
Fri Oct 18 22:47:32 CEST 2002


[Thorsten Kampe]
> does anyone know what "dict1 < dict2" tests?

Yes <wink>.

> I think it's equivalent to "len(dict1) <= len(dict2)", but I could be
> wrong.

Partly.  len(d1) < len(d2) implies d1 < d2 in recent Python releases, but
it's much more complicated if len(d1) == len(d2).

> "{111: 111} < {11:11, 22:22}" but "{111: 111, 22:22} > {11:11, 22:22}"
> made me guess: "'<' first tests the lengths

Yes.

> and if they're the same the keys are compared".

More that (key, value) pairs are compared, and *hoping* that the key and
value types implement a consistent total ordering (in which case dict
ordering also will) -- but that isn't the full truth either.

> Anyone who doesn't guess but /knows/?!

It's too tedious to explain the full truth here, and it doesn't matter (if
you think it does, you're writing code nobody will understand!).
dict_compare() in dictobject.c is the ultimate authority.

In the earliest Python releases, dicts were compared as if like so, and
assuming d1 and d2 are both dicts:

class dict:
    ...
    def __cmp__(d1, d2):
        items1 = d1.items()
        items2 = d2.items()
        items1.sort()
        items2.sort()
        return cmp(items1, items2)

This was incredibly expensive for large dicts.  Staring at lots of programs,
and soliciting advice, Guido discovered that in real life dicts were
compared for only two reasons:

1. To see whether two dicts in fact had the same set of (key, value)
   pairs, d1 == d2.

2. Comparing a dict against an empty dict, as in

     while dict > {}:

The current implementation of dict comparison works hard to optimize those
two, doing nothing more for any other case than is required merely to ensure
a consistent ordering.  It remains a very good, but much faster,
approximation to the original scheme when len(d1) == len(d2).





More information about the Python-list mailing list