Welcome, guest | Sign In | My Account | Store | Cart

argmin (Python recipe) by Peter Norvig
ActiveState Code (http://code.activestate.com/recipes/389640/)

Implement the argmin function from math, in a form that makes use of generator expressions in 2.4.

Python, 9 lines
Download
1
2
3
4
5
6
7
8
9
def argmin(sequence, fn=None):
    """Two usage patterns:
    argmin([s0, s1, ...], fn)
    argmin([(fn(s0), s0), (fn(s1, s1), ...]) 
    Both return the si with lowest fn(si)"""
    if fn is None:
        return min(sequence)[1]
    else:
        return min((fn(e), e) for e in sequence)[1]

Often you want to find the element of a set that is "best" in some way. In math, this is usually notated with argmin (or argmax):

best = argmine in S f(e)

where f is a function that gives a score, and low score is best. Python syntax doesn't allow subscripts like this, but we can come up with two protocols that are not too ugly. Examples:

If we have sequence = ['one', 'to', 'three'], then

argmin(sequence, len) ==> 'to' ## because 'to' has smallest len.

argmin((len(x), x) for x in sequence) ==> 'to' ## alternate protocol

Note that with generator expressions this is efficient (doesn't build up a large intermediate list) and not too hard to read.

Tags: shortcuts

2 comments

Steven Bethard 19 years, 1 month ago  # | flag

essentially min with a key argument. argmin is essentially min with a key argument like what list.sort and sorted have. Note that min and max now take such 'key' arguments in the current Python cvs:

Python 2.5a0 (#60, Nov 30 2004, 15:53:08) [MSC v.1310 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
you need the ctypes module to run this code
http://starship.python.net/crew/theller/ctypes/
>>> sequence = ['one', 'to', 'three']
>>> min(sequence, key=len)
'to'

Of course, most people can't use the current CVS version of Python, so here's a substitute:

py> class _minmax(object):
...     def __init__(self, func):
...         self.func = func
...     def __call__(*args, **kwargs):
...         self = args[0]
...         key = kwargs.pop('key', None)
...         if kwargs:
...             raise TypeError("only 'key' accepted as a "
...                             "keyword argument")
...         if key is None:
...             return self.func(*args[1:])
...         else:
...             if len(args) == 2:
...                 seq = args[1]
...             else:
...                 seq = args[1:]
...             return self.func((key(item), i, item)
...                              for i, item in enumerate(seq))[-1]
...
py> min = _minmax(min)
py> max = _minmax(max)

Now you should be able to use key arguments to min and max just like in CVS:

py> min('ab', 'c')
'ab'
py> min('ab', 'c', key=len)
'c'
py> d = dict(a=2, b=1)
py> max(d)
'b'
py> max(d, key=d.__getitem__)
'a'
Andras Csibi 14 years, 12 months ago  # | flag

As far as I understand, in math, arg functions return the _argument_ of our actual functions, which means that the point(s) at which the values of our function is minimal/maximal.

So for example if our function is:

f(x) = x**2 + 3

then the minimum value of the function is 3, and the point where our function takes its minimum value is x=0. 

min(f(x)) = 3
argmin(f(x)) = 0

In Python, this translates to returning the index of the minimum element in the sequence, not the actual minimum element. In this sense, argmin means something like this:

min((fn(x), i) for i,x in enumerate(sequence))[1]
Created by Peter Norvig on Fri, 25 Feb 2005 (PSF)
◄ Python recipes (4591) ►
◄ Peter Norvig's recipes (3) ►

Required Modules

  • (none specified)

Other Information and Tasks