[Python-Dev] Stable sort and partial order

[Michael Foord]

On 01/11/2010 11:33, Antoine Pitrou wrote:
> On Mon, 01 Nov 2010 02:55:35 +0000
> Michael Foord<fuzzyman at voidspace.org.uk>  wrote:
>> Having a more efficient 'slow-path' and moving to that by default would
>> fix it. The bug is only a duplicate of the bug in sorted - caused by the
>> fact that sets / frozensets can't be sorted in the standard Python way
>> (their less than comparison adheres to the set definition). This is
>> something that will probably surprise many Python developers:
>>
>>   >>>  a = [{2,4}, {1,2}]
>>   >>>  b = a[::-1]
>>   >>>  sorted(a)
>> [set([2, 4]), set([1, 2])]
>>   >>>  sorted(b)
>> [set([1, 2]), set([2, 4])]
>>
>> (Fixing the bug in sorted would fix assertItemsEqual ;-)
> How is this a bug? The sort algorithm is stable, which means the above
> behaviour is a feature.

Well, bug is the wrong word as it is obviously an intended feature (or 
consequence of a feature). I still think, given the general behaviour of 
Python sorting, that it is unexpected. It breaks what is usually an 
invariant for sorting without an explicit key that sortable types 
sorted(l) == sorted(l[::-1]).

There is however a note in the set documentation:

Since sets only define partial ordering (subset relationships), the 
output of the list.sort() method is undefined for lists of sets.

> I see no easy way of eliminating the O(n*n) issue. Custom key functions
> can't work in all cases.
>
Right. Special casing sets and frozensets would be one (particularly 
inelegant) way however.

All the best,

Michael
> Regards
>
> Antoine.
>
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/fuzzyman%40voidspace.org.uk


-- 

http://www.voidspace.org.uk/

READ CAREFULLY. By accepting and reading this email you agree,
on behalf of your employer, to release me from all obligations
and waivers arising from any and all NON-NEGOTIATED agreements,
licenses, terms-of-service, shrinkwrap, clickwrap, browsewrap,
confidentiality, non-disclosure, non-compete and acceptable use
policies (”BOGUS AGREEMENTS”) that I have entered into with your
employer, its partners, licensors, agents and assigns, in
perpetuity, without prejudice to my ongoing rights and privileges.
You further represent that you have the authority to release me
from any BOGUS AGREEMENTS on behalf of your employer.