[解決済み] ベクトルまたは列の2番目（3番目...）の最大値/最小値を見つける最速の方法

質問

Rは最大値と最小値を提供しますが、ベクトル全体をソートして、このベクトルから値xを選ぶ以外に、順序で別の値を見つける本当に速い方法を私は見ません。

例えば、2番目に大きい値を得るために、もっと速い方法はないでしょうか？

どのように解決するのですか？

Rfast には nth_element という関数があり、これはまさにあなたが尋ねたとおりのことをしてくれます。

さらに、上で説明した部分ソートに基づく方法は、kの値を求めることをサポートしていません。 最小 値

更新情報 (28/FEB/21) パッケージキットはより高速な実装を提供します (topn)。 https://stackoverflow.com/a/66367996/4729755 , https://stackoverflow.com/a/53146559/4729755

免責事項 : Rfast::nth(as.numeric(1:10), 2)のように、as.numericを使用することで回避できる整数を扱った場合に問題が発生する可能性があり、Rfastの次のアップデートで対処予定です。

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

はxの5番目に大きい要素を返しますが

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

xの5番目に小さい要素を返します。

最も一般的な回答に対して、以下のベンチマークを行います。

1万個の数字に対して

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

1の場合 百万円 の数値になります。

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