wake-up-neo.com

Wie kann man überprüfen, ob eine Zahlenfolge monoton ansteigt (oder abnimmt)?

Wir erhalten eine Zahlenfolge als Vektor foo. Die Aufgabe ist zu finden, dass foo ist monoton steigend - jedes Element ist kleiner oder gleich dem nächsten - oder monoton verringert - jedes Element ist größer oder gleich dem nächsten. 

Sicher kann man dies über eine Schleife finden, aber mehr kreative Ideen?

rvector
37
Ali

Noch eine: prüfe ob

all(x == cummax(x))

oder

all(x == cummin(x))

für monotones Ansteigen bzw. Abnehmen. Es scheint, dass cummax viel schneller als diff ist und außerdem weniger Speicher benötigt:

> 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

Ich wette, warum cummax schneller ist als diff, weil er nur Zahlen vergleichen muss, was schneller ist als die Berechnung von Unterschieden.

Edit : Auf Anfrage Ihres (ALi's) zusätzliche Tests, einschließlich Ihrer Antwort (Beachten Sie, dass ich jetzt von einem anderen Computer aus laufe, sodass die folgenden Ergebnisse nicht mit den obigen Ergebnissen verglichen werden sollten).

> 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
51
flodel

Eine Möglichkeit besteht darin, die Funktion diff() zu verwenden, um die Unterschiede zwischen benachbarten Elementen in einem Vektor zu ermitteln.

Eine monoton steigende Funktion hat diff(x) all> oder gleich 0:

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

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

Obwohl das Prüfen auf Gleichheit mit 0 nicht gern gesehen wird; Es könnte besser sein, < 0 zu verwenden und den Vergleich über ! zu negieren:

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

Der Grund dafür ist, dass Sie einen Computer verwenden, auf dem nicht alle Zahlen exakt dargestellt werden können. Sie können ein Ergebnis berechnen, das praktisch Null ist, aber nicht ganz Null, da die Zahlen in der Berechnung nicht exakt dargestellt werden konnten (d. H. Fließkommazahlen ). Wenn also foo das Ergebnis einer Berechnung ist, könnte das Testen, ob es gleich 0 ist, möglicherweise zu einem Ergebnis führen, bei dem 0 ein kleines Bit größer oder kleiner als 0 sein sollte, was dann das falsche Ergebnis für eine zunehmende/abnehmende Funktion ergibt.

14
Gavin Simpson

all(diff(x)<0) (ersetzen Sie ggf. >, <=, >=)

7
Ben Bolker

Für die aufsteigende Version können Sie is.unsorted() verwenden:

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

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

Das ist auch ziemlich schnell:

> 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

Leider ist is.unsorted() explizit für die Erhöhung der Reihenfolge. Wir haben ein bisschen Erfolg, wenn wir dies in die abnehmende Situation umwandeln, aber es ist immer noch konkurrenzfähig mit den anderen Optionen meines Systems:

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

Und bei einem größeren Problem ...

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

Wenn Sie eine streng zunehmende Sequenz erzwingen möchten, lesen Sie strictly in ?is.unsorted.

4
Gavin Simpson

Eine interessante Antwort ist wie folgt:

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
0
Ali