[issue1771] Remove cmp parameter to list.sort() and builtin.sorted()
Tom Switzer thomas.swit...@gmail.com added the comment: If the equal min y-coords are handled, I think it'd be quicker too. As Guido noted, O(n) function calls is better then O(n log n) =] Though the general case is still unhandled. And, though it doesn't help my case, the Graham Scan can also be performed on points sorted lexicographically too, by constructing the upper lower hull separately, hehe. Now, I understand cmp on the whole was removed from the language. Using __lt__, __eq__, etc. really is more natural. However, having an explicit cmp function for sorting makes sense to me. At the very least, it is more obvious and natural for some problems - though I respect that using a key func. is often faster. In some rare (though rare is very subjective) cases it is required; packing a cmp function into __cmp__ in a wrapper object is really just a hard-to-read cmp function and highlights the need for cmp. I would actually love to see it added for min/max too actually, since I find I often use a simple reduce function in place of a min(lst, cmp=...). Enforcing proper comparisons (, , ==, etc) makes sense, but would having the cmp function live, so to speak, in sorting really be that bad? Just inform the user in the docs that key is preferred and often faster. -- Added file: http://bugs.python.org/file15473/unnamed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1771 ___If the equal min y-coords are handled, I think it#39;d be quicker too. As Guido noted, O(n) function calls is better then O(n log n) =] Though the general case is still unhandled. And, though it doesn#39;t help my case, the Graham Scan can also be performed on points sorted lexicographically too, by constructing the upper amp; lower hull separately, hehe.br brNow, I understand cmp on the whole was removed from the language. Using __lt__, __eq__, etc. really is more natural. However, having an explicit cmp function for sorting makes sense to me. At the very least, it is more obvious and natural for some problems - though I respect that using a key func. is often faster. In some rare (though quot;rarequot; is very subjective) cases it is required; packing a cmp function into __cmp__ in a wrapper object is really just a hard-to-read cmp function and highlights the need for cmp. I would actually love to see it added for min/max too actually, since I find I often use a simple reduce function in place of a min(lst, cmp=...). Enforcing proper comparisons (lt;, gt;, ==, etc) makes sense, but would having the cmp function live, so to speak, in sorting really be that bad? Just inform the user in the docs that key is preferred and often faster.br ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue1771] Remove cmp parameter to list.sort() and builtin.sorted()
Tom Switzer thomas.swit...@gmail.com added the comment: Mark: I think your example actually helps illustrate my point. My point was that computing the angle directly is less efficient or not as nice numerically. For instance, if you are sorting points by angle relative to an extreme point you could do something like this (a first step in the Graham Scan) - be prepared for non-Python 3.0 code ;) from functools import partial from random import random def turn(p, q, r): Return -1, 0, or 1 if p,q,r forms a right, straight, or left turn respectively. return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0) pts = [(random(), random()) for i in xrange(10)] i = min(xrange(len(pts)), key=lambda i: pts[i]) p = pts.pop(i) pts.sort(cmp=partial(turn, p)) Here our comparison function requires only 2 multiplications and 5 additions/subtractions. This function is nice especially if you are using arbitrary precision or rational numbers as it is exact. On Sun, Dec 6, 2009 at 6:57 AM, Mark Dickinson rep...@bugs.python.orgwrote: Mark Dickinson dicki...@gmail.com added the comment: Tom, I think I'm missing your point: all three of the examples you give seem like perfect candidates for a key-based sort rather than a comparison-based one. For the first example, couldn't you do something like: def direction(pt1, pt2): angle of line segment from point 1 to point 2 return atan2(pt2.y - pt1.y, pt2.x - pt1.x) my_points.sort(key=lambda pt: direction(reference_pt, pt)) ? How would having a cmp keyword argument make this any easier or simpler? Here's the best example I can think of for which key-based sorting is problematic: imagine that the Decimal type doesn't exist, and that you have triples (sign, coefficient_string, exponent) representing arbitrary-precision base 10 floating-point numbers. It's fairly tricky to come up with a key function that maps these triples to some existing ordered type, so that they can be sorted in natural numerical order. The problem lies in the way that the sort order for the coefficient string and exponent depends on the value of the sign (one way for positive numbers, reversed for negative numbers). But it's not a big deal to define a wrapper for cases like this. -- nosy: +mark.dickinson ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1771 ___ -- Added file: http://bugs.python.org/file15463/unnamed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1771 ___Mark: I think your example actually helps illustrate my point. My point was that computing the angle directly is less efficient or not as nice numerically. For instance, if you are sorting points by angle relative to an extreme point you could do something like this (a first step in the Graham Scan) - be prepared for non-Python 3.0 code ;)br brfrom functools import partialbrfrom random import randombrbrdef turn(p, q, r):br   quot;quot;quot;Return -1, 0, or 1 if p,q,r forms a right, straight, or left turn respectively.quot;quot;quot;br   return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)br brpts = [(random(), random()) for i in xrange(10)]bri = min(xrange(len(pts)), key=lambda i: pts[i])brp = pts.pop(i)brpts.sort(cmp=partial(turn, p))brbrHere our comparison function requires only 2 multiplications and 5 additions/subtractions. This function is nice especially if you are using arbitrary precision or rational numbers as it is exact.br brbrdiv class=gmail_quoteOn Sun, Dec 6, 2009 at 6:57 AM, Mark Dickinson span dir=ltrlt;a href=mailto:rep...@bugs.python.org;rep...@bugs.python.org/agt;/span wrote:brblockquote class=gmail_quote style=border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex; br Mark Dickinson lt;a href=mailto:dicki...@gmail.com;dicki...@gmail.com/agt; added the comment:br br Tom, I think I#39;m missing your point:  all three of the examples you givebr seem like perfect candidates for a key-based sort rather than abr comparison-based one.  For the first example, couldn#39;t you do somethingbr like:br br def direction(pt1, pt2):br   quot;quot;quot;angle of line segment from point 1 to point 2quot;quot;quot;br   return atan2(pt2.y - pt1.y, pt2.x - pt1.x)br br my_points.sort(key=lambda pt: direction(reference_pt, pt))br br ? How would having a cmp keyword argument make this any easier orbr simpler?br br br Here#39;s the best example I can think of for which key-based sorting isbr problematic:  imagine that the Decimal type doesn#39;t exist, and that youbr have triples (sign, coefficient_string, exponent) representingbr arbitrary-precision base 10 floating-point numbers.  It#39;s fairly trickybr to come up with a key function that maps these triples to some existingbr ordered
[issue1771] Remove cmp parameter to list.sort() and builtin.sorted()
Tom Switzer thomas.swit...@gmail.com added the comment: I am not sure I understand the reasoning behind removing the cmp parameter (and agree with Lea Wiemann). Trying to wedge a proper comparison into the key parameter is clumsy and unreadable (as can be seen in the 2to3 example above). The intrinsic ordering on objects does not necessarily match up with the way you want to sort them. For example, a natural intrinsic order on 2 points in 2d is lexicographical, however you often want to sort by angular order relative to some other point instead. Clearly this can never be put in __cmp__ or __lt__, because the sorted order is relative to some other unknown point. Trying to do this with the key function doesn't make sense; it would not be clear you are sorting by angular order and you'd have to instantiate a bunch of wrapper objects just to do basic sorting. Another quick example would be sorting hyperplanes by intersection on a ray. Sorting points along a direction given by a vector. I understand removing redundant features from a language, but I just can't see how key replaces this functionality in a readable or efficient way. This highlights an important class of cases (since it was mentioned that none could be thought of) in which we wish to make comparisons between values where a comparison (, or ==) is more numerically sound, more efficient, or the only option (perhaps the ordering is defined explicitly) then computing the exact values (eg. angle). As far as it seems, the only way to do this with key is by following the example given and creating a class solely to wrap each object that overrides __cmp__, which is certainly non-obvious (ie. there is no one, obvious way to do it). -- nosy: +tixxit ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1771 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
