Moving maximum function?

How can I construct a moving maximum function?

For example, if I have a list of 12 values: { 5, 6, 9, 3, 2, 6, 7, 8, 1, 1, 4, 7 } and I want to maximize over 3 values then the expected result would be: { 6, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7 }.

-
I'm not clear how you got 6 as the first value of your expected result. Shouldn't it be the maximum of {5, 6, 9} which is 9? – Codie CodeMonkey Jan 16 '14 at 6:26
I was centering the range on the value, but you could just as well right or left shift it. In other words, in my example, the first value is the maximum of { null, 5, 6 } – Tyler Durden Jan 16 '14 at 6:28
@TylerDurden, why not {Null, Null, 6}? – alancalvitti Sep 28 '14 at 19:46
Related: (4061) – Mr.Wizard Jan 23 '15 at 22:41

test = {5, 6, 9, 3, 2, 6, 7, 8, 1, 1, 4, 7}

MaxFilter[test, 1]

(* {6, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7} *)


You can also use

Max /@ Transpose[{Rest[Append[#, 0]], #, Most[Prepend[#, 0]]}] &[yourList]


which is competitive with the MM MaxFilter, but will allow you to change the 'slide' (e.g.pad with zeroes, or other arbitrary 'start').

-
We've got a winner – Rojo Jan 16 '14 at 7:40
+1 This function needs to be in more "See also: " sections in the documentation! – Aky Jan 16 '14 at 7:47
I was looking for this but there was no link around MovingAverage :( – Kuba Jan 16 '14 at 7:48
Yes, WRI could do a better job there. Most of the stuff they call 'image processing' has a myriad of other uses. – ciao Jan 16 '14 at 7:49
This MaxFilter method can only handle "windows" of odd-numbered elements, since it's based on a radius, e.g. MaxFilter[test, 1] finds the maximum of 3 elements at a time, MaxFilter[test, 2] finds the maximum of 5 elements at a time, etc. For those wishing to use arbitrary window sizes, see mathematica.stackexchange.com/a/78269/6944, where I've come up with a trick for handling the even cases. – Andrew Cheong Mar 26 '15 at 10:02

Using the fourth and fifth arguments of Partition gives you exactly what you want

lis = {5, 6, 9, 3, 2, 6, 7, 8, 1, 1, 4, 7}
Max @@@ Partition[lis, 3, 1, {2, 2}, {}]


Gives:

{6, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7}

Update

As Simon Wood suggested in the comment below (I also know this but on my system the difference isn't that much), Maping Max instead of Applying it makes a difference. Also interesting, I don't notice that much difference between DeveloperPartitionMapand pure Partition with Map as my timing shows with an even bigger data size, this may be a difference in version (I'm on v. 9.0.1).

Timings

lis2 = RandomInteger[10, 10^7];

(* My Solution updated with Map *)
AbsoluteTiming[Max /@ Partition[lis2, 3, 1, {2, 2}, {}]][[1]]

(* 6.203406 *)

(* My Original Solution using Apply *)

AbsoluteTiming[Max @@@ Partition[lis2, 3, 1, {2, 2}, {}]][[1]]

(* 7.750364 *)

(* Anon's Solution using PartitionMap *)

AbsoluteTiming[DeveloperPartitionMap[Max, lis2, 3, 1, {2, 2}, {}]][[1]]

(* 5.675949 *)

(* Kuba's ListConvolve (You can also use ListCorrelate) *)

AbsoluteTiming[ListConvolve[{1, 1, 1}, lis2, {2, -2}, {}, Times, Max]][[1]]

(* 12.078693 *)

(* rasher's winner using MaxFilter *)

AbsoluteTiming[MaxFilter[lis2, 1]][[1]]

(* 0.640655 *)

(* rasher's second equally fast solution using Transpose and co. *)

AbsoluteTiming[Max /@ Transpose[{Rest[Append[#, 0]], #, Most[Prepend[#, 0]]}] &[lis2]][[1]]

(* 0.765662 *)


Clearly, rasher's methods are winners.

-
You're a better partitioner than I sir! – Codie CodeMonkey Jan 16 '14 at 6:43
@CodieCodeMonkey. Thank you sir! Partition is a very powerful too. I spent quite a while exploring how to use it. Sal Mangano also does a good job on his website explaining it. – RunnyKine Jan 16 '14 at 6:47
As a curiosity I might add that I learned about DeveloperPartitionMap, which is undocumented, that I use from Sal Manganos' Mathematica Cookbook. I've since seen it on here. But he implements moving average, which is the same kind of operation, not with PartitionMap but with ListConvolve thus making him a possible reference for all three methods hehe :) – C. E. Jan 16 '14 at 7:27
@Anon, I also learned about DeveloperPartitionMap from Sal's book – RunnyKine Jan 16 '14 at 7:29
@Anon I used double () at the beginning and end – RunnyKine Jan 16 '14 at 7:36

Another option is DeveloperPartitionMap. In RunnyKine's solution we first partition the list and sweep through it to add Max to every element. With DeveloperPartitionMap we can do both at the same time, which is faster.

Here's a table for reference. My first table was incorrect and I apologize for that, it was an honest mistake which I am not sure how it happened:

lis = RandomInteger[10, 10^6];

AbsoluteTiming[DeveloperPartitionMap[Max, lis, 3, 1, {2, 2}, {}]][[1]]
(* Out: 0.578836 *)

(* RunnyKine's solution: *)
AbsoluteTiming[Max /@ Partition[lis, 3, 1, {2, 2}, {}]][[1]]
(* Out: 0.698822 *)

(* Kuba's solution: *)
AbsoluteTiming[ListConvolve[{1, 1, 1}, lis, {2, -2}, {}, Times, Max]][[1]]
(* Out: 1.294132 *)


Did not see this coming! Rasher's method that he just posted is way faster:

AbsoluteTiming[MaxFilter[lis, 1]][[1]]
(* Out: 0.070911 *)

-
Faster and less memory hungry – Rojo Jan 16 '14 at 7:20
;-) - one of the seldom used but sometimes really useful functions! – ciao Jan 16 '14 at 7:47

Just a different method:

lis = {5, 6, 9, 3, 2, 6, 7, 8, 1, 1, 4, 7};

ListConvolve[{1, 1, 1}, lis, {2, -2}, {}, Times, Max]

{6, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7}

-
A modification: ListConvolve[{1, 1, 1}, li, {2, -2}, -Infinity, #2 &, Max], which unfortunately isn't any faster (as opposed to what I wrote previously in a comment! - I compared with different sizes of data by mistake) – Aky Jan 16 '14 at 7:36
@Aky Indeed it isn't but I find you comment useful anyway :) – Kuba Jan 16 '14 at 7:37

Dilation produces the same output as MaxFilter and has comparable speed.

test = {5, 6, 9, 3, 2, 6, 7, 8, 1, 1, 4, 7};

Dilation[test, 1]
(* {6, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7} *)


It also has a Padding option which may be convenient:

Dilation[test, 1, Padding -> 10]
(* {10, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 10} *)
(* {7, 9, 9, 9, 6, 7, 8, 8, 8, 4, 7, 7} *)


Using RunnyKine's test setup we get speeds comparable to rasher's two methods:

lis2 = RandomInteger[10, 10^7];

AbsoluteTiming[Dilation[lis2, 1]][[1]]
(* 0.754053 *)
AbsoluteTiming[MaxFilter[lis2, 1]][[1]]
(* 0.678272 *)
AbsoluteTiming[Max /@ Transpose[{Rest[Append[#, 0]], #,
Most[Prepend[#, 0]]}] &[lis2]][[1]]
(* 0.786325 *)
`
-
Not quite the same results - you're kind of forced to check ends and pad or jump through other hoops (e.g. where there's a negative on one or both ends)... and as span of what's to be maxed increases, you need to check for more and more cases like that... but neat answer, so +1 and stay tuned for more. – ciao Apr 25 '15 at 22:34