查找向量或列中第二个(第三个......)最高/最低值的*索引*的最快方法

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个元素函数，该函数似乎比讨论的所有其他实现都要快。

x <- runif(1e+6)

ind <- 2

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

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