sorting list of complex numbers

[skip]

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.326722518499 59244+0.4142898 3433288791j), (0.352380564846 09881+0.9275820 3977208264j), (0.193378240381 25528+0.1652728 5180541951j), (0.475693071145 25849+0.7238196 0418815128j), (0.214988131350 82351+0.2046308 266222292j), (0.301427457569 37939+0.3521675 1451102601j), (0.773556763869 39132+0.0023447 924287695043j), (0.254773612460 6309+0.52234837 788936905j), (0.383491890813 50132+0.6201761 7694427096j), (0.583620967735 61245+0.8770244 3273108477j)]

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.193378240381 25528+0.1652728 5180541951j), (0.214988131350 82351+0.2046308 266222292j), (0.254773612460 6309+0.52234837 788936905j), (0.301427457569 37939+0.3521675 1451102601j), (0.326722518499 59244+0.4142898 3433288791j), (0.352380564846 09881+0.9275820 3977208264j), (0.383491890813 50132+0.6201761 7694427096j), (0.475693071145 25849+0.7238196 0418815128j), (0.583620967735 61245+0.8770244 3273108477j), (0.773556763869 39132+0.0023447 924287695043j)]

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.8600000000 000003j),
(4+3.1200000000 000001j),
(2+22j),
(9+29j),
(3+2.9900000000 000002j),
(6+26j),
2.6000000000000 001j,
(8+3.6400000000 000001j),
(3+23j),
(5+3.25j),
(1+21j),
(5+25j),
20j,
(6+3.3799999999 999999j),
(7+3.5100000000 000002j),
(4+24j)]

I can sort by the real parts just fine:

>>lst.sort(key= lambda x: x.real)
pprint.pprint (lst)

[2.6000000000000 001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000 000003j),
(2+22j),
(3+2.9900000000 000002j),
(3+23j),
(4+3.1200000000 000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999 999999j),
(7+27j),
(7+3.5100000000 000002j),
(8+28j),
(8+3.6400000000 000001j),
(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

[Duncan Booth]

sk**@pobox.com wrote:

I can sort by the real parts just fine:

>>lst.sort(key= lambda x: x.real)
>>pprint.pprint (lst)

[2.6000000000000 001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000 000003j),
(2+22j),
(3+2.9900000000 000002j),
(3+23j),
(4+3.1200000000 000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999 999999j),
(7+27j),
(7+3.5100000000 000002j),
(8+28j),
(8+3.6400000000 000001j),
(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.6000000000000 001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000 000003j),
(2+22j),
(3+2.9900000000 000002j),
(3+23j),
(4+3.1200000000 000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+3.3799999999 999999j),
(6+26j),
(7+3.5100000000 000002j),
(7+27j),
(8+3.6400000000 000001j),
(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.6000000000000 001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000 000003j),
(2+22j),
(3+2.9900000000 000002j),
(3+23j),
(4+3.1200000000 000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+3.3799999999 999999j),
(6+26j),
(7+3.5100000000 000002j),
(7+27j),
(8+3.6400000000 000001j),
(8+28j),
(9+3.77j),
(9+29j)]

>>>

[Diez B. Roggisch]

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.326722518499 59244+0.4142898 3433288791j), (0.352380564846 09881+0.9275820 3977208264j), (0.193378240381 25528+0.1652728 5180541951j), (0.475693071145 25849+0.7238196 0418815128j), (0.214988131350 82351+0.2046308 266222292j), (0.301427457569 37939+0.3521675 1451102601j), (0.773556763869 39132+0.0023447 924287695043j), (0.254773612460 6309+0.52234837 788936905j), (0.383491890813 50132+0.6201761 7694427096j), (0.583620967735 61245+0.8770244 3273108477j)]

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.193378240381 25528+0.1652728 5180541951j), (0.214988131350 82351+0.2046308 266222292j), (0.254773612460 6309+0.52234837 788936905j), (0.301427457569 37939+0.3521675 1451102601j), (0.326722518499 59244+0.4142898 3433288791j), (0.352380564846 09881+0.9275820 3977208264j), (0.383491890813 50132+0.6201761 7694427096j), (0.475693071145 25849+0.7238196 0418815128j), (0.583620967735 61245+0.8770244 3273108477j), (0.773556763869 39132+0.0023447 924287695043j)]

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.8600000000 000003j),
(4+3.1200000000 000001j),
(2+22j),
(9+29j),
(3+2.9900000000 000002j),
(6+26j),
2.6000000000000 001j,
(8+3.6400000000 000001j),
(3+23j),
(5+3.25j),
(1+21j),
(5+25j),
20j,
(6+3.3799999999 999999j),
(7+3.5100000000 000002j),
(4+24j)]

I can sort by the real parts just fine:

>>lst.sort(key= lambda x: x.real)
>>pprint.pprint (lst)

[2.6000000000000 001j,
20j,
(1+2.73j),
(1+21j),
(2+2.8600000000 000003j),
(2+22j),
(3+2.9900000000 000002j),
(3+23j),
(4+3.1200000000 000001j),
(4+24j),
(5+3.25j),
(5+25j),
(6+26j),
(6+3.3799999999 999999j),
(7+27j),
(7+3.5100000000 000002j),
(8+28j),
(8+3.6400000000 000001j),
(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

[skip]

>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

[Steve Holden]

Thomas Bellman wrote:

Steve Holden <st***@holdenwe b.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.at trgetter('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 [phone] [phone]
Holden Web LLC http://www.holdenweb.com/

[Paul Rubin]

Duncan Booth <du**********@i nvalid.invalidw rites:

If you don't like the tuple then just do the two sorts separately:

>lst.sort(key=l ambda x: x.imag)
lst.sort(key=l ambda 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.itemge tter 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.group by) but
if/when I downgrade to 3.0, a bunch of my code is going to break.

[Paul Rubin]

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(k ey=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.

[Gabriel Genellina]

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(k ey=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

[Arnaud Delobelle]

Paul Rubin <http://ph****@NOSPAM.i nvalidwrites:

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

[Terry Reedy]

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.itemge tter 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.group by) 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*.