[Python-ideas] a sorting protocol dunder method?

[Serhiy Storchaka]

04.12.17 13:06, Antoine Pitrou пише:
> On Mon, 4 Dec 2017 08:45:55 +0200
> Serhiy Storchaka <storchaka at gmail.com>
> wrote:
>> 04.12.17 01:06, Chris Barker пише:
>>> So: has this already been brought up and rejected?
>>
>> https://bugs.python.org/issue20632
>>
>>> Am I imagining the performance benefits?
>>
>> This will add an additional overhead. This will be even slower than
>> passing the key function, since you will need to look up the __key__
>> method in every item.
> 
> That is a reasonable objection.  However, looking up a tp_XXX slot is
> very cheap.

But introducing a new slot is not easy. This will increase the size of 
the type object, break binary compatibility. According to Stefan 
Behnel's researches (https://bugs.python.org/issue31336) the main time 
of the creation of a new type is spent on initializing slots. This cost 
will pay every Python program, even if it doesn't use the __key__ method.

There are many more common and important methods that don't have the 
corresponding slot (__length_hint__, __getstate__, __reduce__, __copy__, 
keys).

>> Yes, it is too special-case. I don't see any advantages in comparison
>> with defining the __lt__ method.
> 
> 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).

It will call __lt__ for each key comparison (the same O(n log n) times), 
but *in addition* it will call __key__ O(n) times. You can get the 
benefit only when times of calling __key__ is much smaller than the 
difference between times of calling item's __lt__ and key's __lt__, and 
maybe only for large lists. But why not just pass the key argument when 
you sort the large list?

>> It will be rather confusing if
>> different methods of sorting produce inconsistent order.
> 
> If __key__ is inconsistent with __lt__, it is the same error as making
> __lt__ inconsistent with __gt__.

If __key__ is consistent with __lt__, then we can just use __lt__, and 
don't introduce new special methods.

> And there could be a decorator that generates all comparison methods
> from __key__.

The decorator idea LGTM. But it doesn't need the special __key__ method. 
Just pass the key function as a decorator argument.

This idea was proposed more than 3.5 years ago. Is there a PyPI package 
that implements it?