Как проверить, является ли последовательность чисел монотонно возрастающей (или уменьшающейся)?

Ответ 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, заключается в том, что он должен сравнивать числа, которые быстрее, чем вычислять различия.

Изменить: по вашему запросу (Ali), дополнительные тесты, включая ваш ответ (обратите внимание, что теперь я запускаюсь с другого компьютера, поэтому следующие результаты не следует сравнивать с приведенными выше)

> 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 

Ответ 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, что может дать неверный результат для функции увеличения/уменьшения.

Ответ 3

all(diff(x)<0) (замените >, <=, >= в зависимости от ситуации)

Ответ 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.

Ответ 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