[Tutor] can someone explain to me how this works [comparison
functions]
Danny Yoo
dyoo at hkn.eecs.berkeley.edu
Wed Oct 22 03:20:10 EDT 2003
On Wed, 22 Oct 2003, Kirk Bailey wrote:
> Not inverts the logical vallue of a returned logical value. Again,
> a[1]=12 and b[1]=4. with this test, and those values, the return is 0.
> Were the values reversed, this would be a 1 return, which is true, as is
> a -1 return value. IF the value HAS to be 0 or -1, we need to define the
> function with customized values. And a simple way to do it is:
>
> def compare(a,b):
> return (a[1]>b[1])-1
Hi Kirk,
True, it's simpler for the computer, but it's depending on the fact that
True and False are represented as 1 and 0. Personally, I like:
###
def compare(a,b):
if a[1] > b[1]:
return 0
else:
return -1
###
better. Even though it's more wordy, it won't surprise anyone who is
coming from a language with stricter boolean types.
But even so, I feel:
###
def compare(a,b):
if a[1] < b[1]:
return -1
elif a[1] == b[1]:
return 0
else:
return 1
###
is clearer as a comparison function. Comparison functions are meant to be
triple-valued. The original function obscured this point because it only
returned either -1 or 0, which isn't quite right. By making three
distinct cases, we can convince anyone reading this that it is
triple-valued.
(By the way, the shortest definition I can think that's equivalent to the
above example is: "def compare(a,b): return cmp(a[1], b[1])".)
It's very important to know that comparison functions must not be boolean
functions. We can even see sort() malfunction if we accidently make it
return either 0 or 1!
###
>>> def brokenCompare(a, b):
... if a > b: return 1
... return 0
...
>>> numbers = [5,4,3,2,1]
>>> numbers.sort(brokenCompare)
>>> numbers
[5, 4, 3, 2, 1]
###
It's only by a coincidence of implementation that sort() works on a
comparison function that returns either 0 or -1. Even so, we should
strive to make a comparison function return either -1, 0, or 1.
One last point: I've been fudging. *grin* Comparison functions don't have
to return -1, 0, or 1: they can return negatives, zero, or positives. If
we know this, then it's tempting to avoid writing:
###
def compare(a,b):
if a[1] < b[1]:
return -1
elif a[1] == b[1]:
return 0
else:
return 1
###
and instead say something like
###
def compare(a, b):
return a[1] - b[1]
###
to avoid all that wordy comparison logic. It's fast, it involves a single
numeric operation, so what can be the problem with it? Actually, it is
dangerous. It's not so bad in Python, since we have long ints, but in a
language that doesn't automagically use bignums, this definition is
broken: subtraction can overflow!
That's one reason why I personally remind myself that the range of a
comparison function is (-1, 0, 1), and not (negative, zero, positive) ---
it pretty much forces me to do the explicit comparisons. *grin*
Talk to you later!
More information about the Tutor
mailing list