[Python-Dev] Stable sort and partial order

[Michael Foord]

On 01/11/2010 15:10, R. David Murray wrote:
> On Mon, 01 Nov 2010 14:26:19 -0000, Michael Foord<fuzzyman at voidspace.org.uk>  wrote:
>> 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 =3D [{2,4}, {1,2}]
>>>>    >>>   b =3D 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]).
> Well, as Antoine pointed out, Python's sorting algorithm is stable,
> so that is in fact *not* an invariant:
>
>>>> x = ['abcd', 'foo'*50, 'foo'*50, 'dkke']
>>>> y = x[::-1]
>>>> [id(n) for n in sorted(x)]
> [3073747680, 3073747904, 3073747624, 3073747512]
>>>> [id(n) for n in sorted(y)]
> [3073747680, 3073747904, 3073747512, 3073747624]
>
> Yes, == usually hides the fact that the *objects* are in a different
> order, but obviously that doesn't apply to sets :)
>

Sorry, that should have been sorted(l) == sorted(l[::-1]) - which *is* 
the case for your example above.

Michael

> --
> R. David Murray                                      www.bitdance.com


-- 

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.