r - que - sucesiones monotonas y acotadas
¿Cómo verificar si una secuencia de números es monótonamente creciente(o decreciente)? (5)
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
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?
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 .
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.
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
all(diff(x)<0) (sustituto > , <= , >= según corresponda)