[Python-ideas] a sorting protocol dunder method?

[Antoine Pitrou]

On Mon, 4 Dec 2017 23:16:11 +1100
Steven D'Aprano <steve at pearwood.info> wrote:
> On Mon, Dec 04, 2017 at 12:06:38PM +0100, Antoine Pitrou wrote:
> 
> > There are definitely advantages.  Sorting calls __lt__ for each
> > comparison (that is, O(n log n) times) while __key__ would only be
> > called once per item at the start (that is, O(n) times).  
> 
> Passing a key function doesn't magically turn a O(n log n) comparison 
> sort into a O(n) sort.

Where did I say it did?

> Once you've called the key function every time, you still have to 
> *actually sort*, which will be up to O(n log n) calls to __lt__ on 
> whatever __key__ returned.

Yes... and the whole point is for __key__ to return something which is
very cheap to compare, such that there are O(n) expensive calls to
__key__ and O(n log n) cheap calls to __lt__, rather than O(n log n)
expensive calls to __lt__.

> > If __key__ is inconsistent with __lt__, it is the same error as making
> > __lt__ inconsistent with __gt__.  
> 
> You seem to be assuming that __key__ is another way of spelling __lt__, 
> rather than being a key function.

It isn't.  It's just supposed to be consistent with it, just like
__hash__ is supposed to be consistent with __eq__, and noone reasonable
chastises Python because it allows to define __hash__ independently of
__eq__.

Also please note Serhiy's sentence I was responding to:
"""It will be rather confusing if different methods of sorting produce
inconsistent order."""

> In any case, it isn't an error for __lt__ to be inconsistent with 
> __gt__.
[...]
> Not all values have total ordering.

As usual you should try to understand what people are trying to say
instead of imagining they are incompetent.

In the present case, it would definitely be an inconsistency (and a
programming error) to have both `a < b` and `b < a` return true.

> Defining a single comparison method is not enough to define the rest. 

How about you stick to the discussion?  I'm talking about deriving
comparison methods from __key__, not from another comparison method.
Defining __key__ is definitely enough to define all comparison
methods.

Regards

Antoine.