如何检查数字序列是否单调递增(或递减)? [英] How to check if a sequence of numbers is monotonically increasing (or decreasing)?

问题描述

我们得到一个数字序列，作为一个向量foo.任务是找到 foo 是 单调递增 - 每一项都小于或等于下一项 - 或 单调递减 - 每一项大于或等于下一个.

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?

推荐答案

另一个:检查是否

all(x == cummax(x))

或

all(x == cummin(x))

分别用于单调递增或递减.看起来 cummax 比 diff 快很多，而且使用的内存也更少:

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

我敢打赌为什么 cummax 比 diff 快是因为它只需要比较数字，这比计算差异要快.

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 

这篇关于如何检查数字序列是否单调递增(或递减)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！