Comparison of functions

S

Steven D'Aprano

Steven D'Aprano ha scritto:


Because, of course, when I sort numbers the first thing I think of is
looking at the ascii table... Here I was, thinking maths was useful.
Sorting numbers "lexicographically" might make sense to you, but it's
totally unintuitive to me. For example, why or how would I guess that
"3-3j" is bigger (or smaller) than "3+3j"?

3-3j is NOT bigger than 3+3j, nor is it smaller. You said so yourself:
"it's not possible to define an order that preserves the properties of
arithmetical operations on complex numbers."

Fortunately, when we sort a list, we don't care about preserving the
properties of arithmetical operations, we just need to place each item in
a known, non-arbitrary (or at least not too arbitrary) position.
You'll still want to sort complex numbers lexicographically. It'll still
have no meaning whatsoever, so you might as well leave the list
unsorted.

Your mathematical purity does you great credit. Unfortunately,
it is also quite impractical. I'll give you a real-world actual case where
sorting complex numbers is important: "The Penguin Dictionary Of
Curious and Interesting Numbers" by David Wells. Some few hundreds of
numbers are listed, including i. Should Wells have listed those numbers in
random unsorted order just to satisfy some purists who insist that placing
i in the list makes sorting the other 399 entries meaningless?

You might think you sorted something. 100? 200? years of maths
say you didn't.

Sorting is not just numeric ordering. There are many different collation
systems, not just ordering numbers by their magnitude.

Think about sorting guests around a dinner table: married couples next to
each other, single people across from another single person of the
opposite sex, children at the end of the table, babies next to their
mother, Uncle Enno as far away from Aunt May as possible. It is a
complicated algorithm, but it is still sorting (people, in this case, not
numbers).

I appreciate your strong feelings about not doing comparisons on complex
numbers, but if you actually studied the mathematics of orderings sets,
you would realise how silly it was to say that a century of mathematics
says that I didn't sort a list. Mathematicians are fully aware that
numeric sorting is just one way of many of sorting.

Do you understand the difference between partial and total ordering, or
weakly and strongly ordered? When you do understand them, come back and
tell me again whether you still think lexicographic sorting has no meaning
whatsoever.
 
S

Steven D'Aprano

If you want to treat numbers as strings, why not convert them before
sorting them?

Because that changes the object and throws away information.

Here is a list, containing one complex number converted to a string, and
one string that just happens to look like a complex number:

['1+1j', '2+2j'].

Now convert it back the way it was.

Python is just saying "He's trying to sort complex
numbers. No can do".

Python is quite happy to sort a list with one single complex number and
nothing else, so it is not SORTING complex numbers that Python objects
to, merely greater or less than comparisons. It is an accident of
implementation that Python blindly uses GT or LT comparisons for sorting
complex numbers, but not other objects.

You're trying to make it guess that you want them
sorted as strings, not as numbers. I don't see how Python treats things
the same way. I see that real numbers and strings can be compared and
sorted (asciibetically? don't remember). It has nothing to do with
complex numbers. The abstraction or overloading or what it is fails,
because they don't have an order as numbers, and Py is not intelligent
enough to know that you want them asciibetized

Which has been my point all along: Python confuses the specific case of
NUMERIC COMPARISONS with the general case of SORTING. Worse, Python
doesn't even do that consistently: it is quite happy to let you compare
floats with strings, even though mathematically that is just as
much nonsense as to compare floats with complex numbers.

As I've said, the two are similar enough that such a mistake is easy to
make. And at this time, I'm not sure how to implement a better solution,
or even if there is a better solution, but I am giving it some thought.
 
D

Dennis Lee Bieber

I am aware of that. That's a wart.

I suppose we could modify Python to throw an exception: "the
objects have no defined order and can not be compared".

As for ordering complex numbers? Would you want them ordered on
angle first, then length, or length first then angle (converting the
x+yj to equivalent polar coordinates -- Ah, but then we have the
problem: do we sweep for 0 to 360 degrees [or use radians], or 0 to +/-
180 degrees)

--
 
S

Steven D'Aprano

Steven D'Aprano ha scritto:


I think I answered this in another post... If you want to order text
strings (as complex numbers in an index in a book, or in a lexicographic
sort are) do so. I understand the importance it has to you, but it's
hardly reasonable to argue that Python should do the most unintuitive
thing with complex numbers by default just because it suits you.

Adriano, list.sort() is not an operation on complex numbers. It is an
operation on a list. What is unintuitive is that you can't sort a list
merely because of the arithmetical properties of an object in that list.
Why should that make a difference? We're not doing arithmetic on the
objects, we're sorting the list.

It isn't even about *complex numbers* as such -- that was just a
convenient example. There are no end to the possible objects which don't
define greater than and less than. But you should still be able to sort a
list containing them. Sorting is not numeric comparisons!

Python already allows you to compare "this is not a number" with the float
5.0. Mathematically, that is meaningless, but I would bet money that
99.9% of programmers would demand that they should be able to sort the
list ["this is not a number", 5.0]. Do you think that it is unintuitive
too?

This conversation has been an exercise in futility. I'm sorry that so many
of the people answering find it difficult to see the difference between
numeric comparisons of complex numbers (which are rightly forbidden) and
sorting of lists of arbitrary objects (which should always succeed): in
effect, confusing the current implementation of sort() in Python with the
general principle of sorting.

Unless anyone comes up with constructive comments (which does not
necessarily mean "agrees with me"), I plan to drop this thread until such
time, if ever, that I have something more concrete to suggest.
 
E

Erik Max Francis

Steven said:
Um, I didn't ask to compare complex numbers using comparison operators. I
asked to sort a list. And please don't tell me that that sorting is
implemented with comparison operators. That just means that the
implementation is confusing numeric ordering with sort order.

Python doesn't have a distinction between these two, so yes, you're
sorting with comparison operators.
 
P

Peter Hansen

Steven said:
Python already allows you to compare "this is not a number" with the float
5.0. Mathematically, that is meaningless, but I would bet money that
99.9% of programmers would demand that they should be able to sort the
list ["this is not a number", 5.0]. Do you think that it is unintuitive
too?

I strongly suspect that 99.8% of (let's say non-newbie) programmers
would have no expectation that the default sort routine would do
something other than barf on that input. You want "garbage in, garbage
out", but in Python it's supposed to be "garbage in, exception out,
please be explicit about what you want next time".

I can't think of any use case for sorting a list like that which
wouldn't most appropriately be handled with a custom comparison routine
passed to sort.

-Peter
 
B

Bengt Richter

Seems to me the object addresses are compared in this case. But I'm too
lazy to check it in the source. ;)

Strangely enough, I'm lazy enough to not check the source too :)

Actually, more to the point, I don't read C, so even if I did check the
source, I wouldn't know what it was trying to tell me.
However, the doc [1] warns you about such comparisons: """Most other
types compare unequal unless they are the same object; the choice
whether one object is considered smaller or larger than another one is
made arbitrarily but consistently within one execution of a program."""

I am aware of that. That's a wart.
What if rich sorting "measured" the objects it was sorting, to form a measurement tuple
of primitive types, so that you'd wind up sorting as if by a decorated list with the
measurement tuple as the decoration, e.g., (an I think having to wrap complex for sorting
is CWrap ;-)

Just a sketch to illustrate an idea for sorting...

----< richlysorted.py >-------------------------------------
def richlysorted(seq):
return ((type(v) is CWrap and [v.v] or [v])[0]
for d,v in sorted(measure_dec(seq)))

INT = LONG = FLOAT = 0
COMPLEX = 1
STR = 2
UNICODE = 3
FUNCTION = 4
TYPE = 5
DEFAULT = 6

type_sort_order = dict(
int=INT, long=LONG, float=FLOAT,
complex=COMPLEX,
str=STR, unicode=UNICODE,
function=FUNCTION,
type=TYPE)

class CWrap(object):
def __init__(self, v): self.v=v
def __eq__(self, other): return True

def measure_dec(seq):
for v in seq:
sort_priority = type_sort_order.get(type(v).__name__, DEFAULT)
if sort_priority == COMPLEX:
yield (sort_priority, v.real, v.imag), CWrap(v)
elif sort_priority <= UNICODE:
yield (sort_priority,), v
elif sort_priority == FUNCTION:
yield (sort_priority, v.func_name, v.func_code.co_argcount), v
elif sort_priority == TYPE:
yield (sort_priority, v.__name__), v
else:
yield (sort_priority, type(v).__name__, repr(v)) , v

def test():
class C: pass
class D(object): pass
def foo(): pass
def bar(a,b): pass
tbs = [1, -1.0, 1+0j, 2j, lambda x:x, test, measure_dec, lambda:None,
foo, bar, D, D(), C(), C, 2**32, -2**32]

for tup in zip(tbs, measure_dec(tbs)):
print '%35s | %-s' % tup
print '%s\nSorted:'% (50*'-')
for item in richlysorted(tbs):
print '%35s' % item

if __name__ == '__main__':
test()
------------------------------------------------------------

[16:57] C:\pywk\ut>py24 richlysorted.py
1 | ((0,), 1)
-1.0 | ((0,), -1.0)
(1+0j) | ((1, 1.0, 0.0), <__main__.CWrap object at 0x02F00B2C>)
2j | ((1, 0.0, 2.0), <__main__.CWrap object at 0x02F00B4C>)
<function <lambda> at 0x02EE8DF4> | ((4, '<lambda>', 1), <function <lambda> at 0x02EE8DF4>)
<function test at 0x02EE8D4C> | ((4, 'test', 0), <function test at 0x02EE8D4C>)
<function measure_dec at 0x02EE8CA4> | ((4, 'measure_dec', 1), <function measure_dec at 0x02EE8C
A4>)
<function <lambda> at 0x02EE8E2C> | ((4, '<lambda>', 0), <function <lambda> at 0x02EE8E2C>)
<function foo at 0x02EE8D84> | ((4, 'foo', 0), <function foo at 0x02EE8D84>)
<function bar at 0x02EE8DBC> | ((4, 'bar', 2), <function bar at 0x02EE8DBC>)
<class '__main__.D'> | ((5, 'D'), <class '__main__.D'>)
<__main__.D object at 0x02F0044C> | ((6, 'D', '<__main__.D object at 0x02F0044C>'), <__main__.
D object at 0x02F0044C>)
<__main__.C instance at 0x02F004CC> | ((6, 'instance', '<__main__.C instance at 0x02F004CC>'), <
__main__.C instance at 0x02F004CC>)
__main__.C | ((6, 'classobj', '<class __main__.C at 0x02EE78CC>'), <cla
ss __main__.C at 0x02EE78CC>)
4294967296 | ((0,), 4294967296L)
-4294967296 | ((0,), -4294967296L)
--------------------------------------------------
Sorted:
-4294967296
-1.0
1
4294967296
2j
(1+0j)
<function <lambda> at 0x02EE8E2C>
<function <lambda> at 0x02EE8DF4>
<function bar at 0x02EE8DBC>
<function foo at 0x02EE8D84>
<function measure_dec at 0x02EE8CA4>
<function test at 0x02EE8D4C>
<class '__main__.D'>
<__main__.D object at 0x02F0044C>
__main__.C
<__main__.C instance at 0x02F004CC>

Regards,
Bengt Richter
 
R

Rocco Moretti

Adriano said:
As far as I recall from Math Analysis, which I studied two months ago,
you can't sort complex numbers. It makes no sense. The reason being
(reading from my book), it's not possible to define an order that
preserves the properties of arithmetical operations on complex numbers.
So you can't order them, and you can't compare them.

Debate the merits of Python's method of sorting all you want, but for
the love of all that is good and holy, please do not claim that the
current way of doing things is somehow mathematically pure. The best
explanation of the current method is that it is a compromise borne out
of the best use cases encountered as the language grew in it's infancy,
and we're stuck with it currently because it would break too much to
change things right now.

E.g.:
1 < '2' => True
'1' < 2 => False
20 < 'Five' => True
None < 0 => True
[1,2] < (1,2) => True
(1,2) < [100,200] => False
(None,) < None => False
{1:None,2:None} < [1,2] => True

[None, 1, 'five', open('README'), (1,2,3)].sort() => works just fine
[None, 1, 'five', open('README'), (1,2,3), 1j].sort() => crashes and burns

None of these make sense mathematically, nor were they motivated
primarily by mathematical arguments. Why is [1,2] < (1,2)? Because
'list' < 'tuple' - No more, no less.

One could argue that you could think of complex numbers as tuples of
values - but then why does
[(1,2),(4,1),(4,-3),(7.2,-1.2)].sort() work and
[(1+2j),(4+1j),(4-3j),(7.2-1.2j)].sort() fail?

"Practicality beats purity." Python has it's current ordering/sorting
scheme not because it is theoretically pure, but because it seemed like
the best option at the time. Please don't pretend it's perfect - it's
even been admitted that things are going to change in the future,
although I haven't yet seen a conversation where it has been made clear
exactly what will change.
 
D

Dan Bishop

Steven said:
Because that changes the object and throws away information.

I think he meant doing something like

->>> lst = ['2+2j', 1+1j]
->>> lst.sort(key=str)
->>> lst
[(1+1j), '2+2j']
Python is quite happy to sort a list with one single complex number and
nothing else, so it is not SORTING complex numbers that Python objects
to, merely greater or less than comparisons. It is an accident of
implementation that Python blindly uses GT or LT comparisons for sorting
complex numbers, but not other objects.

Python uses GT/LT comparisons for sorting *everything*. The wart is
not in list.sort, but in the inconsistent implementation of the
comparison operators.
...
Which has been my point all along: Python confuses the specific case of
NUMERIC COMPARISONS with the general case of SORTING. Worse, Python
doesn't even do that consistently: it is quite happy to let you compare
floats with strings, even though mathematically that is just as
much nonsense as to compare floats with complex numbers.

As I've said, the two are similar enough that such a mistake is easy to
make. And at this time, I'm not sure how to implement a better solution,
or even if there is a better solution, but I am giving it some thought.

How's this?


# This would be the default cmp function for list.sort
def sortcmp(x, y):
try:
return x.__sortcmp__(y)
except (AttributeError, TypeError):
try:
return -(y.__sortcmp__(x))
except (AttributeError, TypeError):
return cmp(x, y)

# Example class for __sortcmp__ method
class SaneComplex(complex):
def __sortcmp__(self, other):
other = complex(other)
return cmp((self.real, self.imag), (other.real, other.imag))

lst = map(SaneComplex, [1, 1+0j, 1+7j, 2, 2+3j, 3+3j, 3-3j, 3+4j, 4,
4+2j])
lst.sort(sortcmp)
print lst
 
S

Steven Bethard

Steven said:
You are confusing mathematical ordering with sorting a list. Here, I will
sort some mixed complex and real numbers for you. If you look at them
closely, you will even be able to work out the algorithm I used to sort
them.

1
1+0j
1+7j
2
2+3j
3+3j
3-3j
3+4j
4
4+2j

It's clear which algorithm you used to sort these:

py> lst = [3+3j, 3+4j, 1+7j, 2, 3-3j, 4, 4+2j, 1, 1+0j, 2+3j]
py> def complex2tuple(c):
.... c = complex(c)
.... return c.real, c.imag
....
py> for item in sorted(lst, key=complex2tuple):
.... print item
....
1
(1+0j)
(1+7j)
2
(2+3j)
(3-3j)
(3+3j)
(3+4j)
4
(4+2j)

What isn't clear is that this should be the default algorithm for
sorting complex numbers.

STeVe
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,481
Members
44,900
Latest member
Nell636132

Latest Threads

Top