[issue1771] Remove cmp parameter to list.sort() and builtin.sorted()

[Tom Switzer]

Tom Switzer  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 
<http://bugs.python.org/issue1771>
___
___
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]

Tom Switzer  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 wrote:

>
> Mark Dickinson  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 
> <http://bugs.python.org/issue1771>
> ___
>

--
Added file: http://bugs.python.org/file15463/unnamed

___
Python tracker 
<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 ;)
from functools import partialfrom random import randomdef 
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 
<mailto:rep...@bugs.python.org";>rep...@bugs.python.org> 
wrote:

Mark Dickinson <mailto:dicki...@gmail.com";>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 the

[issue1771] Remove cmp parameter to list.sort() and builtin.sorted()

[Tom Switzer]

Tom Switzer  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 
<http://bugs.python.org/issue1771>
___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.

___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com