How to check if a sequence of numbers is monotonically increasing (or decreasing)?

Question

We are given a sequence of numbers, as a vector foo. The task is to find is foo is monotonically increasing - every item is less than or equal to the next one - or monotonically decreasing - every item greater than or equal than the next one.

For sure this can be found through a loop, but any more creative ideas?

Answer 1

Another one: check if

all(x == cummax(x)) 

or

all(x == cummin(x)) 

for monotonously increasing or decreasing respectively. It seems that cummax is a lot faster than diff and also uses less memory:

> x <- seq_len(1e7) > system.time(all(x == cummax(x)))    user  system elapsed     0.11    0.00    0.11  > system.time(all(diff(x) >= 0))    user  system elapsed     0.47    0.13    0.59  > x <- seq_len(1e8) > system.time(all(x == cummax(x)))    user  system elapsed     1.06    0.09    1.16  > system.time(all(diff(x) >= 0)) Error: cannot allocate vector of size 381.5 Mb In addition: Warning messages: 1: Reached total allocation of 1535Mb: see help(memory.size)  2: Reached total allocation of 1535Mb: see help(memory.size)  3: Reached total allocation of 1535Mb: see help(memory.size)  4: Reached total allocation of 1535Mb: see help(memory.size)  Timing stopped at: 1.96 0.38 2.33 

My bet as to why cummax is faster than diff is because it only has to compare numbers which is faster than having to compute differences.

Edit: at your (Ali's) request, additional tests including your answer (Note that I am now running from a different machine so the following results should not be compared with the ones above)

> x <- seq_len(1e7) > system.time(x == cummax(x))    user  system elapsed    0.316   0.096   0.416  > system.time(all(diff(x) >= 0))    user  system elapsed    4.364   0.240   4.632  > system.time(x[-1] - x[-length(x)] >= 0)    user  system elapsed    3.828   0.380   4.227 > system.time(all(x[-1] >= x[-length(x)]))    user  system elapsed    2.572   0.288   2.865  

Answer 2

One option is to employ the diff() function to give the differences between adjacent elements in a vector.

An monotonically increasing function will have diff(x) all > or equal to 0:

f1 <- 1:10 f2 <- 10:1  > all(diff(f1) >= 0) [1] TRUE > all(diff(f2) >= 0) [1] FALSE 

Although testing for equality to 0 may be frowned upon; better might be to use < 0 and negate the comparison via !:

> all(!diff(f1) < 0) [1] TRUE > all(!diff(f2) < 0) [1] FALSE 

The reason for this is that you are using a computer in which not all numbers can be represented exactly. You might compute a result that is effectively zero but not quite zero because the numbers in calculation couldn't be represented exactly (i.e. floating points). So if foo is the result of a computation, testing if it equals 0 might resulting is something that should be 0 being a tiny bit greater than or less than 0 which may then given the wrong result for an increasing/decreasing function.