This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tixxit
Recipients LeWiemann, gvanrossum, mark.dickinson, rhettinger, tixxit
Date 2009-12-06.16:24:41
SpamBayes Score 3.7562176e-12
Marked as misclassified No
Message-id <853aa53f0912060824j12451935ob500deffe5824bc1@mail.gmail.com>
In-reply-to <1260100651.05.0.868730760351.issue1771@psf.upfronthosting.co.za>
Content
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>
> _______________________________________
>
Files
File name Uploaded
unnamed tixxit, 2009-12-06.16:24:40
History
Date User Action Args
2009-12-06 16:24:43tixxitsetrecipients: + tixxit, gvanrossum, rhettinger, mark.dickinson, LeWiemann
2009-12-06 16:24:41tixxitlinkissue1771 messages
2009-12-06 16:24:41tixxitcreate