[Python-ideas] a sorting protocol dunder method?

Antoine Pitrou solipsis at pitrou.net
Mon Dec 4 06:06:38 EST 2017


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.

> 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 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__.

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

Regards

Antoine.




More information about the Python-ideas mailing list