Najszybszy sposób na znalezienie drugiej (trzeciej…) najwyższej / najniższej wartości w wektorze lub kolumnie

R oferuje max i min, ale nie widzę naprawdę szybkiego sposobu na znalezienie innej wartości w zamówieniu, poza sortowaniem całego wektora, a następnie wybraniem wartości x z tego wektora.

Czy jest na przykład szybszy sposób uzyskania drugiej najwyższej wartości?

Użyj partialargumentu sort(). Dla drugiej największej wartości:

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

Nieco wolniejsza alternatywa, tylko dla rekordów:

x <- c(12.45,34,4,0,-234,45.6,4)
max( x[x!=max(x)] )
min( x[x!=min(x)] )

Zawinąłem odpowiedź Roba w nieco bardziej ogólną funkcję, której można użyć do znalezienia drugiego, trzeciego, czwartego (itd.) Maksimum:

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)

Rfast ma funkcję o nazwie nth_element, która robi dokładnie to, o co prosisz i jest szybsza niż wszystkie implementacje omówione powyżej

Również metody omówione powyżej, które są oparte na sortowaniu częściowym, nie obsługują znajdowania k najmniejszych wartości

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

Zwróci piąty co do wielkości element x, a

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

Zwróci 5. najmniejszy element x

Poniższe testy porównawcze z najpopularniejszymi odpowiedziami.

Za 10 tysięcy numerów:

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

Za 1 milion numerów:

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

Oto prosty sposób na znalezienie indeksów N najmniejszych / największych wartości w wektorze (przykład dla N = 3):

N <- 3

N najmniejszy:

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

N Największy:

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

Możesz więc wyodrębnić wartości jako:

x[ndx]

Dla n-tej najwyższej wartości,

sort(x, TRUE)[n]

Odkryłem, że najpierw usuwam element max, a następnie wykonuję kolejne przebiegi maksymalne z porównywalną prędkością:

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 

Oto najprostszy sposób, jaki znalazłem,

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

Kiedy ostatnio szukałem funkcji R zwracającej indeksy najwyższych N max / min w danym wektorze, byłem zaskoczony, że nie ma takiej funkcji.

I to jest coś bardzo podobnego.

Rozwiązanie siłowe wykorzystujące funkcję base :: order wydaje się najłatwiejsze.

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

Ale nie jest to najszybsze, jeśli wartość N jest stosunkowo mała w porównaniu z długością wektora x .

Z drugiej strony, jeśli N jest naprawdę małe, możesz użyć iteracyjnie funkcji base :: whichMax, aw każdej iteracji możesz zastąpić znalezioną wartość -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
}

Wydaje mi się, że widzisz problem - naturę R. polegającą na kopiowaniu przy modyfikacji, więc będzie to działać lepiej dla bardzo, bardzo, bardzo małych N (1, 2, 3), ale szybko zwolni przy większych wartościach N. I iterujesz po wszystkich elementach w wektorze x N razy.

Myślę, że najlepszym rozwiązaniem w czystym R jest użycie częściowej bazy :: sort .

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

Następnie możesz wybrać ostatnią ( N- tą) pozycję z wyniku funkcji defiend powyżej.

Uwaga: funkcje zdefiniowane powyżej to tylko przykłady - jeśli chcesz z nich skorzystać, musisz sprawdzić dane wejściowe / sanity (np. N> length (x) ).

Napisałem mały artykuł o czymś bardzo podobnym (pobierz indeksy górnych wartości N max / min wektora) na http://palusga.cz/?p=18 - możesz znaleźć tutaj kilka testów podobnych funkcji, które zdefiniowałem powyżej.

head(sort(x),..)lub tail(sort(x),...)powinien działać

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)
}

ta funkcja zwróci macierz z n górnymi wartościami i ich indeksami. mam nadzieję, że to pomaga VDevi-Chou

Pozwoli to znaleźć indeks N-tej najmniejszej lub największej wartości w wejściowym wektorze liczbowym x. Ustaw bottom = TRUE w argumentach, jeśli chcesz, aby N-ty od dołu, lub bottom = FALSE, jeśli chcesz, aby N-ty od góry. N = 1 i bottom = TRUE jest równoważne któremu. Min, N = 1 i bottom = FALSE jest równoważne któremu. 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)
}

dplyr ma funkcję nth, gdzie pierwszy argument to wektor, a drugi to żądane miejsce. Dotyczy to również powtarzających się elementów. Na przykład:

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

Znajdowanie drugiej największej wartości:

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

[1] 17

Możesz zidentyfikować następną wyższą wartość za pomocą cummax(). Jeśli chcesz na przykład lokalizację każdej nowej wyższej wartości, możesz przekazać swój wektor cummax()wartości do diff()funkcji, aby zidentyfikować lokalizacje, w których cummax()wartość uległa zmianie. powiedzmy, że mamy wektor

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

Teraz, jeśli chcesz znaleźć lokalizację zmiany cummax(), masz wiele opcji, z których zwykle korzystam sign(diff(cummax(v))). Musisz dostosować się do utraconego pierwszego elementu z powodu diff(). Pełny kod dla wektora vwyglądałby tak:

which(sign(diff(cummax(v)))==1)+1

Możesz użyć tego sortsłowa kluczowego w następujący sposób:

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

Przykład:

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

poda pierwsze 5 maksymalnych liczb.