Самый быстрый способ найти второе (третье ...) самое высокое / самое низкое значение в векторе или столбце

Question

R предлагает максимальное и минимальное значения, но я не вижу действительно быстрого способа найти другое значение в порядке, кроме сортировки всего вектора и выбора значения x из этого вектора.

Есть ли более быстрый способ получить второе по величине значение (например,)?

Спасибо

Answer 1

Используйте аргумент partial sort(). Для второго по величине значения:

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

Answer 2

Немного более медленная альтернатива, только для записей:

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

Answer 3

Я обернул ответ Роба в чуть более общую функцию, которую можно использовать, чтобы найти 2-й, 3-й, 4-й (и т. Д.) Максимум:

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)

Answer 4

Вот простой способ найти индексы N наименьших / наибольших значений в векторе (пример для N = 3):

N <- 3

N Наименьший:

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

N Самый большой:

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

Таким образом, вы можете извлечь значения как:

x[ndx]

Answer 5

Rfast имеет функцию nth_element, которая делает именно то, что вы просите, и работает быстрее, чем все реализации, описанные выше

Также рассмотренные выше методы, основанные на частичной сортировке, не поддерживают поиск k наименьших значений

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

Вернет 5-й по величине элемент x, в то время как

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

Вернет 5-й самый маленький элемент x

Сравнительные показатели ниже самых популярных ответов.

Для 10 тысяч номеров:

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

Для 10 миллионов номеров:

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

Answer 6

Для n-го наибольшего значения,

sort(x, TRUE)[n]

Answer 7

Я обнаружил, что сначала удаляем элемент max, а затем делаем еще один максимальный прогон с сопоставимой скоростью:

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 

Answer 8

head(sort(x),..) или tail(sort(x),...) должно работать

Answer 9

Когда я недавно искал функцию R , возвращающую индексы верхних N max / min чисел в данном векторе, я был удивлен, что такой функции нет.

И это нечто очень похожее.

Решение о грубой силе, использующее функцию base :: order , кажется самым простым.

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

Но он не самый быстрый, если ваше значение N относительно мало по сравнению с длиной вектора x .

С другой стороны, если N действительно маленький, вы можете использовать функцию base :: whichMax итеративно, и в каждой итерации вы можете заменить найденное значение на -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
}

Я полагаю, вы видите проблему - природу копирования при модификации R. Так что это будет работать лучше для очень очень очень маленького N (1,2,3), но будет быстро замедляться при больших значениях N. И вы перебираете все элементы в векторе x N раз.

Я думаю, что лучшее решение в чистом R - это использовать частичное base :: sort .

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

Затем вы можете выбрать последний ( N th) элемент из результата функций, описанных выше.

Примечание: функции, определенные выше, являются просто примерами - если вы хотите их использовать, вы должны проверить / рассудить входные данные (например, N> length (x) ).

Я написал небольшую статью о чем-то очень похожем (получите индексы максимальных значений N max / min вектора) в http://palusga.cz/?p=18 - здесь вы можете найти некоторые тесты аналогичных функций, которые я определил выше.

Answer 10

dplyr имеет функцию nth, где первый аргумент - это вектор, а второй - то место, которое вы хотите. Это касается и повторяющихся элементов. Например:

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

Нахождение второго по величине значения:

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

[1] 17