maximum() efficency

[Paul McGuire]

"Steve R. Hastings" <steve at hastings.org> wrote in message
news:pan.2006.03.26.23.31.46.779886 at hastings.org...
> On Sun, 26 Mar 2006 10:34:16 -0700, Steven Bethard wrote:
> > What's the original?
>
>
>
> def minimum(cmp, lst):
>   """minimum(cmp, lst)
>
>   Returns the minimal element in non-empty list LST with elements
>   compared via CMP() which should return values with the same semantics
>   as Python's cmp().  If there are several minimal elements, the last
>   one is returned.
>   """
>
>   if not lst:
>     raise ValueError, 'empty list'
>
>   minval = lst[0]
>
>   for i in xrange(1, len(lst)):
>     v = lst[i]
>     if cmp(minval, v) > 0:
>       minval = v
>
>   return minval
>
>
>
> This is from Google's "goopy" package.
>
> http://goog-goopy.sourceforge.net/
>
> -- 
> Steve R. Hastings    "Vita est"
> steve at hastings.org    http://www.blarg.net/~steveha
>

The doc string is not correct.  If there are several minimal elements, the
*first* one is returned.  See this example:

import math

class Vector(object):
    def __init__(self,*x):
        # x is list of n-dimensional coordinates
        self.x = x

    def magnitude(self):
        return math.sqrt(sum(x**2 for x in self.x))

    def __cmp__(self,other):
        return cmp(self.magnitude(), other.magnitude())

    def __str__(self):
        return "Vector(%s)" % ",".join(str(x) for x in self.x)

a = Vector(0,1)
b = Vector(0,0)
c = Vector(1,0)

# these print 1, -1, and 0 to show that cmp() and Vector are doing the right
thing
print cmp(a,b)
print cmp(b,a)
print cmp(a,c)

print min(a,b)   # gives Vector(0,0), or b
print max(a,b,c)   # gives Vector(0,1) or a
print min(a,c)    # gives Vector(0,1) or a

print minimum(Vector.__cmp__, [a,b])   # gives Vector(0,0), or b
print minimum(Vector.__cmp__, [a,c])    # gives Vector(0,1) or a


-- Paul