wake-up-neo.com

Der schnellste Weg, um den zweiten (dritten ...) höchsten/niedrigsten Wert in einem Vektor oder einer Spalte zu finden

R bietet max und min, aber ich sehe keinen wirklich schnellen Weg, den anderen Wert in der Reihenfolge zu finden, abgesehen vom Sortieren des gesamten Vektors und dem Auswählen des Werts x aus diesem Vektor.

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

Vielen Dank

146
jorgusch

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

n <- length(x)
sort(x,partial=n-1)[n-1]
181
Rob Hyndman

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)] )
46
Paolo

Ich habe Robs Antwort zu einer etwas allgemeineren Funktion zusammengefasst, mit der das 2., 3., 4. (usw.) Maximum gefunden 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)
27
Zach

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

N <- 3

N kleinste:

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

N größte:

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

So können Sie die Werte wie folgt extrahieren:

x[ndx]
15
Davit Sargsyan

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

Auch die oben diskutierten Methoden, die auf partieller Sortierung 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 5. kleinste Element von x zurück

Benchmarks unten gegen die meisten Antworten.

Für zehntausend 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 10 Millionen Zahlen:

N = 1e6
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
10
Stefanos

Für den n-ten höchsten Wert

sort(x, TRUE)[n]
4
Abrar

Ich habe herausgefunden, dass das Max-Element zuerst entfernt wird und dann ein weiteres Max mit vergleichbarer Geschwindigkeit ausgeführt wird:

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 
3
John Jiang

Als ich kürzlich nach einer R -Funktion gesucht habe, die Indizes der höchsten 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.

Wenn das N sehr klein ist, können Sie base :: whichMax iterativ und in jeder Iteration verwenden Ersetzen Sie den gefundenen Wert durch - Inf

# 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 Art des Kopierens und Modifizierens von R. Dies führt also zu einer besseren Leistung für sehr, sehr kleine N (1,2,3), verlangsamt sich jedoch bei größeren N-Werten rapide. Und Sie iterieren über alle Elemente im Vektor x N mal.

Ich denke, die beste Lösung für clean R ist die Verwendung von partial 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 th) 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/sanity-Eingaben überprüfen (z. B. N> Länge (x)).

Ich habe unter http://palusga.cz/?p=18 einen kleinen Artikel über etwas sehr ähnliches geschrieben (Indexe der höchsten N max/min-Werte eines Vektors abrufen) - hier finden Sie einige Benchmarks von ähnlichen Funktionen, die ich oben definiert habe.

1
Donarus

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

1
Job Mangelmans

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

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

Den zweitgrößten Wert finden:

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

[1] 17
0
Noale
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

0
vdc320

Dadurch wird der Index des N-ten kleinsten oder größten Werts im numerischen Eingabevektor x ermittelt. Setzen Sie in den Argumenten bottom = TRUE, wenn Sie das N-te von unten wünschen, oder bottom = FALSE, wenn Sie das n-te 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)
}
0
Ralph