如何检查数字序列是否单调递增（或递减）？

Question

我们得到一个数字序列，作为向量

foo

。任务是找到

foo

是 单调递增 - 每一项都小于或等于下一项 - 或 单调递减 - 每一项都大于或等于下一项。

当然可以通过循环找到这个，但是还有更多创意吗？

Answer 1

另一项：检查是否

all(x == cummax(x))

或

all(x == cummin(x))

分别表示单调增加或单调减少。看起来

cummax

比

diff

快很多，而且占用的内存也更少：

> 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

我敢打赌为什么

cummax

比

diff

更快是因为它只需要比较数字，这比计算差异更快。

编辑：根据您（阿里）的要求，进行其他测试，包括您的答案（请注意，我现在正在另一台机器上运行，因此以下结果不应与上面的结果进行比较）

> 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

一种选择是使用

diff()

函数给出向量中相邻元素之间的差异。

单调递增函数将具有

diff(x)

全部 > 或等于 0：

f1 <- 1:10
f2 <- 10:1

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

尽管测试与

0

的相等性可能会令人不悦；更好的方法可能是使用

< 0

并通过

!

否定比较：

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

原因是您使用的计算机无法准确表示所有数字。您可能会计算出实际上为零但不完全为零的结果，因为计算中的数字无法准确表示（即浮点）。因此，如果

foo

是计算结果，测试它是否等于 0 可能会导致 0 比 0 稍微大一点或小一点，然后可能会给出递增/递减函数的错误结果。

Answer 3

对于增加的版本，您可以使用

is.unsorted()

:

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

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

这也很快：

> 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

不幸的是

is.unsorted()

明确用于增加顺序。我们在将其转换为减少的情况时受到了一些打击，但与我系统上的其他选项相比，它仍然具有竞争力：

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

还有一个更大的问题......

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

如果您想强制严格递增的序列，请参阅

strictly

中的

?is.unsorted

。

Answer 4

all(diff(x)<0)

（酌情替换为

>

、

<=

、

>=

）

Answer 5

一个有趣的答案如下：

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

Answer 6

对于递增和递减序列，当您不知道序列的方向时，以下函数有效：

使用

case_when

库中的

dplyr

。

isMonotone <- function(x){
  return(
    case_when(
      all(diff(x)>=0) ~ TRUE,
      all(diff(x)<=0) ~ TRUE,
      TRUE ~ FALSE)
    )
}

isMonotone(1:10)

[1] TRUE

isMonotone(10:1)

[1] TRUE

isMonotone(c(1, 3, 2))

[1] FALSE

isMonotone(c(-1, 3, -2))

[1] FALSE