如何检查一系列数字是否单调递增(或递减)？

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

all(diff(x)<0)(替代>,<=,>=如适用)

Answer 4

对于增加版本，您可以使用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。