metaclasses for type comparison
Tim Peters
tim.one at comcast.net
Thu Sep 11 17:40:30 EDT 2003
[David Eppstein]
> I don't have 2.3 yet, so haven't used sets yet, but what happens if
> you try to sort a list of sets?
>
> I found a message
> <http://mail.python.org/pipermail/python-bugs-list/2003-January/015454.h
> tml> from Guido wondering about this but didn't see what the response
> was...
It was resolved as suggested there: an explict cmp() applied to two Sets
raises an exception. Set1.__lt__(Set2) returns true iff Set1 is a proper
subset of Set2. list.sort() uses only __lt__ (when it can), so sorting a
list of Sets won't raise an exception (at least not just because __cmp__
raises an exception -- __cmp__ is never called because __lt__ exists), but
it's hard to say something useful about the result. For example,
>>> from sets import Set
>>> x = [Set([i]) for i in range(10, 0, -1)]
>>> x.sort()
>>> x
[Set([10]), Set([9]), Set([8]), Set([7]), Set([6]), Set([5]), Set([4]),
Set([3]), Set([2]), Set([1])]
>>>
"x < y" returns false for each distinct pair of sets x and y in that list,
so any permutation of the list is as good an answer as any other. It so
happens that the 2.3 list.sort() implementation first asks
x[i] < x[i-1]
for each relevant index position i. They all say "no", so list.sort()
"deduces" (via assumed trichotomy) that x[i] >= x[i-1] everywhere, so ends
up believing the list is already in sorted order, and leaves it alone after
that one pass over the data.
More information about the Python-list
mailing list