マトリックスのトップn値のカラムインデックスを効率的に見つける方法は？

Question

行列mが与えられれば、mの上位kの値を見つけ、それらが属する列/行を正確に見つける直接的な方法があります。私はSO上に何も見つからなかったので、この質問をしました。私はこれが原因で、私は行列の全体の値をソートするのではなく、それらのk値を拾っていた理由で効率的であるかどうかわからないのです

set.seed(1729) 
k=5 #top 5 
m = matrix(round(runif(30),digits = 2),nr=10) 
idx <- which(matrix(m %in% head(sort(m), k), nr = nrow(m)), arr.ind = TRUE) 
print(m) 
     [,1] [,2] [,3] 
[1,] 0.59 0.54 0.57 
[2,] 0.44 0.43 0.32 
[3,] 0.57 0.08 0.29 
[4,] 0.35 0.58 0.24 
[5,] 0.86 0.52 0.53 
[6,] 0.41 0.78 0.17 
[7,] 0.51 0.47 0.26 
[8,] 0.15 0.81 0.49 
[9,] 0.85 0.64 0.64 
[10,] 1.00 0.78 0.95 

print(idx) 

     row col 
[1,] 8 1 
[2,] 3 2 
[3,] 4 3 
[4,] 6 3 
[5,] 7 3 

： 上記の私の試みはこれをされています。私はk < <の長さ（m）と仮定したいと思います。 は1つが上位k個の列名

例えば

を取得したいときのようなシナリオでを複製で私を助けることができる任意の方法があるにも大行列mのための任意の効率的な方法があります、と：で行列のmm、私は最小値を持つ上位2列を識別する必要があります。ここで、次のケースでは、列1と列2を期待しています。

mm = matrix(c(6,6,7,8,7,9,8,8,9), 3) 
print(mm) 
    [,1] [,2] [,3] 
[1,] 6 8 8 
[2,] 6 7 8 
[3,] 7 9 9 
idx <- which(matrix(mm %in% head(sort(mm), 2), nr = nrow(mm)), arr.ind = TRUE) 
print(idx) 
     row col 
[1,] 1 1 
[2,] 2 1 

ただし、ここでは1つの列しか取得できません。 1、この場合、出力は最小値を有する2つの異なる列でなければならない。 1と2

Answer 1

ここでRの部分ソート機能とquantileを使った方法で置換するバーカーの提案@、OPのアプローチの比較です：

私が出した

Unit: milliseconds 
expr  min  lq  mean median  uq  max neval cld 
    idx 145.01260 148.10571 155.27124 149.97761 152.45523 206.27179 30 d 
    dtq 30.05910 33.11280 44.83088 35.02334 37.78721 90.92545 30 b 
idxp 114.69501 118.23185 127.37992 119.50131 121.33241 175.41117 30 c 
idxq 13.02406 14.47907 22.81266 16.41707 18.28308 68.53364 30 a 

を与える

# example data 
set.seed(1729) 
n = 1e6 
k = 50 
m = matrix(runif(n), nr=10) 

# illustration of the quantile way 
which(m <= quantile(m, k/length(m)), arr.ind = TRUE) 
# or... 
library(data.table) 
setDT(melt(m))[ value <= quantile(value, k/.N) ] 
# Var1 Var2  value 
# 1: 8 4945 1.471722e-06 
# 2: 1 7025 1.856475e-05 
# 3: 9 7480 4.518987e-05 
# 4: 10 8378 1.877453e-05 
# 5: 2 9043 3.262958e-05 
# 6: 7 9925 1.327880e-05 
# 7: 5 13571 5.097035e-05 
# ... 

# benchmark 
microbenchmark::microbenchmark(times = 30, 
    idx = idx <- which(matrix(m %in% head(sort(m), k), nr = nrow(m)), arr.ind = TRUE), 
    dtq = dtq <- setDT(melt(m))[ value <= quantile(value, k/.N) ], 
    idxp = idxp <- which(matrix(m %in% head(sort(m, partial = 1:k), k), nr = nrow(m)), arr.ind = TRUE), 
    idxq = idxq <- which(m <= quantile(m, k/length(m)), arr.ind = TRUE) 
) 

# verifying, requires data.table 1.9.7+ 
fsetequal(as.data.table(idx), dtq[, .(row = Var1, col = Var2)]) 
fsetequal(as.data.table(idxp), dtq[, .(row = Var1, col = Var2)]) 
fsetequal(as.data.table(idxq), dtq[, .(row = Var1, col = Var2)]) 

この例のOPの丸め。パラメータnとkを調整すると、アプローチの順位が異なる可能性があります。私の好みの方法はsetDT(melt(m))[order(value, partial = 1:k)]ですが、Rでまだ利用できないようです。