Steven D'Aprano
1/26/2008 10:08:00 PM
On Sat, 26 Jan 2008 12:40:26 -0800, Paul Rubin wrote:
> bearophileHUGS@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