[Python-ideas] a sorting protocol dunder method?

[Chris Angelico]

On Tue, Dec 5, 2017 at 8:22 AM, Barry <barry at barrys-emacs.org> wrote:
>
>
>> On 4 Dec 2017, at 20:12, Antoine Pitrou <solipsis at pitrou.net> wrote:
>>
>> On Mon, 4 Dec 2017 19:37:02 +0000
>> Barry Scott <barry at barrys-emacs.org> wrote:
>>> I wondered what the performance would be and tested the following code:
>>>
>> [...]
>>>
>>> it outputs this for my with python 3.6.0
>>>
>>> 10000
>>> key 0.010628s  10000 calls
>>> lt 0.053690s 119886 calls
>>>
>>> It seems that providing a key is ~5 times faster the depending on __lt__.
>>> (I even used a short circuit to se if __lt__ could beat key).
>>
>> Thanks for taking the time to write a benchmark.  I'm not surprised
>> by the results (and your __lt__ method isn't even complicated: the gap
>> could be very much wider).  There is more to Python performance than
>> aggregate big-O algorithmic complexity.
>
> I was surprised by the huge difference. I was expecting a closer race.
>
> For the record I think that a __sort_key__ is not a good idea as it is so easy to
> do as I did and define key methods on the class, without the limit of one such
> method.

The numbers here are all fairly small, but they make a lot of sense.
Calls into Python code are potentially quite slow, so there's a LOT of
benefit to be had by calling Python code once per object instead of N
log N times for the comparisons. Increasing the length of the list
will make that difference even more pronounced.

But that's an argument for using a key function, not for having a
__key__ special method.

ChrisA