Fastest way to find *the index* of the second (third...) highest/lowest value in vector or column

One possible route is to use the index.return argument to sort. I'm not sure if this is fastest though.

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

EDIT 2 :

As Joshua pointed out, none of the given solutions actually performs correct when you have a tie on the maxima, so :

X <- c(11:19,19)

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

fastest way of doing it correctly then. I deleted the order way, as that one doesn't work and is a lot slower, so not a good answer according to OP.

To point to the issue we ran into :

> 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

The timings of the valid solutions :

> 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

library Rfast has implemented the nth element function with return index option, which seems to be faster than all other implementations discussed.

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

Tags:

R

Recent Posts