min() with custom compare.

[Bram Stolk]

Hi there,


If you have a list of elements, you can sort it with an alternative
comparator (default is __lt__())

This is done as:

l=[5,-4,1,9,-9]
l.sort()
l [-9, -4, 1, 5, 9]
l.sort(lambda x,y: abs(x)-abs(y))
l

[1, -4, 5, -9, 9]

Lovely stuff, is it not?

Now my question:
What if I need only a max, or min value, and not a complete sort,
but I do want to have a custom compare func.
What could I do?

min() and max() built-ins cannot take a compare func.

Thanks,

Bram

--
------------------------------------------------------------------------------
Bram Stolk, VR Engineer.
SARA Academic Computing Services Amsterdam, PO Box 94613, 1090 GP AMSTERDAM
email: (e-mail address removed) Phone +31-20-5923059 Fax +31-20-6683167

"For the costs of subsidized agriculture in the EU, we can have all 56 million
European cows fly around the world. First Class." - J. Norberg
------------------------------------------------------------------------------

 

[Heather Coppersmith]

On Wed, 7 Apr 2004 11:44:07 +0200,

[ example of sort with custom compare function snipped ]

What if I need only a max, or min value, and not a complete
sort, but I do want to have a custom compare func. What could I
do?

min() and max() built-ins cannot take a compare func.

Use reduce:

def absolulte_minimum_function( x, y ):
x, y = abs( x ), abs( y )
if x < y:
return x
else:
return y

minimum = reduce( absolute_minimum_function, l )

There's probably some (awfully horrible) lambda-embeddable
equivalent to absolute_minimum_function, but I'm not about to try
to figure it out right now, and even if I did, I'd probably end up
not using it anyway.

HTH,
Heather

 

[Felix Wiemann]

Use reduce:

def absolulte_minimum_function( x, y ):
x, y = abs( x ), abs( y )
if x < y:
return x
else:
return y

minimum = reduce( absolute_minimum_function, l )

That doesn't work if the "minimum" element is negative, e.g.

l = [5, -4, -1, 9, -9].
# ^^


def absolute_minimum_function(x, y):
if abs(x) < abs(y):
return x
else:
return y
minimum = reduce(absolute_minimum_function, l)

 

[Jeff Epler]

Use DSU, as for sorts. Turn each element i of the sequence into a tuple
(f(i), i), and find the min of that sequence. Return element 1 of that
tuple, which is the original set element.


def min_f(seq, f):
decorated = [(f(i), i) for i in seq]
return min(decorated)[1]

def max_f(seq, f):
decorated = [(f(i), i) for i in seq]
return min(decorated)[1]

l=[5,-4,1,9,-9]
min(l) -9
min_f(l, abs)

1

You can make 'decorated' be a generator and avoid the need to hold the
whole list in memory:

def decorated2(seq, f):
for i in seq:
yield f(i), i

def min_f2(seq, f):
return min(decorated(seq, f))[1]

def max_f2(seq, f):
return max(decorated(seq, f))[1]

If you want to break ties not by comparing the original items but by
comparing indices, you could do this:
def decorated3(seq, f):
for i, v in enumerate(seq):
yield (f(v), i, v)

def min_f3(seq, f):
return min(decorated3(seq, f))[2]

Jeff

 

[Dan Bishop]

On Wed, 7 Apr 2004 11:44:07 +0200,

[ example of sort with custom compare function snipped ]

What if I need only a max, or min value, and not a complete
sort, but I do want to have a custom compare func. What could I
do?

....

def absolulte_minimum_function( x, y ):
x, y = abs( x ), abs( y )
if x < y:
return x
else:
return y

minimum = reduce( absolute_minimum_function, l )

There's probably some (awfully horrible) lambda-embeddable
equivalent to absolute_minimum_function, but I'm not about to try
to figure it out right now, and even if I did, I'd probably end up
not using it anyway.

minimum = reduce(lambda x, y: min(abs(x), abs(y)), l)

 

[Felix Wiemann]

minimum = reduce(lambda x, y: min(abs(x), abs(y)), l)

This doesn't work for 'l = [5, -4, -1, 9, -9]', as I pointed out in
<[email protected]>.