<div dir="ltr">wow! a few time zones (and a day job) really make a difference to taking part in a discussion :-)<div><br></div><div>Thanks for all the feedback. From what I can tell, we don't have a consensus, though It's looking pretty unlikely that this is going to be adopted (though maybe the decorator idea). But I'm going to go through and try to summarize what we (I?) have learned, and what does seem to be agreed upon, or not. If I misinterpret something you said, or take a quote out of context, please correct it, but trust that I didn't do it on purpose....</div><div><br></div><div>Also, it's kind of a pain to do a digest like this and properly attribute everyone, so mostly I'm not going to attribute the quotes...</div><div><br></div><div><br></div><div><span class="gmail-im" style="font-size:12.8px"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">So: has this already been brought up and rejected?<br></blockquote><br></span><a href="https://bugs.python.org/issue20632" rel="noreferrer" target="_blank" style="font-size:12.8px">https://bugs.python.org/issue2<wbr>0632</a><br></div><div><br></div><div>Thanks Serhiy -- I didn't think to look in the Bug DB. This does remind me that it would be good to have a place (maybe in a mets-PEP?) to put topics that have been discussed, but didn't get as far as anyone writing a PEP...</div><div><br></div><div><br></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><span style="font-size:12.8px">An existence proof: in NLTK, an </span><span style="font-size:12.8px;font-family:monospace,monospace">__lt__</span><span style="font-size:12.8px"> method added purely to facilitate consistent sorting (in doctests) of structured data objects for which comparison operators do not really make conceptual sense: </span><a href="https://github.com/nltk/nltk/pull/1902/files#diff-454368f06fd635b1e06c9bb6d65bd19bR689" target="_blank" style="font-size:12.8px">https://github.com/nltk/nltk/<wbr>pull/1902/files#diff-<wbr>454368f06fd635b1e06c9bb6d65bd1<wbr>9bR689</a><br>Granted, calling <span style="font-family:monospace,monospace">min()</span> and <span style="font-family:monospace,monospace">max()</span> on collections of these objects would not make conceptual sense either. Still, <span style="font-family:monospace,monospace">__sort_key__</span> would have been cleaner than <span style="font-family:monospace,monospace">__lt__</span>.</blockquote><div><br></div><div>So nice to know I'm not the only one that wants (needs) to provide a sort order be default -- though it doesn't mean it's not a niche issue anyway.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">By default, we sort by the inherent order of the values. But if the<br></span><span style="font-size:12.8px">values have no inherent order (they are unordered), we can sort<br></span><span style="font-size:12.8px">unordered items in a collection by providing an appropriate key<br></span><span style="font-size:12.8px">function. Hence why I say they are loosely related.</span></blockquote><div><snip></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> It<br>doesn't make sense to put that functionality into the complex numbers<br>themselves: complex numbers are unordered, and any order we impose on<br>them comes from the collection, not the individual numbers. </blockquote><div> </div><div>Sure -- and that's why we definitely still need a key option for the sorting functions, and why not all classes should define a sort order. But for many classes, it does make sense to define a default sort order. Take something as simple as strings -- they have a default sort order, but a user very well might want to sort them differently -- say case-insensitive, or ...</div><div><br></div><div>So I think there is consensus here (and no one was proposing otherwise):</div><div><br></div><div> - Defining a sort order is NOT required of all classes</div><div> - The sorting methods definitely need to allow a custom key function.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px"> the comparison operators<br></span><span style="font-size:12.8px">apply to the values in the collection; the key function applies to the<br></span><span style="font-size:12.8px">collection itself </span></blockquote><div><br></div><div>But many (most) objects DO provide a default sort order, by means of the comparison methods.  So the idea that objects have a default sort order is already pretty well accepted :-)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">But that assumes that there's only ever one way to order a collection of<br></span><span style="font-size:12.8px">unordered items.</span></blockquote><div><br></div><div>no,. it doesn't -- it implies there is a default way, which is what is done already for most types. And again, some classes  shouldn't even have a default.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">I'm not sure I understand the motivation to make elements *sortable* but not comparable. If an arbitrary order is still useful, I'd think you'd want to be able to tell how two particular elements *would* sort by asking a<b.</span> </blockquote><div><br></div><div>yeah, I'm not sure about this -- going back to the example of complex numbers, I like </div><div>the idea of providing a default sort order but not make the declaration that this is how the objects SHOULD be compared -- after all, you can provide your own key function, but not so easily re-define the comparisons...</div><div><span class="gmail-im" style="font-size:12.8px"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Is sorting-related functionally too special-case to deserve a protocol?<br></blockquote></span></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br></blockquote></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Yes, it is too special-case. I don't see any advantages in comparison with defining the __lt__ method. It will be rather confusing if different methods of sorting produce inconsistent order. If the first item of the sorted list is not the smallest item of the list.</blockquote></div></blockquote><div><br></div><div>well, yeah, but not any different than the fact that you can inconsitently define the comparison operators already.</div><div><br></div><div>What I wasn't realizing is that you only need to define __lt__ (and __eq__) to get sortability. Maybe it would be good to document that more prominently somewhere (if it's documented at all, other than the source).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">But the idea of the class decorator looks more sane to me.</span></blockquote><div><br></div><div>yeah, I'm liking that. </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">Most often when I define equality and comparison dunder methods for a<br></span><span style="font-size:12.8px">custom class, I'm effectively just deferring the comparison to some<br></span><span style="font-size:12.8px">field or tuple of fields of the object. </span></blockquote><div> </div><div>Exactly -- which may be an argument for a decorator, rather than a dunder method -- particularly if performance isn't improved by the dunder method.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">What if we added a @key_ordering decorator, like @total_ordering but<br></span><span style="font-size:12.8px">using __key__ to generate the comparisons?</span></blockquote><div><br></div><div>This could be a good idea -- just putting it here for the record as it's mentioned elsewhere.</div><div><br></div><div>OK -- multiple posts about performance, I'm going to try to summarize:</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-im" style="font-size:12.8px">> This will add an additional overhead. This will be even slower than<br></span><span class="gmail-im" style="font-size:12.8px">> passing the key function, since you will need to look up the __key__<br></span><span class="gmail-im" style="font-size:12.8px">> method in every item.</span><span class="gmail-im" style="font-size:12.8px"><br></span><span style="font-size:12.8px">That is a reasonable objection.  However, looking up a tp_XXX slot is<br></span><span style="font-size:12.8px">very cheap.</span><span class="gmail-im" style="font-size:12.8px"><br></span><span class="gmail-im" style="font-size:12.8px">> Yes, it is too special-case. I don't see any advantages in comparison<br></span><span class="gmail-im" style="font-size:12.8px">> with defining the __lt__ method.</span><span class="gmail-im" style="font-size:12.8px"><br></span><span style="font-size:12.8px">There are definitely advantages.  Sorting calls __lt__ for each<br></span><span style="font-size:12.8px">comparison (that is, O(n log n) times) while __key__ would only be<br></span><span style="font-size:12.8px">called once per item at the start (that is, O(n) times).</span></blockquote><div><br></div><div>OK -- so:</div><div><br></div><div>if a new slot is added, then the performance hit of __key__ lookup is minor, but every type now has a new slot, so there is another performance (and memory) hit for that everywhere -- this is too niche to want to hit every type.</div><div><br></div><div>Any chance that adding a __key__ slot would help with other built-in types by being faster than checking __lt__ -- probably not.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">Conversely, when sorting a key can provide significant performance<br></span><span style="font-size:12.8px">improvements. A single O(n) pass to compute keys, followed by O(n<br></span><span style="font-size:12.8px">log(n)) comparisons could be significantly faster, </span></blockquote><div><br></div><div>snip</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px"> It can happen, if key(x).__lt__ is sufficiently faster than<br></span><span style="font-size:12.8px">x.__lt__, but that would be unusual.</span></blockquote><div><br></div><div>actually, that's quite common :-) -- but a __sort_key__ method would add n extra attribute lookups, too. so now it's less likely that it'll be faster than __lt__</div><div><br></div><div>This is "key" :-) -- it is very common for the sort key to be a very simple type, say int or float, that are very fast to compare -- so this can be a really performance saver when passing key function.</div><div><br></div><div>Also, I recall that someone was working on special-casing the sort code to do even faster sorting on simple numeric keys -- not sure what came of that though. But the extra method lookup for every key could overwhelm that anyway :-(</div><div><br></div><div><span style="color:rgb(80,0,80);font-size:12.8px">> And there will be an overhead even in the case when the __key__ method is not defined.</span><br></div><div><br></div><div>not good.</div><div><br></div><div>I can't think of a way to profile this easily -- we know that having a key function can be helpful, but that doesn't take into account the extra method lookup -- maybe a key function that involves a method lookup??</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">If it defines both, it isn't clear which will be used for sorting.<br></span><span style="font-size:12.8px">Should __lt__ take priority, or __key__? Whichever we choose, somebody<br></span><span style="font-size:12.8px">is going to be upset and confused by the choice.</span></blockquote><div><br></div><div>__sort_key__ would take priority -- that is a no brainer, it's the sort key, it's used for sorting. And __lt__ giving a different result is no more surprising, and probably less surprising, than total ordering being violated in  any other way.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">I disagree with the design of this: it is putting the decision of how to<br></span><span style="font-size:12.8px">sort uncomparable objects in the wrong place, in the object itself<br></span><span style="font-size:12.8px">rather than in the report that wants to sort them.</span></blockquote><div><br></div><div>No -- it's putting the decision about a default sort order in the object itself -- maybe a niche case, but a real one.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">If we have a __key__ method on a class, then the following becomes true:</span><br style="font-size:12.8px"><span style="font-size:12.8px">    * We can work out which of 2 instances is bigger/smaller using max/min.<br></span><span style="font-size:12.8px">    * We can compare two items by doing a sort.</span><br style="font-size:12.8px"><span style="font-size:12.8px">So while the *intent* may not be to allow comparisons, that's what you've done.</span></blockquote><div><br></div><div>Sure, but Python is for consenting adults -- we allow a lot of things that aren't encouraged...</div><div><br></div><div>I don't think leveraging sort to get a comparison is a problematic use case at all -- though "min" and "max" is a different matter ... maybe they shouldn't use __sort_key__? thought that does weaken the whole idea :-)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">But why not just define __lt__ and use total_ordering, instead of<br></span><span style="font-size:12.8px">defining two identical decorators that differ only in the name of the<br></span><span style="font-size:12.8px">dunder method they use?</span></blockquote><div><br></div><div>well, one reason is that total_ordering can result in even worse performance... thought probably not a huge deal.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">I never imagined that it would be a required method. Of course it is<br></span><span style="font-size:12.8px">optional. But by adding interpreter support, we're blessing something<br></span><span style="font-size:12.8px">which I think is a misguided design choice as the One Obvious Way.</span></blockquote><div><br></div><div>I don't think it's interpreter support, but rather standard library support -- it would be changes in the list.sort and sorted, and ... functions, not any change to the interpreter. (and it would be a change to the language definition) But your point is that same.</div><div><br></div><div>However, I think there is no consensus that it's a misguided design choice -- having an explicit way to specifically say "this is the default way to sort these objects", when there is not other reason for total ordering feels pythonic to me. Again, maybe a niche use case though.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">If people like Chris' idea, just add a sortkey() method to your class,<br></span><span style="font-size:12.8px">and then call sorted(collection_of_Spam, key=Spam.sortkey) and it will<br></span><span style="font-size:12.8px">Just Work.</span></blockquote><div><br></div><div>Not a bad approach, though that as useful until/unless it becomes something of a standard.</div><div><br></div><div>(and for the record, if we did add __sort_key__, then on older versions you could still do:</div><div><br></div><div><span style="font-size:12.8px">sorted(collection_of_Spam, key=Spam.__sort_key__)</span><br></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">so too bad on the compatibility front...</span></div><div><span style="font-size:12.8px"><br></span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">The decorator idea LGTM. But it doesn't need the special __key__ method. Just pass the key function as a decorator argument.</span><br style="font-size:12.8px"><span style="font-size:12.8px">This idea was proposed more than 3.5 years ago. Is there a PyPI package that implements it?</span></blockquote><div><br></div><div>yes, it was, though not in a terribly public place / way...</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">I would find it cleaner to express it as a method in the class's body<br></span><span style="font-size:12.8px">("__key__" or anything else) rather than have to pass a function object.<br></span><span style="font-size:12.8px">Also, it's easier to unit-test if it officially exists as a method...</span> </blockquote><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">me too, though couldn't we do both? the decorator, if not passed a sort function, would look for __key__.</span></div><div><span style="font-size:12.8px"><br></span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">I wondered what the performance would be and tested the following code:</span></blockquote><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><snip></span></div><div><span style="font-size:12.8px"><br></span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">it outputs this for my with python 3.6.0</span><br style="font-size:12.8px"><span style="font-size:12.8px">10000<br></span><span style="font-size:12.8px">key 0.010628s  10000 calls<br></span><span style="font-size:12.8px"> lt 0.053690s 119886 calls</span><br style="font-size:12.8px"><span style="font-size:12.8px">It seems that providing a key is ~5 times faster the depending on __lt__.<br></span><span style="font-size:12.8px">(I even used a short circuit to se if __lt__ could beat key).</span></blockquote><div> </div><div>yeah, this is what I expect for a key function -- exactly why I started all this expecting a performance gain. But as others' have pointed out, this is a key function, not a __key__ method that would need to be called each time. I'm going to try to benchmark (a simulation of) that. This is Barry's code, with the addition of a "outer_key" function that call the instances key method:</div><div><br></div><div>[I got very similar results as Barry with his version: about 5X faster with the key function]</div><div><div><br></div><div>def outer_key(item):</div><div>    return item.key()</div></div><div><br></div><div>so we get a function lookup each time it's used.</div><div><br></div><div>However, I'm confused by the results -- essentially NO Change. That extra method lookup is coming essentially for free. And this example is using a tuple as the key, so not the very cheapest possible to sort key.</div><div><br></div><div>Did I make a mistake? is that lookup somehow cached?</div><div><br></div><div><font face="monospace, monospace">In [36]: run sort_key_test.py</font></div><div><font face="monospace, monospace">10000</font></div><div><font face="monospace, monospace">key       0.012529s  10000 calls</font></div><div><font face="monospace, monospace">outer_key 0.012139s  10000 calls</font></div><div><font face="monospace, monospace">lt        0.048057s 119877 calls</font></div><div><br></div><div>each run gives different results, but the lt method is always on order of 5X slower for this size list. Sometimes out_key is faster, mostly a bit slower, than key.</div><div><br></div><div>Also, I tried making a "simpler" __lt__ method:</div><div><br></div><div><font face="monospace, monospace">return (self.value1, self.value2) < (other.value1, other.value2)<br></font></div><div><br></div><div>but it was bit slower than the previous one -- interesting.</div><div><br></div><div>Then I tried a simpler (but probably common) simple attribute sort:</div><div><br></div><font face="monospace, monospace">    def __lt__(self, other):<br>        global lt_calls<br>        lt_calls += 1<br><br>        return self.value1 < other.value1<br><br>    def key(self):<br>        global key_calls<br>        key_calls += 1<br><br>        return self.value1</font><div><br></div><div>And that results in about a 6X speedup</div><div><br></div><font face="monospace, monospace">In [42]: run sort_key_test.py<br>10000<br>key       0.005157s  10000 calls<br>outer_key 0.007000s  10000 calls<br>lt        0.041454s 119877 calls<br>time ratio: 5.922036784741144</font><div><br></div><div><br></div><div>And, interestingly (t me!) there is even a performance gain for only  a 10 item list! (1.5X or so, but still)</div><div><br></div><div>In fact, this seems to show that having a __key__ method would  often provide a performance boost, even for small lists.</div><div><br></div><div>(still to try to figure out -- how much would the look for __key__ slow things down when it didn't exist....)</div><div><br></div><div>I have got to be doing something wrong here -- I hope some of you smarter folks will tell me what :-)</div><div><br></div><div>Code enclosed.</div><div><br></div><div><br></div><div><br></div><div><br></div><div class="gmail_extra">-- <br><div class="gmail-m_-2568965429799507930gmail_signature"><br>Christopher Barker, Ph.D.<br>Oceanographer<br><br>Emergency Response Division<br>NOAA/NOS/OR&R            <a href="tel:(206)%20526-6959" value="+12065266959" target="_blank">(206) 526-6959</a>   voice<br>7600 Sand Point Way NE   <a href="tel:(206)%20526-6329" value="+12065266329" target="_blank">(206) 526-6329</a>   fax<br>Seattle, WA  98115       <a href="tel:(206)%20526-6317" value="+12065266317" target="_blank">(206) 526-6317</a>   main reception<br><br><a href="mailto:Chris.Barker@noaa.gov" target="_blank">Chris.Barker@noaa.gov</a></div>
</div></div>