r - que - sucesiones monotonas y acotadas

¿Cómo verificar si una secuencia de números es monótonamente creciente(o decreciente)?

Question

Se nos da una secuencia de números, como un vector foo . La tarea es encontrar que foo está aumentando monótonamente - cada elemento es menor o igual que el siguiente - o disminuyendo monótonamente - cada elemento mayor o igual que el siguiente.

Seguro que esto se puede encontrar a través de un bucle, pero ¿hay más ideas creativas?

Answer 1

Otro: verifique si

all(x == cummax(x))

o

all(x == cummin(x))

para aumentar o disminuir monótonamente, respectivamente. Parece que cummax es mucho más rápido que diff y también usa menos memoria:

> 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

Mi apuesta sobre por qué cummax es más rápido que diff es porque solo tiene que comparar números, que es más rápido que tener que calcular diferencias.

Editar : a petición de (Ali), pruebas adicionales que incluyan su respuesta (tenga en cuenta que ahora estoy ejecutando desde una máquina diferente, por lo que los siguientes resultados no se deben comparar con los anteriores)

> 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

Para la versión en aumento, puede usar is.unsorted() :

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

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

Esto es bastante rápido también:

> 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

Desafortunadamente is.unsorted() es explícitamente para aumentar el orden. Nos llevamos un poco de golpe convirtiendo esto a una situación decreciente, pero sigue siendo competitivo con las otras opciones en mi sistema:

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

Y en un problema más grande ...

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

Si desea forzar una secuencia estrictamente creciente, entonces vea strictly in ?is.unsorted .

Answer 3

Una opción es emplear la función diff() para dar las diferencias entre elementos adyacentes en un vector.

Una función monótonamente creciente tendrá diff(x) todo> o igual a 0:

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

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

Aunque probar la igualdad a 0 puede ser mal visto; mejor podría ser utilizar < 0 y negar la comparación a través de ! :

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

La razón de esto es que estás usando una computadora en la que no todos los números se pueden representar exactamente. Puede calcular un resultado que sea efectivamente cero pero no exactamente cero porque los números en el cálculo no se pudieron representar exactamente (es decir, puntos flotantes ). Entonces, si foo es el resultado de un cálculo, probar si es igual a 0 podría ser algo que debería ser 0 un poco mayor que o menor que 0, que luego puede dar el resultado incorrecto para una función creciente / decreciente.

Answer 4

Una respuesta interesante es la siguiente:

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 5

all(diff(x)<0) (sustituto > , <= , >= según corresponda)