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 <report@bugs.python.org> wrote:

Mark Dickinson <dickinsm@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 <report@bugs.python.org>
<http://bugs.python.org/issue1771>
_______________________________________