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

To quickly find the index of the first maximum item of a sequence.

Python, 145 lines
 ``` 1 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.

 Created by bearophile - on Sun, 27 Jan 2008 (PSF)