Index of maximum element in list

[Steven D'Aprano]

On Sat, 26 Jan 2008 12:40:26 -0800, Paul Rubin wrote:

> bearophileHUGS at lycos.com writes:
>> > def posmax(seq, key=lambda x:x):
>> >    return max(enumerate(seq), key=lambda k: key(k[1]))[0]
>> 
>> Is the Python max able to tell that's the identity function? I don't
>> think so, so your version may be slower and more memory hungry in the
>> common situation where you don't have a key function. So I think my
>> version is better :-)
> 
> I don't think there will be a noticable memory increase.  It's not a DSU
> situation like in sorting, it's just a small constant parameter. Yes
> there might be a small speed hit.  The compiler in principle could
> convert the (lambda k: lambda x: k[1]) to something like
> operator.itemgetter(1), but I doubt that it actually does so.

Actually there is a big speed hit. Until such time that Python has a fast 
identity function, and lambda x:x isn't it, your version is about three 
times slower than Bearophile's.

Much to my surprise, the fastest solution I've tried appears to be a pure 
Python version not even using max() at all.

Here are the three versions:

def posmax1(seq, key=None):  # bearophile's version
    """Return the position of the first maximum item of a sequence.
    It accepts the usual key parameter too."""
    if key:
        return max(enumerate(seq), key=lambda k: key(k[1]))[0]
    else:
        return max(enumerate(seq), key=itemgetter(1))[0]


def posmax2(seq, key=lambda x:x):  # Paul Rubin's version
    return max(enumerate(seq), key=lambda k: key(k[1]))[0]


def posmax3(seq, key=None):  # Pure Python version
    if key is None:
        m = seq[0]
        index = 0
        for i, x in enumerate(seq):
            if x > m:
                m = x
                index = i
        return index
    else:
        return NotImplemented



And my timing results:

>>> alist = [3]*1000 + [5] + [3]*1000
>>> assert alist.index(5) == 1000
>>> assert posmax1(alist) == posmax2(alist) == posmax3(alist) == 1000
>>>
>>> min(timeit.Timer('posmax1(alist)',
...     'from __main__ import posmax1, alist').repeat(number=1000))/1000
0.00074387979507446289
>>> min(timeit.Timer('posmax2(alist)',
...     'from __main__ import posmax2, alist').repeat(number=1000))/1000
0.0022983889579772949
>>> min(timeit.Timer('posmax3(alist)',
...     'from __main__ import posmax3, alist').repeat(number=1000))/1000
0.00063846302032470701



-- 
Steven