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.