ActiveState Code

Recipe 389640: argmin

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

Python 
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]

Discussion

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.

Comments

  1. 1. At 10:12 p.m. on 25 feb 2005, Steven Bethard said:

    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'
  2. 2. At 10:39 a.m. on 26 apr 2009, Andras Csibi said:

    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]

Sign in to comment