Discussion:
How to sort a list? NOT a newbie question.
(too old to reply)
Alex Martelli
2001-09-19 10:20:49 UTC
Permalink
"Michael James Barber" <mjbarber at ascc.artsci.wustl.edu> wrote in message
news:9o9mga$fmp at ascc.artsci.wustl.edu...

I had claimed Michael needed to test set-equality, but he notices:
...
Actually, this won't work in general. Consider having repeated roots of,
say, [1j,1j,-1j].
True! So, you need to test MULTI-SET equality -- i.e.
to associate a *count* (number of occurrences) to each
member in the (multi-)set.
rootset = {}
rootset[root] = rootset.get(root,0)+1
return 0
return 1
Untested, but it looks right.
Yep. Or, one could be slightly trickier, e.g.:

def all_coefficient_are_real(roots):
rootset = {}
for root in roots:
conj = root.conjugate()
rootset[root] = rootset.get(root,0)+1
rootset[conj] = rootset.get(conj,0)-1
return not filter(None, rootset.values())

(also "untested, but":-) -- however, the simpler
approach is no doubt preferable!


Alex
David Bolen
2001-09-17 18:31:34 UTC
Permalink
Obviously the policy of python is that all things are sortable. I really
can't imagine how complex numbers got left out.
Actually, everything being sortable really hasn't been true ever since
objects could implement their own __cmp__ mechanisms (back in 1.5 I
think), and thus any object can raise an exception during sorting. I
do think it's true that complex numbers are the only built-in types
that aren't comparable however, as of 2.1.

It doesn't seem like it would be terribly hard to wrap your own class
around a complex number and implement __cmp__ if you wanted to create
your own definition for comparing complex numbers. The uncertainty as
to the "best" manner in which to compare two such numbers was at least
part of the reason for leaving it out of the core implementation, but
that doesn't prevent anyone from implementing their own approach.

This change occurred during Python 2.1 (I believe) along with rich
comparisons. The argument at the time was the lack of mathematical
meaning in comparing complex numbers (which isn't in my area to
judge), but I think that was more along the lines of justifying the
behavior than forcing the change.

But the most logical argument against such a change I've tended to see
since is in fact the case brought up here - being able to sort lists
with complex numbers in them, or just in general being able to sort
arbitrary, heterogeneous lists. But the latter isn't true in general
anyway (as above), and the former can be solved with a private class
implementing an acceptable comparison for the particular application
domain in question.

--
-- David
--
/-----------------------------------------------------------------------\
\ David Bolen \ E-mail: db3l at fitlinxx.com /
| FitLinxx, Inc. \ Phone: (203) 708-5192 |
/ 860 Canal Street, Stamford, CT 06902 \ Fax: (203) 316-5150 \
\-----------------------------------------------------------------------/
Ignacio Vazquez-Abrams
2001-09-21 18:40:55 UTC
Permalink
Then, how does Python compare complex now?
It doesn't; it raises an exception.
--
Ignacio Vazquez-Abrams <ignacio at openservices.net>
William Park
2001-09-21 18:49:36 UTC
Permalink
Post by Ignacio Vazquez-Abrams
Then, how does Python compare complex now?
It doesn't; it raises an exception.
Thanks, I thought complex was treated just like tuple...
--
William Park, Open Geometry Consulting, <opengeometry at yahoo.ca>
8 CPU cluster, (Slackware) Linux, Python, LaTeX, Vim, Mutt, Sc.
Chris Barker
2001-09-17 21:56:07 UTC
Permalink
In Matlab,
complex numbers are sorted based on their magnitudes, and then by phase
angle if the magnitudes are the same. Comparing complex numbers using <,
<=, >, and >= always returns false.
Hmm. this isn't a solution that would be easy to use for Python, as
Python is more general purpose, so the list sort() method has to do the
same thing as the comparison operators. Also, you can write your own
sort function, so it would not be hard to deal with complex numbers
however you wanted.

Note that NumPy sort chokes on complex numbers as well, so I suppose you
could do something like MATLAB in Numpy.

One possible solution is for list.sort() have a way to deal with
"non-sortable" objects. I've had this problem when sorting a set of
two-tuples, when the second item in the tuple was not sortable.
list.sort() would choke, even though I was happy for it to ignore the
second item.

hhhmmm...

-Chris
--
Christopher Barker,
Ph.D.
ChrisHBarker at home.net --- --- ---
http://members.home.net/barkerlohmann ---@@ -----@@ -----@@
------@@@ ------@@@ ------@@@
Oil Spill Modeling ------ @ ------ @ ------ @
Water Resources Engineering ------- --------- --------
Coastal and Fluvial Hydrodynamics --------------------------------------
------------------------------------------------------------------------
Greg Ewing
2001-09-18 00:08:52 UTC
Permalink
Post by Chris Barker
Python is more general purpose, so the list sort() method has to do the
same thing as the comparison operators.
I don't think that's true. The sort() method could first look
for a __cmp__ method, and __cmp__ for complex numbers could
impose an arbitary ordering, independently of what <, >, <=,
Post by Chris Barker
= do.
--
Greg Ewing, Computer Science Dept, University of Canterbury,
Christchurch, New Zealand
To get my email address, please visit my web page:
http://www.cosc.canterbury.ac.nz/~greg
Tim Roberts
2001-09-19 05:54:06 UTC
Permalink
l1 = [1, '1j', [1,'1j']]
l1.sort()
print l1
[1, [1, '1j'], '1j']
l2 = [1, 1j, [1,'1j']]
l2.sort()
File "<input>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=
This came up in the context of building the coefficients of polynomials
from a list of roots. If complex roots occur in complex conjugate pairs,
then the resulting coefficients must be real, so I decided to cast the
coefficients to floats in this case. A straightforward test is to take
the complex conjugate of each element of the list, then sort both lists
and see if they are the same. As is clear from the above, that definitely
didn't work!
You can make this work if you can answer a couple of simple questions.

Which is greater: 3 or 3j?

Put these numbers in order: 3+0j 1+1j 1+2j 2+1j 2+2j 1+0j 0+3j
--
- Tim Roberts, timr at probo.com
Providenza & Boekelheide, Inc.
Alex Martelli
2001-09-19 07:12:30 UTC
Permalink
"Tim Roberts" <timr at probo.com> wrote in message
news:4jcgqtsvc9dc7or96alisr6rhcv776qhd1 at 4ax.com...
...
Post by Tim Roberts
This came up in the context of building the coefficients of polynomials
from a list of roots. If complex roots occur in complex conjugate pairs,
then the resulting coefficients must be real, so I decided to cast the
coefficients to floats in this case. A straightforward test is to take
the complex conjugate of each element of the list, then sort both lists
and see if they are the same. As is clear from the above, that definitely
didn't work!
You can make this work if you can answer a couple of simple questions.
Which is greater: 3 or 3j?
Put these numbers in order: 3+0j 1+1j 1+2j 2+1j 2+2j 1+0j 0+3j
Any ordering will work for the original poster's application,
which is one of testing SETS -- he needs to test whether the
set of x's and the set of x.conjugate()'s are identical, as he
clearly explained in the just-quoted paragraph.

Of course, thanks to Python's dictionaries, roughly O(1) for
both insertion and membership-testing, there are better ways
[O(n) ones] to perform this test than the O(n log n) approach
of sorting lists. Moreover, dictionaries are finely tuned
so the multiplicative constants are also prety good -- not a
big theoretical issue but definitely a practical one!-)

E.g., the plainest and simplest approach would be OK:

def all_coefficients_are_real(roots):
rootset={}
for root in roots:
rootset[root]=1
for root in roots:
if not rootset.has_key(root.conjugate()):
return 0
return 1


This doesn't mean that arbitrary-ordering sorts of complex
numbers wouldn't be helpful in some other case -- just that,
even if they were available, it might be best not to
use them for this specific application.


Alex
Michael James Barber
2001-09-19 08:54:34 UTC
Permalink
Post by Alex Martelli
Of course, thanks to Python's dictionaries, roughly O(1) for
both insertion and membership-testing, there are better ways
[O(n) ones] to perform this test than the O(n log n) approach
of sorting lists. Moreover, dictionaries are finely tuned
so the multiplicative constants are also prety good -- not a
big theoretical issue but definitely a practical one!-)
Definitely good points, and I'll probably be modifying my code to use this
idea, if performance proves to be a problem.
Post by Alex Martelli
rootset={}
rootset[root]=1
return 0
return 1
Actually, this won't work in general. Consider having repeated roots of,
say, [1j,1j,-1j].

It needs to be slightly modified to something like:

def all_coefficient_are_real(roots):
rootset = {}
for root in roots:
rootset[root] = rootset.get(root,0)+1
for root in roots:
if rootset[root] != rootset.get(root.conjugate(),0):
return 0
return 1

Untested, but it looks right.
Post by Alex Martelli
This doesn't mean that arbitrary-ordering sorts of complex
numbers wouldn't be helpful in some other case -- just that,
even if they were available, it might be best not to
use them for this specific application.
I agree totally. The list I asked about in the original post was really
for rhetorical purposes: one element of the list was another list,
specifically to prevent this remapping to a dictionary. I have to admit,
I don't have any idea where I'd need to sort such a list--but of course, I
probably would have said the same thing about lists with complex numbers
about a week ago.

I'd like to thank all the respondents. I've learned a bit, and definitely
found the thread thought provoking so far. Hopefully, others have as well.
--
Michael J. Barber
Grant Griffin
2001-09-21 15:58:49 UTC
Permalink
In article <4jcgqtsvc9dc7or96alisr6rhcv776qhd1 at 4ax.com>, Tim says...
Post by Tim Roberts
l1 = [1, '1j', [1,'1j']]
l1.sort()
print l1
[1, [1, '1j'], '1j']
l2 = [1, 1j, [1,'1j']]
l2.sort()
File "<input>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=
This came up in the context of building the coefficients of polynomials
from a list of roots. If complex roots occur in complex conjugate pairs,
then the resulting coefficients must be real, so I decided to cast the
coefficients to floats in this case. A straightforward test is to take
the complex conjugate of each element of the list, then sort both lists
and see if they are the same. As is clear from the above, that definitely
didn't work!
You can make this work if you can answer a couple of simple questions.
Which is greater: 3 or 3j?
3j: both have the same magnitude, but 3j has a greater phase (90 degrees as
opposed to 0). So I'm gonna say 3j is greater. (Does anybody care to fight me
to the death over that one <wink>?)
Post by Tim Roberts
Put these numbers in order: 3+0j 1+1j 1+2j 2+1j 2+2j 1+0j 0+3j
OK. Here's an ordering based on comparing the inphase, then the quadrature
components:

0+3j 1+0j 1+1j 1+2j 2+1j 2+2j 3+0j

Of course, other orderings are possible based on other comparison conventions.

I like to think of complex numbers as being "two-valued numbers" which can be
represented equivalently either in Cartesian form (x + jy) or polar form
(magnitude at phase--kindda like e-mail <wink>). The concept of "equality" of
complex numbers is perfectly mathematically sensible, but the concept of "less
than", and "greater than" make sense only in terms of a complex number's two
component real values (either inphase/quadrature or magnitude/phase).

For the purposes of sorting, it is entirely sensible to use any convention for
comparison that compares one of the two real values individually, then breaks
ties using the other one. Of course, you could do this in either Cartesian or
polar representation (assuming the phase has been normalized). Those
conventions would have different--but consistent--results.

In Python, it is more expedient to do comparisons based on the Cartesian
representation since that is what Python uses internally to store complex
numbers. However, the most generally useful method would be to compare first on
magnitude, then on phase (and assuming normalization of phase to the range of
+/- 180 degrees) would probably be . (A complex number's magnitude is what we
generally think of as its "size", so a complex number with a bigger magnitude
seems to be "greater".)

Note that Python has something of an inconsistency in the fact that it happily
Post by Tim Roberts
a=1
b=[0,2,3]
a>b
0
Post by Tim Roberts
c=[2,3,4]
a>c
0
Post by Tim Roberts
t=()
l=[]
t>l
1
Post by Tim Roberts
c1=1+1j
c2=2+2j
cmp(c1,c2)
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=
Post by Tim Roberts
c1<c1
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=

Presumably this is by design: perhaps Python doesn't want to mislead you that
these operations are mathematically meaningful when they aren't. (BTW, neither
is comparing different data types, bug I guess you're supposed to figure that
one out yourself.)

For sorting, you could try comparing complex numbers based on their hashed
Post by Tim Roberts
hash(c1)
1000004
Post by Tim Roberts
hash(c2)
2000008

Since the hashed values are integers, one can compare based on those. Hashed
valued are not guaranteed to be unique (specifically, one can't uniquely squeeze
two floating-point valuess into a single integer), but for most practical
purposes, Python's complex hash function presumably has been designed so there's
a good chance they are. (But before doing this, I'd peek at the hashing
function inside complexobject.c if I were you: looks kindda suspicious to me
<wink>.)

For example:

hash_cmp = lambda a,b: cmp(hash(a), hash(b))
cpx_list = [3+0j, 1+1j, 1+2j, 2+1j, 2+2j, 1+0j, 0+3j]
cpx_list.sort(hash_cmp)
print cpx_list

yields:

[(1+0j), (3+0j), (1+1j), (2+1j), (1+2j), (2+2j), 3j]

Even better, you could create a custom complex "cmp" function that works in a
comparison-of-a-pair-of-real-values sense, which you could then feed to Python's
sort method. For fun, I decided to try to come up with a lambda for that:

Cartesian_cmp = lambda a,b: (a.real != b.real) * cmp(a.real, b.real) + \
(a.real == b.real) * cmp(a.imag, b.imag)

(The essential trick here is to use a multiply by an equality to avoid the "if"
statement lambda doesn't allow.)

With that comparison function in hand, the following:

cpx_list.sort(Cartesian_cmp)

yields:

[3j, (1+0j), (1+1j), (1+2j), (2+1j), (2+2j), (3+0j)]

which is the same as the manual result I gave at top.

And then there's the polar (magnitude/phase) version:

from math import *
polar_cmp = lambda a,b: (abs(a) != abs(b)) * cmp(abs(a), abs(b)) + \
(abs(a) == abs(b)) * cmp(atan2(a.imag, a.real), atan2(b.imag, b.real))

which yeids:

[(1+0j), (1+1j), (2+1j), (1+2j), (2+2j), (3+0j), 3j]

never-let-theory-stand-in-the-way-of-practice-ly y'rs,

=g2

_____________________________________________________________________

Grant R. Griffin g2 at dspguru.com
Publisher of dspGuru http://www.dspguru.com
Iowegian International Corporation http://www.iowegian.com
William Park
2001-09-21 18:32:01 UTC
Permalink
Simpler is
Cartesian_cmp = lambda a, b: cmp((a.real, a.imag), (b.real, b.imag))
That is, sequences in Python are compared lexicographically, and tuples are
a sequence type; you don't have to fake lexicographic comparison by hand.
+ Python used to compare complex numbers that way.
Then, how does Python compare complex now?
--
William Park, Open Geometry Consulting, <opengeometry at yahoo.ca>
8 CPU cluster, (Slackware) Linux, Python, LaTeX, Vim, Mutt, Sc.
Tim Peters
2001-09-21 19:36:03 UTC
Permalink
[William Park]
Thanks, I thought complex was treated just like tuple...
It used to be. Reread my original msg for why it used it to be treated that
way, and why it isn't treated that way anymore.
Brian Quinlan
2001-09-18 00:26:57 UTC
Permalink
I don't think that's true. The sort() method could first look
for a __cmp__ method, and __cmp__ for complex numbers could
impose an arbitary ordering, independently of what <, >, <=,
= do.
But what would the point be? The current implementation is telling you
that there is no meaningful sort order that it can impose. If you have
some sort order in mind then you should use that by providing your own
comparison function. If not, why are you bothering with the sort?

Cheers,
Brian
Toby Dickenson
2001-09-18 12:12:55 UTC
Permalink
Post by Greg Ewing
Post by Brian Quinlan
But what would the point be? The current implementation is telling you
that there is no meaningful sort order that it can impose.
The point would be to make sort() impose an ordering on
everything, arbitrary where necessary. That's what the
original poster was asking for, and I was pointing out
that the new rich-comps stuff doesn't make it impossible.
Whether it's a good idea or not is another question.
Personally I can't see how it would hurt anything, and
it can sometimes be useful.
I like the C++ solution to this issue. A class can define two
different sorting orders for its instances...

Classes can overload the comparison operators to define the 'natural'
sorting order. The complex type doesnt do this, because there is no
'natural' ordering.

Seperately, classes can provide the cmp<> template function to define
a potentially arbitrary ordering. cmp<> can be used by data structures
that need to sort their content, but dont mind if the sort order is
not meaningful (for example, a C++ map<> container is similar to a
python dictionary, but uses a sorted tree of keys rather than hashes)
Post by Greg Ewing
But if you want to be purist about it, I'd suggest that
sort() should refuse to compare objects of different types,
either. Presently it's quite happy to impose an arbitrary
ordering in that case.
Greg Ewing, Computer Science Dept, +--------------------------------------+
University of Canterbury, | A citizen of NewZealandCorp, a |
Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. |
greg at cosc.canterbury.ac.nz +--------------------------------------+
Toby Dickenson
tdickenson at geminidataloggers.com
Michael James Barber
2001-09-17 10:09:21 UTC
Permalink
l1 = [1, '1j', [1,'1j']]
l1.sort()
print l1
[1, [1, '1j'], '1j']
l2 = [1, 1j, [1,'1j']]
l2.sort()
Traceback (most recent call last):
File "<input>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=


This came up in the context of building the coefficients of polynomials
from a list of roots. If complex roots occur in complex conjugate pairs,
then the resulting coefficients must be real, so I decided to cast the
coefficients to floats in this case. A straightforward test is to take
the complex conjugate of each element of the list, then sort both lists
and see if they are the same. As is clear from the above, that definitely
didn't work!

For the particular problem I was working on, it was simple to find a
workaround that was only slightly awkward. I don't have any idea how to
address the case shown above. Admittedly, it is largely a rhetorical
question, but what do people think is the "one obvious way" to sort such
a list? The goal is an "arbitrary but deterministic" sort, much like with
other heterogeneous lists.


In a larger sense, this is a frustrating aspect of Python's numerical
model. PEP 228 looks like a good start on treating all numbers just as
numbers, without the surprises that can arise now. But where do
comparisons of complex numbers fit in? Is it better to be mathematically
correct and raise an exception, or to have complex numbers respond in a
useful, but not really correct, fashion to all comparisons?

I've used Matlab extensively for about 8 years (although a lot less often
since discovering Python and Numeric about a year ago!). In Matlab,
complex numbers are sorted based on their magnitudes, and then by phase
angle if the magnitudes are the same. Comparing complex numbers using <,
<=, >, and >= always returns false. I've known about the sorting for
quite a while, but only learned about the behavior of the comparison
operators after discovering Python's behavior yesterday. While not
strictly correct mathematically, I suspect that Matlab's approach is a
good practical approach, since it took me so long to notice. I don't know
what Mathematica and others do.
--
Michael J. Barber
Ken Seehof
2001-09-17 17:30:08 UTC
Permalink
l1 = [1, '1j', [1,'1j']]
l1.sort()
print l1
[1, [1, '1j'], '1j']
l2 = [1, 1j, [1,'1j']]
l2.sort()
File "<input>", line 1, in ?
TypeError: cannot compare complex numbers using <, <=, >, >=
This came up in the context of building the coefficients of polynomials
from a list of roots. If complex roots occur in complex conjugate pairs,
then the resulting coefficients must be real, so I decided to cast the
coefficients to floats in this case. A straightforward test is to take
the complex conjugate of each element of the list, then sort both lists
and see if they are the same. As is clear from the above, that definitely
didn't work!
For the particular problem I was working on, it was simple to find a
workaround that was only slightly awkward. I don't have any idea how to
address the case shown above. Admittedly, it is largely a rhetorical
question, but what do people think is the "one obvious way" to sort such
a list? The goal is an "arbitrary but deterministic" sort, much like with
other heterogeneous lists.
In a larger sense, this is a frustrating aspect of Python's numerical
model. PEP 228 looks like a good start on treating all numbers just as
numbers, without the surprises that can arise now. But where do
comparisons of complex numbers fit in? Is it better to be mathematically
correct and raise an exception, or to have complex numbers respond in a
useful, but not really correct, fashion to all comparisons?
I've used Matlab extensively for about 8 years (although a lot less often
since discovering Python and Numeric about a year ago!). In Matlab,
complex numbers are sorted based on their magnitudes, and then by phase
angle if the magnitudes are the same. Comparing complex numbers using <,
<=, >, and >= always returns false. I've known about the sorting for
quite a while, but only learned about the behavior of the comparison
operators after discovering Python's behavior yesterday. While not
strictly correct mathematically, I suspect that Matlab's approach is a
good practical approach, since it took me so long to notice. I don't know
what Mathematica and others do.
--
Michael J. Barber
I agree. The current approach of raising an exception is inconsistent with
all other sorting protocols in python. You can sort by tuples, types, and
even heterogeneous data! So why should complex numbers be so special?

Complex numbers should be sortable even though it doesn't seem to make
mathematical sense to some people. Of course, all multi-dimensional
domains -are- sortable: it is just a matter of selecting the sort keys.

For compatibility, Matlab's approach (A, theta) is tempting, but this
would not be compatible with python thinking (especially the new way
of looking at numbers(whether you agree with this new way or not)).
I was thinking that sorting by (real, imag) would be more appropriate,
that way 2 behaves the same as (2.0+0.0j), which is necessary for
the grand numeric unification.

Matlab says that you can sort, but not compare complex numbers.
This won't work in python because sorting and comparing are the
same thing.

Sorting complex numbers feels mathematically strange to me; I'm not
saying that it doesn't. But the current policy of raising an exception is
based on a false premise: that "(2.0+1.0j) > (2.0+0.9j)" makes less
sense than "type(3.4) > ['spam', 52]".

Hmm, how about sensibility sorting? :-)

if sensibility("type(3.4) > 'spam'") > sensibility("2.0+1.0j > 2.0"):
run_away_run_away()

Obviously the policy of python is that all things are sortable. I really
can't imagine how complex numbers got left out.

Finally, there is the practical argument: Michael has given an example
of useful sorting of complex numbers. To counter this, someone must
show an example of a realistic hypothetical bug where a programmer
accidentally sorts or compares complex numbers with devastating
results which would have been avoided if an exception had been
raised.

All experienced programmers know this:
importance(consistency) > importance(sensibility)

Is there a PEP for this? I couldn't find one. It doesn't seem to be part
of 228, though obviously it would be a requirement for 228. If nobody
responds to me that a PEP already exists, I'll make one.

- Ken
Michael James Barber
2001-09-18 09:09:39 UTC
Permalink
In article <mailman.1000739421.20070.python-list at python.org>,
Skip Montanaro <skip at pobox.com> wrote:
[my question about sorting heterogeneous lists snipped]
Seems to me that you need to convert complex numbers to reals for
comparison. That can be done a number of ways. Some that come immediately
* compare them as tuples, e.g., compare 1+2j as (1,2)
This is what I wound up using, actually. For the particular case I was
interested in, changing representations made sense and was easy to do.
Naturally, comparing these alternate representations of complex numbers
is every bit as incorrect mathematically as the direct comparison.
Which you choose will depend on your application.
[example comparison function snipped]
There is a definite appeal to this approach. Raise errors for "wrong"
comparisons, and have the user define a convention as appropriate. Of
course, comparing non-numeric types is arguably wrong as well, but the
lexicographical sort is so familiar that we don't really notice.

Thanks for the thought-provoking comment. I think I'm going to have to
consider this very carefully before I decide if it's "obvious" or not!
--
Michael J. Barber
Skip Montanaro
2001-09-17 15:08:39 UTC
Permalink
Michael> For the particular problem I was working on, it was simple to
Michael> find a workaround that was only slightly awkward. I don't have
Michael> any idea how to address the case shown above. Admittedly, it
Michael> is largely a rhetorical question, but what do people think is
Michael> the "one obvious way" to sort such a list? The goal is an
Michael> "arbitrary but deterministic" sort, much like with other
Michael> heterogeneous lists.

Seems to me that you need to convert complex numbers to reals for
comparison. That can be done a number of ways. Some that come immediately
to mind include:

* compare them as tuples, e.g., compare 1+2j as (1,2)
* ignore either the real or imaginary part
* compare them using magnitudes

Which you choose will depend on your application.

Here's an example of ignoring the imaginary part:

def _cmp(x,y):
if hasattr(x, "real"):
x = x.real
if hasattr(y, "real"):
y = y.real
return cmp(x,y)

l2 = [1, 1j, [1,'1j']]
l2.sort(_cmp)
print l2
--
Skip Montanaro (skip at pobox.com)
http://www.mojam.com/
http://www.musi-cal.com/
Michael James Barber
2001-09-18 09:44:51 UTC
Permalink
In article <mailman.1000747640.16457.python-list at python.org>,
Post by Ken Seehof
Finally, there is the practical argument: Michael has given an example
of useful sorting of complex numbers. To counter this, someone must
show an example of a realistic hypothetical bug where a programmer
accidentally sorts or compares complex numbers with devastating
results which would have been avoided if an exception had been
raised.
I'd be interested to hear about such examples, too. This was the behavior
in Python 1.5, so possibly there are real examples, not just hypothetical
ones?
Post by Ken Seehof
importance(consistency) > importance(sensibility)
Is there a PEP for this? I couldn't find one. It doesn't seem to be part
of 228, though obviously it would be a requirement for 228. If nobody
responds to me that a PEP already exists, I'll make one.
Take a look at PEP 207 for something related. Given rich comparisons, the
most consistent and correct approach is, arguably, to eliminate
comparisons of different types (except, presumably, int and float?).

PEP 209, concerning revisions to Numeric, is also relevant. I suspect
that most people using complex numbers also tend to use Numeric, so the
most sensible approach may be to have different sorting behavior for lists
and multiarrays. Clashes with the inequality above, though.

If you decide to write a PEP, I am willing to help. At this point, I am
not certain what the right behavior is, but I do think it is worth getting
the rationale shown. I also think it is relevant for 228, which I see as
very important.
--
Michael J. Barber
Tim Peters
2001-09-21 18:45:14 UTC
Permalink
[William Park]
Then, how does Python compare complex now?
[Ignacio Vazquez-Abrams]
It doesn't; it raises an exception.
For <, <=, >, >= and cmp. == and != are non-exceptional and do "the
obvious" thing.
Tim Peters
2001-09-21 18:17:35 UTC
Permalink
[Grant Griffin]
...
Cartesian_cmp = lambda a,b: (a.real != b.real) * cmp(a.real, b.real) + \
(a.real == b.real) * cmp(a.imag, b.imag)
Why lambda? Surely

def Cartesian_cmp(a, b):
if a.real == b.real:
return cmp(a.imag, b.imag)
else:
return cmp(a.real, b.real)

is clearer.

Simpler is

Cartesian_cmp = lambda a, b: cmp((a.real, a.imag), (b.real, b.imag))

That is, sequences in Python are compared lexicographically, and tuples are
a sequence type; you don't have to fake lexicographic comparison by hand.

Notes:

+ Python used to compare complex numbers that way.

+ For technical implementation reasons, it used to be impossible to
raise an exception from a comparison function. That's the real reason
Python defined comparison on any pair of objects of builtin types:
it had no choice. User-defined __cmp__ functions could try to raise
exceptions, but if they did such exceptions were ignored.

+ Since all comparisons used to go through __cmp__, it was impossible
for a comparison implementation to know which specific comparison
was desired.

+ Eventually, it became possible to raise exceptions from comparisons,
and, later, "rich comparisons" added the ability to know which
specific comparison was desired. After both of those were in place,
Guido was keen to allow complex comparisons only of the == and !=
flavors. Python "in his head" always worked that way; it just took
a few years for the implementation to catch up <wink>.

channeling-is-a-vital-life-skill-ly y'rs - tim
Greg Ewing
2001-09-18 01:04:44 UTC
Permalink
Post by Brian Quinlan
But what would the point be? The current implementation is telling you
that there is no meaningful sort order that it can impose.
The point would be to make sort() impose an ordering on
everything, arbitrary where necessary. That's what the
original poster was asking for, and I was pointing out
that the new rich-comps stuff doesn't make it impossible.

Whether it's a good idea or not is another question.
Personally I can't see how it would hurt anything, and
it can sometimes be useful.

But if you want to be purist about it, I'd suggest that
sort() should refuse to compare objects of different types,
either. Presently it's quite happy to impose an arbitrary
ordering in that case.

Greg Ewing, Computer Science Dept, +--------------------------------------+
University of Canterbury, | A citizen of NewZealandCorp, a |
Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. |
greg at cosc.canterbury.ac.nz +--------------------------------------+
Grant Griffin
2001-09-21 22:17:37 UTC
Permalink
In article <mailman.1001096306.20291.python-list at python.org>, "Tim says...
Post by Tim Peters
[Grant Griffin]
...
Cartesian_cmp = lambda a,b: (a.real != b.real) * cmp(a.real, b.real) + \
(a.real == b.real) * cmp(a.imag, b.imag)
Why lambda? Surely
return cmp(a.imag, b.imag)
return cmp(a.real, b.real)
is clearer.
Like I said, I used lambda just for fun. Also, I've been polishing my lambda
skills lately to make it easier to sort dictionaries by value <wink>.
Post by Tim Peters
Simpler is
Cartesian_cmp = lambda a, b: cmp((a.real, a.imag), (b.real, b.imag))
That is, sequences in Python are compared lexicographically, and tuples are
a sequence type; you don't have to fake lexicographic comparison by hand.
Cool!--I hadn't thought of that!

I guess it's axiomatic that a one-liner that fits on one line is much better
than a one-liner that doesn't.

But waitaminute! Are there two ways to do it?--or are they just not obvious?
Post by Tim Peters
+ Python used to compare complex numbers that way.
+ For technical implementation reasons, it used to be impossible to
raise an exception from a comparison function. That's the real reason
it had no choice.
Even so, I think it's a good idea.

...
Post by Tim Peters
+ Eventually, it became possible to raise exceptions from comparisons,
and, later, "rich comparisons" added the ability to know which
specific comparison was desired. After both of those were in place,
Guido was keen to allow complex comparisons only of the == and !=
flavors.
Don't tell him, then, how my cold little DSP heart warmed to see that list
sorted in magnitude/phase order.

In all fairness, though, I've never had a need to sort a list of complex
numbers.

dictionaries-by-value-is-another-story-<wink>-ly y'rs,

=g2

_____________________________________________________________________

Grant R. Griffin g2 at dspguru.com
Publisher of dspGuru http://www.dspguru.com
Iowegian International Corporation http://www.iowegian.com
Continue reading on narkive:
Loading...