How to check if a sequence of numbers is monotonic

问题:

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?

回答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 

回答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.

回答3:

all(diff(x)<0) (substitute >, <=, >= as appropriate)

回答4:

For the increasing version, you could use is.unsorted():

x <- seq_len(1e7)
!is.unsorted(x)

> !is.unsorted(x)
[1] TRUE

This is pretty quick too:

> system.time(!is.unsorted(x))
   user  system elapsed 
  0.099   0.000   0.099 
> system.time(all(x == cummax(x)))
   user  system elapsed 
  0.320   0.039   0.360

Unfortunately is.unsorted() is explicitly for increasing order. We take a bit of a hit converting this to the decreasing situation, but it's still competitive with the other options on my system:

xx <- 1e7:1
!is.unsorted(-xx)
system.time(!is.unsorted(-xx))

> system.time(!is.unsorted(-xx))
   user  system elapsed 
  0.205   0.020   0.226 
> system.time(all(xx == cummin(xx)))
   user  system elapsed 
  0.356   0.088   0.444

And on a larger problem...

x  <- 1:1e8
xx <- 1e8:1
system.time(!is.unsorted(x))
system.time(all(x == cummax(x)))
system.time(!is.unsorted(-xx))
system.time(all(xx == cummin(xx)))

> system.time(!is.unsorted(x))
   user  system elapsed 
  1.019   0.000   1.019 
> system.time(all(x == cummax(x)))
   user  system elapsed 
  3.255   0.354   3.608 
> system.time(!is.unsorted(-xx))
   user  system elapsed 
  2.089   0.561   2.650 
> system.time(all(xx == cummin(xx)))
   user  system elapsed 
  3.318   0.395   3.713

If you want to force a strictly increasing sequence, then see strictly in ?is.unsorted.

回答5:

An interesting answer is as below:

foo = c(1, 3, 7, 10, 15)
all(foo[-1] - foo[-length(foo)] >= 0) # TRUE

foo[3] = 20
all(foo[-1] - foo[-length(foo)] >= 0) # FALSE