By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,584 Members | 1,757 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,584 IT Pros & Developers. It's quick & easy.

sorting list of complex numbers

P: n/a
The thread on sorting in Python 3 got me to thinking. How could I sort a
list of complex numbers using key?
>>lst = [random.random()+random.random()*1j for i in range(10)]
lst
[(0.32672251849959244+0.41428983433288791j), (0.35238056484609881+0.92758203977208264j), (0.19337824038125528+0.16527285180541951j), (0.47569307114525849+0.72381960418815128j), (0.21498813135082351+0.2046308266222292j), (0.30142745756937939+0.35216751451102601j), (0.77355676386939132+0.0023447924287695043j), (0.2547736124606309+0.52234837788936905j), (0.38349189081350132+0.62017617694427096j), (0.58362096773561245+0.87702443273108477j)]

As expected:
>>sorted(lst)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

This works:
>>sorted(lst, key=lambda x: x.real)
[(0.19337824038125528+0.16527285180541951j), (0.21498813135082351+0.2046308266222292j), (0.2547736124606309+0.52234837788936905j), (0.30142745756937939+0.35216751451102601j), (0.32672251849959244+0.41428983433288791j), (0.35238056484609881+0.92758203977208264j), (0.38349189081350132+0.62017617694427096j), (0.47569307114525849+0.72381960418815128j), (0.58362096773561245+0.87702443273108477j), (0.77355676386939132+0.0023447924287695043j)]

but what if I want to sort by real, then imaginary parts? Here's a longer
list with 20 elements where there are only 10 distinct reals but 20 distinct
imaginaries:
>>pprint.pprint(lst)
[(1+2.73j),
(9+3.77j),
(7+27j),
(8+28j),
(2+2.8600000000000003j),
(4+3.1200000000000001j),
(2+22j),
(9+29j),
(3+2.9900000000000002j),
(6+26j),
2.6000000000000001j,
(8+3.6400000000000001j),
(3+23j),
(5+3.25j),
(1+21j),
(5+25j),
20j,
(6+3.3799999999999999j),
(7+3.5100000000000002j),
(4+24j)]

I can sort by the real parts just fine:
>>lst.sort(key=lambda x: x.real)
pprint.pprint(lst)
[2.6000000000000001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000000003j),
(2+22j),
(3+2.9900000000000002j),
(3+23j),
(4+3.1200000000000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999999999j),
(7+27j),
(7+3.5100000000000002j),
(8+28j),
(8+3.6400000000000001j),
(9+3.77j),
(9+29j)]

but how do I then do a secondary sort by the imaginary part, preserving the
existing ordering on the real parts? Seems like I have to resort to a
Schwartzian transform and map the complex numbers to tuples, sort that, then
map them back. With the cmp key it would have been a fairly trivial task to
define the desired compare-real-then-imag function.

Is there a way to do this using just the key arg, no extra data structures?

Skip
Nov 9 '08 #1
Share this Question
Share on Google+
16 Replies


P: n/a
sk**@pobox.com wrote:
I can sort by the real parts just fine:
>>lst.sort(key=lambda x: x.real)
>>pprint.pprint(lst)
[2.6000000000000001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000000003j),
(2+22j),
(3+2.9900000000000002j),
(3+23j),
(4+3.1200000000000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999999999j),
(7+27j),
(7+3.5100000000000002j),
(8+28j),
(8+3.6400000000000001j),
(9+3.77j),
(9+29j)]

but how do I then do a secondary sort by the imaginary part, preserving the
existing ordering on the real parts? Seems like I have to resort to a
Schwartzian transform and map the complex numbers to tuples, sort that, then
map them back. With the cmp key it would have been a fairly trivial task to
define the desired compare-real-then-imag function.

Is there a way to do this using just the key arg, no extra data structures?
Is a tuple an extra data structure?
>>lst.sort(key=lambda x: (x.real,x.imag))
pprint.pprint(lst)
[2.6000000000000001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000000003j),
(2+22j),
(3+2.9900000000000002j),
(3+23j),
(4+3.1200000000000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+3.3799999999999999j),
(6+26j),
(7+3.5100000000000002j),
(7+27j),
(8+3.6400000000000001j),
(8+28j),
(9+3.77j),
(9+29j)]

If you don't like the tuple then just do the two sorts separately:
>>lst.sort(key=lambda x: x.imag)
lst.sort(key=lambda x: x.real)
pprint.pprint(lst)
[2.6000000000000001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000000003j),
(2+22j),
(3+2.9900000000000002j),
(3+23j),
(4+3.1200000000000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+3.3799999999999999j),
(6+26j),
(7+3.5100000000000002j),
(7+27j),
(8+3.6400000000000001j),
(8+28j),
(9+3.77j),
(9+29j)]
>>>
Nov 9 '08 #2

P: n/a
sk**@pobox.com schrieb:
The thread on sorting in Python 3 got me to thinking. How could I sort a
list of complex numbers using key?
>>lst = [random.random()+random.random()*1j for i in range(10)]
>>lst
[(0.32672251849959244+0.41428983433288791j), (0.35238056484609881+0.92758203977208264j), (0.19337824038125528+0.16527285180541951j), (0.47569307114525849+0.72381960418815128j), (0.21498813135082351+0.2046308266222292j), (0.30142745756937939+0.35216751451102601j), (0.77355676386939132+0.0023447924287695043j), (0.2547736124606309+0.52234837788936905j), (0.38349189081350132+0.62017617694427096j), (0.58362096773561245+0.87702443273108477j)]

As expected:
>>sorted(lst)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

This works:
>>sorted(lst, key=lambda x: x.real)
[(0.19337824038125528+0.16527285180541951j), (0.21498813135082351+0.2046308266222292j), (0.2547736124606309+0.52234837788936905j), (0.30142745756937939+0.35216751451102601j), (0.32672251849959244+0.41428983433288791j), (0.35238056484609881+0.92758203977208264j), (0.38349189081350132+0.62017617694427096j), (0.47569307114525849+0.72381960418815128j), (0.58362096773561245+0.87702443273108477j), (0.77355676386939132+0.0023447924287695043j)]

but what if I want to sort by real, then imaginary parts? Here's a longer
list with 20 elements where there are only 10 distinct reals but 20 distinct
imaginaries:
>>pprint.pprint(lst)
[(1+2.73j),
(9+3.77j),
(7+27j),
(8+28j),
(2+2.8600000000000003j),
(4+3.1200000000000001j),
(2+22j),
(9+29j),
(3+2.9900000000000002j),
(6+26j),
2.6000000000000001j,
(8+3.6400000000000001j),
(3+23j),
(5+3.25j),
(1+21j),
(5+25j),
20j,
(6+3.3799999999999999j),
(7+3.5100000000000002j),
(4+24j)]

I can sort by the real parts just fine:
>>lst.sort(key=lambda x: x.real)
>>pprint.pprint(lst)
[2.6000000000000001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000000003j),
(2+22j),
(3+2.9900000000000002j),
(3+23j),
(4+3.1200000000000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999999999j),
(7+27j),
(7+3.5100000000000002j),
(8+28j),
(8+3.6400000000000001j),
(9+3.77j),
(9+29j)]

but how do I then do a secondary sort by the imaginary part, preserving the
existing ordering on the real parts? Seems like I have to resort to a
Schwartzian transform and map the complex numbers to tuples, sort that, then
map them back. With the cmp key it would have been a fairly trivial task to
define the desired compare-real-then-imag function.

Is there a way to do this using just the key arg, no extra data structures?
Doesn't (untested)

key=lambda x: (x.real, x.imag)

work?

Diez
Nov 9 '08 #3

P: n/a
>Timeit suggests the single sort returning the real, imag tuples is
faster than two sorts each on one field, as you might expect since
many fewer calls to the key function are made.
SteveOnly half the number, of course. The advantage of the key
Stevefunction is that each element requires only one call out to a
StevePython function, and the comparisons then take place using a
SteveC-coded comparison function.

SteveBut you knew that already, right?

I knew about the C comparison function, not about the number of key calls.
I sort of assumed the key function was called whenever necessary since it
could have side effects. I confirmed that the key function is called once
per element instead of once per comparison.

Thanks,

Skip

Nov 10 '08 #4

P: n/a
Thomas Bellman wrote:
Steve Holden <st***@holdenweb.comwrote:
>Only half the number, of course. The advantage of the key function is
that each element requires only one call out to a Python function, and
the comparisons then take place using a C-coded comparison function.

You don't need any Python-coded function at all. The operator
module is your friend: key=operator.attrgetter('real', 'imag')
will create the required tuples for sorting.
True; "requires only one call out to the key function", then. You're
right, attrgetter will be faster still, and it's a really neat solution.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/

Nov 12 '08 #5

P: n/a
Duncan Booth <du**********@invalid.invalidwrites:
If you don't like the tuple then just do the two sorts separately:
>lst.sort(key=lambda x: x.imag)
lst.sort(key=lambda x: x.real)
pprint.pprint(lst)
That only goes so far though. Suppose instead of complex numbers
you want to sort expressions, like:

a(b,c(d,e),f(g,h))

treat those as parse trees in the obvious way. You want to compare on
the root, and if the roots are equal, compare the left subtree, then
the right subtree, etc. Do you REALLY want to sort over and over
all the way to the max depth of all the trees?

I don't understand what the purpose of was of getting rid of the cmp
arg. It just seems to gratuitously make code hard to write.

Another thing that apparently broke was tuple destructuring in
function args. You can no longer say

def first((a,b)): return a
def second((a,b)): return b

make getters for the first and second elements of a tuple. Sure, you
could use operator.itemgetter for that example, but often you want to
parse out more complicated nested tuples. I do that all the time with
Python 2.5 (typically in conjunction with itertools.groupby) but
if/when I downgrade to 3.0, a bunch of my code is going to break.
Nov 18 '08 #6

P: n/a
sk**@pobox.com writes:
but how do I then do a secondary sort by the imaginary part,...
Is there a way to do this using just the key arg, no extra data structures?
Clever solutions involving multiple sorts aside, I think what they
really want you to do is something like (untested):

class mkKey(complex):
def __lt__(self, other):
a = cmp(self.real, other.real)
return a if a else cmp(self.imag, other.imag)

then:

yourlist.sort(key=mkKey)

for fancier structures you'd need a full blown class implementation
with an init method. Either way you end up temporarily allocating a
lot of extra structures, but at least they're not all in memory
simultaneously like in the DSU pattern.
Nov 18 '08 #7

P: n/a
En Tue, 18 Nov 2008 08:41:58 -0200, Paul Rubin
<"http://phr.cx"@nospam.invalidescribió:
sk**@pobox.com writes:
>but how do I then do a secondary sort by the imaginary part,...
Is there a way to do this using just the key arg, no extra data
structures?

Clever solutions involving multiple sorts aside, I think what they
really want you to do is something like (untested):

class mkKey(complex):
def __lt__(self, other):
a = cmp(self.real, other.real)
return a if a else cmp(self.imag, other.imag)

then:

yourlist.sort(key=mkKey)

for fancier structures you'd need a full blown class implementation
with an init method. Either way you end up temporarily allocating a
lot of extra structures, but at least they're not all in memory
simultaneously like in the DSU pattern.
Yes, the keys for all items in the list are all created when the sort
begins, and live until the sort finishes. list.sort(key=...) is actually
implemented using the DSU pattern, something like this:

for i in range(len(alist)):
alist[i] = (key(alist[i]), alist[i])
# ...sort items...
for i in range(len(alist)):
alist[i] = alist[i][1]

except a custom `sortwrapper` object is used instead of a 2-item tuple.

--
Gabriel Genellina

Nov 18 '08 #8

P: n/a
Paul Rubin <http://ph****@NOSPAM.invalidwrites:
for fancier structures you'd need a full blown class implementation
with an init method. Either way you end up temporarily allocating a
lot of extra structures, but at least they're not all in memory
simultaneously like in the DSU pattern.
The implementation of python sort uses the DSU patterns.

--
Arnaud
Nov 18 '08 #9

P: n/a
Paul Rubin wrote:
That only goes so far though. Suppose instead of complex numbers
you want to sort expressions, like:

a(b,c(d,e),f(g,h))

treat those as parse trees in the obvious way.
Presuming that a, c, and f are function calls that return Tree
instances, you give Tree a __lt__ member that does what you say below.
You want to compare on
the root, and if the roots are equal, compare the left subtree, then
the right subtree, etc.
Do you REALLY want to sort over and over
all the way to the max depth of all the trees?
Don't understand this.
I don't understand what the purpose of was of getting rid of the cmp
arg.
Cmp requires a 3-way classification. Sorting only requires 2-way.
cmp was called nlogn times, key n times.
cmp in practical use amounted to calling some key function on both
items, so cmp amounted to 2*n*log(n) key calls pluse extra overhead.
Another thing that apparently broke was tuple destructuring in
function args. You can no longer say

def first((a,b)): return a
def second((a,b)): return b

make getters for the first and second elements of a tuple. Sure, you
could use operator.itemgetter for that example, but often you want to
parse out more complicated nested tuples. I do that all the time with
Python 2.5 (typically in conjunction with itertools.groupby) but
if/when I downgrade to 3.0, a bunch of my code is going to break.
Do your tuple destructuring in the first statement in your body and
nothing will break. Don't upgrade until it is an upgrade for *you*.

Nov 18 '08 #10

P: n/a
Terry Reedy <tj*****@udel.eduwrites:
Do your tuple destructuring in the first statement in your body and
nothing will break.
Unless you were using a lambda, which is quite useful as argument to
"sort".
Nov 19 '08 #11

P: n/a
Hrvoje Niksic wrote:
Terry Reedy <tj*****@udel.eduwrites:
>Do your tuple destructuring in the first statement in your body and
nothing will break.

Unless you were using a lambda, which is quite useful as argument to
"sort".
So write a separate def statement.
If you do not want to do that, don't run with 3.0.

Nov 19 '08 #12

P: n/a
Terry Reedy <tj*****@udel.eduwrites:
Hrvoje Niksic wrote:
>Terry Reedy <tj*****@udel.eduwrites:
>>Do your tuple destructuring in the first statement in your body and
nothing will break.

Unless you were using a lambda, which is quite useful as argument to
"sort".

So write a separate def statement.
That is a valid possibility, but loses the succinctness of a short
lambda. Some uses of lambda+unpacking can also be replaced by
operator.itemgetter.
If you do not want to do that, don't run with 3.0.
Tuple unpacking in parameters is a useful feature, but hardly reason
enough to abandon the future of the language.
Nov 19 '08 #13

P: n/a
Terry Reedy <tj*****@udel.eduwrites:
Do your tuple destructuring in the first statement in your body and
nothing will break.
Why get rid of a useful feature that unclutters code?
Unless you were using a lambda, which is quite useful as argument to
"sort".

So write a separate def statement.
If you do not want to do that, don't run with 3.0.
You are advising avoiding downgrading from 2.5 to 3.0, which is maybe
the best plan for some users under the circumstances, but some of us
normally expect a new major release to be an upgrade rather than a
downgrade.
Nov 20 '08 #14

P: n/a
Paul Rubin wrote:
Terry Reedy <tj*****@udel.eduwrites:
>>>Do your tuple destructuring in the first statement in your body and
nothing will break.

Why get rid of a useful feature that unclutters code?
Because, as has been posted before, it is rarely used, it is
replaceable, its presence interfered with adding a new signature option,
and its removal uncluttered a bit the C code.
>
Nov 20 '08 #15

P: n/a
On Wed, 19 Nov 2008 18:39:27 -0800, Paul Rubin wrote:
Terry Reedy <tj*****@udel.eduwrites:
>Do your tuple destructuring in the first statement in your body and
nothing will break.

Why get rid of a useful feature that unclutters code?
Unfortunately, the people who find it useful are a minority. Most people
don't care for it, and the Python dev team decided that the code they
most wanted to unclutter was their own CPython implementation.

Personally, I'm with you on this one: it's a small step backwards. But
only a *small* step. Whether it is outweighed by the steps forward, well,
time will tell.
--
Steven
Nov 21 '08 #16

P: n/a
Steven D'Aprano wrote:
On Wed, 19 Nov 2008 18:39:27 -0800, Paul Rubin wrote:
>Terry Reedy <tj*****@udel.eduwrites:
>>>>Do your tuple destructuring in the first statement in your body and
nothing will break.
Why get rid of a useful feature that unclutters code?

Unfortunately, the people who find it useful are a minority. Most people
don't care for it, and the Python dev team decided that the code they
most wanted to unclutter was their own CPython implementation.

Personally, I'm with you on this one: it's a small step backwards. But
only a *small* step. Whether it is outweighed by the steps forward, well,
time will tell.
I must admit I grumbled a bit when I saw it happening, but
held back both because you've got to take the rough with
the smooth when taking advantage of other people's work
on your behalf; and because the developer in question
(Brett C, if memory serves) indicated that to keep it in
would make other needed changes difficult to manage.

So it wasn't just gratuitous breakage. It's tempting to
say that some sort of survey could have been taken to
see who might be affected, but frankly the debates on
these things on python-dev alone can run forever; imagine
what it would be like on python-list. (Or cast your mind
back, if you will, to the three-part-conditional debate :) )

TJG
Nov 21 '08 #17

This discussion thread is closed

Replies have been disabled for this discussion.