To quickly find the index of the first maximum item of a sequence.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | def _posmax_psy(seq, key=None):
"""posmax(seq, key=None): return the position of the first maximum
item of a sequence. Accepts the usual key parameter too.
>>> posmax([])
Traceback (most recent call last):
...
ValueError: maxpos() arg is an empty sequence
>>> posmax([1])
0
>>> posmax(xrange(100))
99
>>> posmax(xrange(100, 0, -1))
0
>>> posmax([1,5,0,4,3])
1
>>> posmax([1,5,0,4,5,3])
1
>>> l = ['medium', 'longest', 'short']
>>> posmax(l)
2
>>> posmax(l, key=len)
1
>>> posmax(xrange(10**4))
9999
>>> posmax([2,4,-2,[4],21]) # silly comparison
3
>>> posmax([2,4,-2+3J,[4],21])
Traceback (most recent call last):
...
TypeError: no ordering relation is defined for complex numbers
"""
first = True
max_pos = 0
pos = 0
if key is None:
for el in seq:
if first:
max_el = el
first = False
elif el > max_el:
max_el = el
max_pos = pos
pos += 1
else:
for el in seq:
key_el = key(el)
if first:
max_key_el = key_el
first = False
elif key_el > max_key_el:
max_key_el = key_el
max_pos = pos
pos += 1
if first:
raise ValueError("maxpos() arg is an empty sequence")
else:
return max_pos
def _posmax_nopsy(seq, key=None):
"""posmax(seq, key=None): return the position of the first maximum
item of a sequence. Accepts the usual key parameter too.
>>> posmax([])
Traceback (most recent call last):
...
ValueError: maxpos() arg is an empty sequence
>>> posmax([1])
0
>>> posmax(xrange(100))
99
>>> posmax(xrange(100, 0, -1))
0
>>> posmax([1,5,0,4,3])
1
>>> posmax([1,5,0,4,5,3])
1
>>> l = ['medium', 'longest', 'short']
>>> posmax(l)
2
>>> posmax(l, key=len)
1
>>> posmax(xrange(10**4))
9999
>>> posmax([2,4,-2,[4],21]) # silly comparison
3
>>> posmax([2,4,-2+3J,[4],21])
Traceback (most recent call last):
...
TypeError: no ordering relation is defined for complex numbers
"""
first = True
max_pos = 0
if key is None:
for pos, el in enumerate(seq):
if first:
max_el = el
first = False
elif el > max_el:
max_el = el
max_pos = pos
else:
for pos, el in enumerate(seq):
key_el = key(el)
if first:
max_key_el = key_el
first = False
elif key_el > max_key_el:
max_key_el = key_el
max_pos = pos
if first:
raise ValueError("maxpos() arg is an empty sequence")
else:
return max_pos
def _posmax_benchmark1():
from time import clock
alist = [3]*1000 + [5] + [3]*1000
t = clock()
for _ in xrange(60000):
r = posmax(alist)
print round(clock() - t, 2), r
try:
import psyco
psyco.full()
posmax = _posmax_psy
except ImportError:
posmax = _posmax_nopsy
if __name__ == "__main__":
import doctest
doctest.testmod()
print "Doctests finished.\n"
_posmax_benchmark1()
|
Timings (2_001 items, 60_000 loops): C: 1.27 ( 1 X) D: 1.52 ( 1.2 X) Psyco: 4.3 ( 3.38 X) ( 1 X) Python 167.7 (132 X) (39 X)
Notes: - Compiled with MinGW 3.4.2 (-O3 -s), DMD 1.026 (-O -release -inline), Psyco 1.5.2, Python 2.5.1.1, on a PIII. - The C version uses a malloc. And it works on an array of ints only. - The D version works with any kind of array, dynamical vectors and any kind of iterable object, just like the Python version. The D version is slower than the C one just because the DMD compiler isn't much optimized yet. - With a tiny adaptation of the code (for el in seq: instead of for pos, el in enumerate(seq):) the Psyco version is almost 40 times faster than the Python version, and just 2.8 times slower than the D version. - A Python/Psyco posmin function can be written easily from this ones. - The Python/Psyco versions I have shown here are probably close to the faster ones. They work with empty arrays, any iterable objects, etc. - The Python version compiled with Psyco is just about 10-20% slower than the Psyco version compiled with Psyco. - A version on array.array("l") is about twice slower than this one. - Probably a Cython/Pyrex version isn't much faster than this Psyco one.
