|
|
To quickly find the index of the first maximum item of a sequence.
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.
|
Download
Copy to clipboard
