Moving maximum function?

Question

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 }.

Answer 1

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').

Answer 2

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 Developer`PartitionMapand 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[Developer`PartitionMap[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.

Answer 3

Another option is Developer`PartitionMap. In RunnyKine's solution we first partition the list and sweep through it to add Max to every element. With Developer`PartitionMap 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[Developer`PartitionMap[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 *)

Answer 4

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}

Answer 5

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} *)
Dilation[test, 1, Padding -> "Periodic"]
(* {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 *)