Der schnellste Weg, um den zweiten (dritten…) höchsten / niedrigsten Wert im Vektor oder in der Spalte zu finden

160

R bietet max und min, aber ich sehe keinen wirklich schnellen Weg, um den anderen Wert in der Reihenfolge zu finden, außer den gesamten Vektor zu sortieren und dann den Wert x aus diesem Vektor auszuwählen.

Gibt es einen schnelleren Weg, um den zweithöchsten Wert zu erhalten (z. B.)?

Vielen Dank

jorgusch
quelle
Der Paket - Kit auf CRAN hat eine topnFunktion , die als schneller ist sort, orderund nth. Schauen Sie sich die Dokumentation an.
Suresh_Patel

Antworten:

195

Verwenden Sie das partialArgument von sort(). Für den zweithöchsten Wert:

n <- length(x)
sort(x,partial=n-1)[n-1]
Rob Hyndman
quelle
4
Was ist der Vorteil dieser Methode gegenüber sort(x, TRUE)[2]der in der Antwort von @ Abrar beschriebenen, abgesehen davon, dass die Einschränkung in der Frage nicht erfüllt wird?
Hugh
5
Ich habe diese Methode verwendet, erhalte jedoch den folgenden Fehler: Error in sort.int(x, na.last = na.last, decreasing = decreasing, ...) : index 4705 outside bounds Irgendeine Idee, woran das liegen könnte? Einige Details: Mein x ist ein numerischer Vektor der Länge 4706 mit einigen NAs in den Daten. Ich habe versucht, den zweithöchsten Wert im Vektor mit genau demselben Code zu erhalten, den @RobHyndman vorgeschlagen hat.
Sriramn
Warum sortierst du nicht absteigend und nimmst den zweiten von nur zwei Werten? Wäre das nicht schneller?
JWG
3
Das absteigende Argument ist nicht mit der Teilsortierung kompatibel.
Rob Hyndman
7
Obwohl das decreasingArgument nicht mit der Teilsortierung kompatibel ist, können Sie dies immer -sort(-x, partial=n-1)[n-1]tun. es ist logisch dasselbe und dauert erheblich kürzer als sort(x, decreasing=TRUE)[n-1].
R2evans
52

Etwas langsamere Alternative, nur für die Aufzeichnungen:

x <- c(12.45,34,4,0,-234,45.6,4)
max( x[x!=max(x)] )
min( x[x!=min(x)] )
Paolo
quelle
Es wäre überraschend, wenn dies schneller wäre, als den gesamten Vektor zu sortieren und den n-1-ten Wert anzunehmen!
JWG
@jwg Dies ist O (n), daher muss es schneller sein als das Sortieren nach großen Datenmengen.
Museful
Funktioniert besser mit NAs als mit anderen akzeptierten Antworten - verwenden Sie einfach 'na.rm = TRUE' als Argument für die 'min'-Funktion.
Yair Daon
2
Es scheint mir, dass Sie mit einer kleinen Modifikation eine beträchtliche Geschwindigkeitsverbesserung max(x[-which.max(x)])
erzielen können
31

Ich habe Robs Antwort in eine etwas allgemeinere Funktion zusammengefasst, mit der das 2., 3., 4. (usw.) Maximum ermittelt werden kann:

maxN <- function(x, N=2){
  len <- length(x)
  if(N>len){
    warning('N greater than length(x).  Setting N=length(x)')
    N <- length(x)
  }
  sort(x,partial=len-N+1)[len-N+1]
}

maxN(1:10)
Zach
quelle
1
Cool. Diese Verwendung ist besonders nützlich maxN(1:10, 1:3)(ich hätte die Standardeinstellung N auf 1 gesetzt)
PatrickT
23

Rfast hat eine Funktion namens nth_element, die genau das tut, was Sie verlangen, und schneller ist als alle oben beschriebenen Implementierungen

Auch die oben diskutierten Methoden, die auf einer Teilsortierung basieren, unterstützen das Finden der k kleinsten Werte nicht

Rfast::nth(x, 5, descending = T)

Gibt das fünftgrößte Element von x zurück, während

Rfast::nth(x, 5, descending = F)

Gibt das fünftkleinste Element von x zurück

Benchmarks unten gegen die beliebtesten Antworten.

Für 10 Tausend Zahlen:

N = 10000
x = rnorm(N)

maxN <- function(x, N=2){
    len <- length(x)
    if(N>len){
        warning('N greater than length(x).  Setting N=length(x)')
        N <- length(x)
    }
    sort(x,partial=len-N+1)[len-N+1]
}

microbenchmark::microbenchmark(
    Rfast = Rfast::nth(x,5,descending = T),
    maxn = maxN(x,5),
    order = x[order(x, decreasing = T)[5]]
)

Unit: microseconds
  expr      min       lq      mean   median        uq       max neval
 Rfast  160.364  179.607  202.8024  194.575  210.1830   351.517   100
  maxN  396.419  423.360  559.2707  446.452  487.0775  4949.452   100
 order 1288.466 1343.417 1746.7627 1433.221 1500.7865 13768.148   100

Für 1 Million Nummern:

N = 1e6 #evaluates to 1 million
x = rnorm(N)

microbenchmark::microbenchmark(
    Rfast = Rfast::nth(x,5,descending = T),
    maxN = maxN(x,5),
    order = x[order(x, decreasing = T)[5]]
)

Unit: milliseconds
  expr      min        lq      mean   median        uq       max neval
 Rfast  89.7722  93.63674  114.9893 104.6325  120.5767  204.8839   100
  maxN 150.2822 207.03922  235.3037 241.7604  259.7476  336.7051   100
 order 930.8924 968.54785 1005.5487 991.7995 1031.0290 1164.9129   100
Stefanos
quelle
8
Nett! Wenn ich sehe, dass ein Benutzer mit relativ geringen Wiederholungszahlen eine Antwort auf eine beliebte alte Frage hinzufügt, ist diese normalerweise von ziemlich geringer Qualität. Dies ist andererseits eine ausgezeichnete Ergänzung. Ich habe einige Änderungen an der Lesbarkeit vorgenommen, aber es sieht gut aus!
Gregor Thomas
3
Es ist zu erwähnen, dass Rfast::nthmehrere Elemente (z. B. das 8. und 9. größte Element) sowie die Indizes dieser Elemente zurückgegeben werden können.
Jasha
3
Was mir an der Rfast-Lösung gefällt, ist, dass das Paket auch eine einfach zu implementierende Lösung für jede Zeile oder Spalte enthält.
Jay
16

Hier ist eine einfache Möglichkeit, die Indizes von N kleinsten / größten Werten in einem Vektor zu finden (Beispiel für N = 3):

N <- 3

N Kleinste:

ndx <- order(x)[1:N]

N Größte:

ndx <- order(x, decreasing = T)[1:N]

Sie können die Werte also wie folgt extrahieren:

x[ndx]
Davit Sargsyan
quelle
Dies läuft in L log L Zeit, wobei L die Länge von x ist. Ich denke, der Benutzer hatte auf eine Methode gehofft, die in log L-Zeit ausgeführt wird.
Arsmath
Dies könnte der zweitschnellste Weg sein, wenn die Methoden nach Zeit geordnet und das schnellste N extrahiert würden. Ich mag es auch, weil es im Vergleich zur akzeptierten Lösung ein sehr klarer Code ist.
Pete
1
Die theoretisch beste und akzeptierte Methode läuft (hoffentlich) in O (L) -Zeit, nicht in O (log L). Dieser läuft in O (L log L).
Valentas
6

Für den n-ten höchsten Wert

sort(x, TRUE)[n]
Abrar
quelle
8
Das OP sagte bereits in seinem Beitrag, dass dies eine Lösung sei, die er nicht verwenden wollte: "Abgesehen davon, dass der gesamte Vektor sortiert und dann der Wert x aus diesem Vektor ausgewählt wird".
Paul Hiemstra
3

Ich habe festgestellt, dass das Entfernen des max-Elements zuerst und das Ausführen eines weiteren max-Elements mit vergleichbarer Geschwindigkeit erfolgt:

system.time({a=runif(1000000);m=max(a);i=which.max(a);b=a[-i];max(b)})
   user  system elapsed 
  0.092   0.000   0.659 

system.time({a=runif(1000000);n=length(a);sort(a,partial=n-1)[n-1]})
   user  system elapsed 
  0.096   0.000   0.653 
John Jiang
quelle
2

Hier ist der einfachste Weg, den ich gefunden habe:

num <- c(5665,1615,5154,65564,69895646)

num <- sort(num, decreasing = F)

tail(num, 1)                           # Highest number
head(tail(num, 2),1)                   # Second Highest number
head(tail(num, 3),1)                   # Third Highest number
head(tail(num, n),1)                   # Generl equation for finding nth Highest number
Vin
quelle
1

Als ich kürzlich nach einer R- Funktion suchte, die Indizes der Top-N-Max / Min-Zahlen in einem bestimmten Vektor zurückgibt, war ich überrascht, dass es keine solche Funktion gibt.

Und das ist etwas sehr Ähnliches.

Die Brute-Force-Lösung mit der Funktion base :: order scheint die einfachste zu sein.

topMaxUsingFullSort <- function(x, N) {
  sort(x, decreasing = TRUE)[1:min(N, length(x))]
}

Es ist jedoch nicht das schnellste, wenn Ihr N- Wert im Vergleich zur Länge des Vektors x relativ klein ist .

Auf der anderen Seite, wenn das N wirklich klein ist, können Sie die Funktion base :: whichMax iterativ verwenden und in jeder Iteration den gefundenen Wert durch -Inf ersetzen

# the input vector 'x' must not contain -Inf value 
topMaxUsingWhichMax <- function(x, N) {
  vals <- c()
  for(i in 1:min(N, length(x))) {
    idx      <- which.max(x)
    vals     <- c(vals, x[idx]) # copy-on-modify (this is not an issue because idxs is relative small vector)
    x[idx]   <- -Inf            # copy-on-modify (this is the issue because data vector could be huge)
  }
  vals
}

Ich glaube, Sie sehen das Problem - die Copy-on-Modify-Natur von R. Dies wird also für sehr sehr sehr kleine N (1,2,3) besser funktionieren, aber für größere N-Werte wird es schnell langsamer. Und Sie iterieren über alle Elemente im Vektor x N- mal.

Ich denke, die beste Lösung in sauberem R ist die Verwendung von partieller base :: sort .

topMaxUsingPartialSort <- function(x, N) {
  N <- min(N, length(x))
  x[x >= -sort(-x, partial=N)[N]][1:N]
}

Dann können Sie das letzte ( N- te) Element aus dem Ergebnis der oben genannten Funktionen auswählen.

Hinweis: Die oben definierten Funktionen sind nur Beispiele. Wenn Sie sie verwenden möchten, müssen Sie die Eingaben überprüfen / überprüfen (z. B. N> Länge (x). ).

Ich habe unter http://palusga.cz/?p=18 einen kleinen Artikel über etwas sehr Ähnliches geschrieben (Indizes der Top-N-Max / Min-Werte eines Vektors abrufen ). Hier finden Sie einige Benchmarks für ähnliche Funktionen, die ich oben definiert habe.

Donarus
quelle
1

head(sort(x),..)oder tail(sort(x),...)sollte funktionieren

Job Mangelmans
quelle
0
topn = function(vector, n){
  maxs=c()
  ind=c()
  for (i in 1:n){
    biggest=match(max(vector), vector)
    ind[i]=biggest
    maxs[i]=max(vector)
    vector=vector[-biggest]
  }
  mat=cbind(maxs, ind)
  return(mat)
}

Diese Funktion gibt eine Matrix mit den oberen n Werten und ihren Indizes zurück. hoffe es hilft VDevi-Chou

vdc320
quelle
0

Dies findet den Index des N'ten kleinsten oder größten Wertes im numerischen Eingabevektor x. Setzen Sie in den Argumenten bottom = TRUE, wenn Sie das N'th von unten wollen, oder bottom = FALSE, wenn Sie das N'th von oben wollen. N = 1 und bottom = TRUE ist äquivalent zu which.min, N = 1 und bottom = FALSE ist äquivalent zu which.max.

FindIndicesBottomTopN <- function(x=c(4,-2,5,-77,99),N=1,bottom=FALSE)
{

  k1 <- rank(x)
  if(bottom==TRUE){
    Nindex <- which(k1==N)
    Nindex <- Nindex[1]
  }

  if(bottom==FALSE){
    Nindex <- which(k1==(length(x)+1-N))
    Nindex <- Nindex[1]
  }

  return(Nindex)
}
Ralph
quelle
0

dplyr hat die Funktion n-te, wobei das erste Argument der Vektor und das zweite die gewünschte Stelle ist. Dies gilt auch für sich wiederholende Elemente. Beispielsweise:

x = c(1,2, 8, 16, 17, 20, 1, 20)

Den zweitgrößten Wert finden:

 nth(unique(x),length(unique(x))-1)

[1] 17
Noale
quelle
2
ist das schnell ...?
Ben Bolker
2
intern wird dies verwendet x[[order(order_by)[[n]]]]- daher muss der gesamte Vektor sortiert werden. Es wird also nicht so schnell sein wie die akzeptierte Antwort.
Ben Bolker
5
aber es verwendet sort mit dem partiellen = Argument (das alles ändert)
Ben Bolker
@BenBolker, was impliziert, dass Paolos oder Robs Antwort zur Verbesserung verwendet werden könnte dplyr::nth()? bench::mark(max(x[-which.max(x)]), x[[order(-x)[[2]]]] ), nth()Scheint fast 10 - mal langsamer, wo length(x)3.000.000 ist.
Sindri_baldur
-1

Sie können den nächsthöheren Wert mit identifizieren cummax(). Wenn Sie beispielsweise die Position jedes neuen höheren Werts möchten, können Sie Ihren Wertevektor cummax()an die diff()Funktion übergeben, um Positionen zu identifizieren, an denen sich der cummax()Wert geändert hat. Sagen wir, wir haben den Vektor

v <- c(4,6,3,2,-5,6,8,12,16)
cummax(v) will give us the vector
4  6  6  6  6  6  8 12 16

Wenn Sie nun den Ort einer Änderung in finden möchten, stehen cummax()Ihnen viele Optionen zur Verfügung, die ich normalerweise verwende sign(diff(cummax(v))). Sie müssen sich wegen auf das verlorene erste Element einstellen diff(). Der vollständige Code für den Vektor vwäre:

which(sign(diff(cummax(v)))==1)+1
user3507767
quelle
Ich denke, Sie verstehen die Frage falsch. Ziel ist es, beispielsweise den zweithöchsten Wert zu finden. Wie hilft das, Sie von v auf 12 zu bringen ... und für die dritthöchste auf 8?
Frank
-1

Sie können das sortSchlüsselwort folgendermaßen verwenden:

sort(unique(c))[1:N]

Beispiel:

c <- c(4,2,44,2,1,45,34,2,4,22,244)
sort(unique(c), decreasing = TRUE)[1:5]

gibt die ersten 5 maximalen Zahlen.

Chethanraj Rao
quelle