[Python-Dev] Stable sort and partial order

[Michael Foord]

On 01/11/2010 16:23, Nick Coghlan wrote:
> On Tue, Nov 2, 2010 at 1:33 AM, R. David Murray<rdmurray at bitdance.com>  wrote:
>> Or, to put it another way, *if* there is a bug here it would be in set,
>> not sorted.
> Put me in the "it's not a bug, it's a feature" camp. Providing a
> "elements equal" check that doesn't rely on LT providing a total
> ordering is a non-trivial exercise.
>
> Looking at assertItemsEqual, I'd be inclined to insert a check that
> falls back to the "unorderable_list_difference" approach in the case
> where "expected != sorted(reversed(expected))"

If that is sufficient then it would be a nice way of keeping the fast path.

(I'm not arguing that Antoine and R. David aren't correct in what 
they're saying about set ordering - I'm just saying that I was surprised 
and bet I'm not the only one. Bit of a dead end discussion. :-)

Michael

> (only need to check the
> one, since if the expected values are totally ordered, while the
> actual values are not, this should show up when comparing the
> elements). It slows down the fast path a bit, but the updated function
> should at least handle partial orderings more correctly than it does
> now.
>
> Cheers,
> Nick.
>
> P.S. Late night post, so I may be missing something obvious...
>


-- 

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.