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

Question

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

т.е. то, что

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

до

max()

но для

which.max()

Лучшее

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

Answer 1

Один из возможных путей - использовать аргумент index.return для sort.Я не уверен, что это быстрее всего.

set.seed(21)
x <- rnorm(10)
ind <- 2
sapply(sort(x, index.return=TRUE), `[`, length(x)-ind+1)
#        x       ix 
# 1.746222 3.000000

Answer 2

РЕДАКТИРОВАТЬ 2:

Как указывал Джошуа, ни одно из данных решений на самом деле не работает правильно, если у вас есть связь с максимумами, поэтому:

X <- c(11:19,19)

n <- length(unique(X))
which(X == sort(unique(X),partial=n-1)[n-1])

самый быстрый способ сделать этоправильно тогда.Я удалил способ заказа, так как он не работает и работает намного медленнее, поэтому, согласно OP, не очень хороший ответ.

Чтобы указать на проблему, с которой мы столкнулись:

> X <- c(11:19,19)    
> n <- length(X)
> which(X == sort(X,partial=n-1)[n-1])
[1]  9 10 #which is the indices of the double maximum 19

> n <- length(unique(X))
> which(X == sort(unique(X),partial=n-1)[n-1])
[1] 8 # which is the correct index of 18

Сроки действительных решений:

> x <- runif(1000000)

> ind <- 2

> n <- length(unique(x))

> system.time(which(x == sort(unique(x),partial=n-ind+1)[n-ind+1]))
   user  system elapsed 
   0.11    0.00    0.11 

> system.time(sapply(sort(unique(x), index.return=TRUE), `[`, n-ind+1))
   user  system elapsed 
   0.69    0.00    0.69 

Answer 3

библиотека Rfast реализовала функцию n-го элемента с опцией return index, которая кажется быстрее, чем все другие обсуждаемые реализации.

x <- runif(1e+6)

ind <- 2


microbenchmark::microbenchmark(
        Rfast = Rfast::nth(x,ind,descending = T,index.return = T),
        order = order(x, decreasing = TRUE)[ind],
        richie = which_nth_highest_richie(x,ind),
        joris = which_nth_highest_joris(x,ind))

Unit: milliseconds
          expr       min        lq      mean    median        uq      max   neval
         Rfast  22.89945  26.03551  31.61163  26.70668  32.07650 105.0016   100
         order 113.54317 116.49898 122.97939 119.44496 124.63646 170.4589   100
        richie  26.69556  27.93143  38.74055  36.16341  44.10246 116.7192   100
         joris 126.52276 138.60153 151.49343 146.55747 155.60709 324.8605   100 

Answer 4

Метод: Установите все максимальные значения на -Inf, затем найдите индексы макс. Сортировка не требуется.

X <- runif(1e7)
system.time(
{
  X[X == max(X)] <- -Inf
  which(X == max(X))
})

Работает со связями и очень быстро.

Если вы можете гарантировать отсутствие связей, то еще более быстрая версия -

system.time(
{
  X[which.max(X)] <- -Inf
  which.max(X)
})

РЕДАКТИРОВАТЬ: Как упоминал Джорис, этот метод не так хорошо масштабируется для нахождения третьего, четвертого и т. Д., Самые высокие значения.

which_nth_highest_richie <- function(x, n)
{
  for(i in seq_len(n - 1L)) x[x == max(x)] <- -Inf
  which(x == max(x))
}

which_nth_highest_joris <- function(x, n)
{
  ux <- unique(x)
  nux <- length(ux)
  which(x == sort(ux, partial = nux - n + 1)[nux - n + 1])
}

Используя x <- runif(1e7) и n = 2, Ричи выигрывает

system.time(which_nth_highest_richie(x, 2))   #about half a second
system.time(which_nth_highest_joris(x, 2))    #about 2 seconds

Для n = 100, Джорис выигрывает

system.time(which_nth_highest_richie(x, 100)) #about 20 seconds, ouch! 
system.time(which_nth_highest_joris(x, 100))  #still about 2 seconds

Точка баланса, где они занимают одинаковое время, составляет около n = 10.

Answer 5

Нет связей which(), вероятно, ваш друг здесь. Объедините выходные данные решения sort() с which(), чтобы найти индекс, который соответствует выходным данным шага sort().

> set.seed(1)
> x <- sample(1000, 250)
> sort(x,partial=n-1)[n-1]
[1] 992
> which(x == sort(x,partial=n-1)[n-1])
[1] 145

Обработка связей Приведенное выше решение не работает должным образом (и не предназначалось для этого), если есть связи, и связи - это значения, которые являются i-м наибольшим или большим значениями. Нам нужно взять уникальные значения вектора перед сортировкой этих значений, и тогда вышеприведенное решение работает:

> set.seed(1)
> x <- sample(1000, 1000, replace = TRUE)
> length(unique(x))
[1] 639
> n <- length(x)
> i <- which(x == sort(x,partial=n-1)[n-1])
> sum(x > x[i])
[1] 0
> x.uni <- unique(x)
> n.uni <- length(x.uni)
> i <- which(x == sort(x.uni, partial = n.uni-1)[n.uni-1])
> sum(x > x[i])
[1] 2
> tail(sort(x))
[1]  994  996  997  997 1000 1000

order() также очень полезен здесь:

> head(ord <- order(x, decreasing = TRUE))
[1] 220 145 209 202 211 163

Таким образом, решение здесь ord[2] для индекса 2-го старшего / самого большого элемента x.

Некоторые тайминги:

> set.seed(1)
> X <- sample(1e7, 1e7)
> system.time({n <- length(X); which(X == sort(X, partial = n-1)[n-1])})
   user  system elapsed 
  0.319   0.058   0.378 
> system.time({ord <- order(X, decreasing = TRUE); ord[2]})
   user  system elapsed 
 14.578   0.084  14.708 
> system.time({order(X, decreasing = TRUE)[2]})
   user  system elapsed 
 14.647   0.084  14.779

Но поскольку ссылка на публикацию доходила до времени, показанного выше, order() намного медленнее, но оба дают одинаковые результаты:

> all.equal(which(X == sort(X, partial = n-1)[n-1]), 
+           order(X, decreasing = TRUE)[2])
[1] TRUE

А для версии обработки связей:

foo <- function(x, i) {
    X <- unique(x)
    N <- length(X)
    i <- i-1
    which(x == sort(X, partial = N-i)[N-i])
}

> system.time(foo(X, 2))
   user  system elapsed 
  1.249   0.176   1.454

Таким образом, дополнительные шаги немного замедляют это решение, но оно все еще очень конкурентоспособно с order().

Answer 6

Используйте функцию maxN, заданную Заком для , найдите следующее максимальное значение и используйте which () с arr.ind = TRUE.

который (x == maxN (x, 4), arr.ind = TRUE)

Использование arr.ind также вернет позицию индекса в любом из вышеперечисленных решений и упростит код.

Answer 7

Это мое решение для нахождения индекса верхних N самых высоких значений в векторе (не совсем то, что хотел ОП, но это может помочь другим людям)

index.top.N = function(xs, N=10){
    if(length(xs) > 0) {
    o = order(xs, na.last=FALSE)
    o.length = length(o)
    if (N > o.length) N = o.length
    o[((o.length-N+1):o.length)]
  }
  else {
    0
  }
}