Using list comprehension to store the maximum seen value

Question

Is it possible to do the below with list comprehension? Trying to store the maximum value that has been seen at any given point through the loop.

def test(input):
    a = input[0]
    b = []
    for i in input:
        a = max(i,a)
        b.append(a)
    return b

print test([-5,6,19,4,5,20,1,30])

# returns [-5, 6, 19, 19, 19, 20, 20, 30]

@sergzach: mind that `i` is the index. Here the **thus far** max is wanted. — Willem Van Onsem, Apr 01 '17 at 22:40
You can't do it with a "plain" list comprehension, because the list comprehension itself won't maintain state (like the highest seen so far). You can only do it if your list comprehension applies a function that maintains state (like `itertools.accumulate`), or if you run your function on chunks of the list instead of individual elements (as in Willem Van Onsem's O(n^2) example. — BrenBarn, Apr 01 '17 at 22:42
The duplicate is not exactly a duplicate. It is correct that both questions have the same structure, but they address different operations. — DYZ, Apr 01 '17 at 23:23
@DYZ - Yes, it is a duplicate. All you have to change is choosing an appropriate function, which the OP of this question has already done. — TigerhawkT3, Apr 01 '17 at 23:41
@TigerhawkT3 I doubt if people looking for a solution to this same problem will find solace in that dupe target. — Moses Koledoye, Apr 01 '17 at 23:45
@MosesKoledoye - They will, unless they're (mis)using this site as a free coding service. — TigerhawkT3, Apr 01 '17 at 23:47
@MosesKoledoye - Do you honestly think that replacing `operator.add` with `max` makes this a unique question? Removing the convenient duplicate link just forces future visitors to take a little longer to find the information they're looking for. — TigerhawkT3, Apr 02 '17 at 00:05
Related, possible duplicate: [List comprehension with an accumulator](http://stackoverflow.com/q/20222485) Note: The accepted answer on that question as been updated with an explanation since when this question was previously marked as a duplicate. With the explanation, particularly of how passing a function to `itertools.accumulate` works, it's much easier to tell that this question is a duplicate, just with a different accumulator function. — Makyen, Apr 02 '17 at 15:37
Possible duplicate of [List comprehension with an accumulator](http://stackoverflow.com/questions/20222485/list-comprehension-with-an-accumulator) — Makyen, Apr 02 '17 at 15:38

score 7 · Answer 1 · edited Apr 01 '17 at 22:44

7

You can use itertools.accumulate with the max builtin in Python 3:

from itertools import accumulate

lst = [-5,6,19,4,5,20,1,30]
r = list(accumulate(lst, max)) #[i for i in accumulate(lst, max)]
print(r)
# [-5, 6, 19, 19, 19, 20, 20, 30]

edited Apr 01 '17 at 22:44

TigerhawkT3

48,464
6
60
97

answered Apr 01 '17 at 22:40

Moses Koledoye

77,341
8
133
139

With `list(accumulate(...))` you can avoid the explicit list comprehension. – DYZ Apr 01 '17 at 22:41
@DYZ Brainfart. Got carried away by the OP. Thanks – Moses Koledoye Apr 01 '17 at 22:42

score 5 · Accepted Answer · edited May 23 '17 at 12:02

What you present here is a typical form of what is known in functional programming as scan.

A way to do this with list comprehension that is inefficient is:

[max(input[:i]) for i in range(1,n+1)]

But this will run in O(n²).

You can do this with list comprehension given you use a function with side effects: like the following:

def update_and_store(f,initial=None):
    cache = [initial]
    def g(x):
       cache[0] = f(cache[0],x)
       return cache[0]
    return g

You can then use:

h = update_and_store(max,a[0])
[h(x) for x in a]

Or you can use a dictonaries setdefault() like:

def update_and_store(f):
    c = {}
    def g(x):
        return c.setdefault(0,f(c.pop(0,x),x))
    return g

and call it with:

h = update_and_store(max)
[h(x) for x in a]

like @AChampion says.

But functions with side-effects are rather unpythonic and not declarative.

But you better use a scanl or accumulate approach like the one offered by itertools:

from itertools import accumulate

accumulate(input,max)

Just as a trick. You can implement the `update_and_store()` with a `dict`: `c = {}; [c.setdefault(0, max(c.pop(0, n), n)) for n in d]` — AChampion, Apr 01 '17 at 23:03
@AChampion: yeah. That is indeed a smart way to do this. Nevertheless regardless on how one implements functions with side-effects, they are almost inherently dangerous to use in list-comprehension, generators, etc. So I would not recommend using them anyway. — Willem Van Onsem, Apr 01 '17 at 23:08

DYZ · Answer 3 · 2017-04-01T22:52:10.720

3

If using NumPy is permitted, then you can use NumPy:

import numpy as np
np.maximum.accumulate([-5,6,19,4,5,20,1,30])
# array([-5,  6, 19, 19, 19, 20, 20, 30])

edited Apr 01 '17 at 22:52

answered Apr 01 '17 at 22:40

DYZ

55,249
10
64
93

Using list comprehension to store the maximum seen value

3 Answers3