Как быстро найти индекс столбца для верхних n значений матрицы?

Question

Если задана матрица, скажем m, существует ли какой-либо прямой метод для нахождения верхних k значений m, а затем найдите именно тот столбец/строку, к которому они принадлежат. Я не мог найти что-либо на SO и, следовательно, поставил этот вопрос. Моя попытка на вышесказанном было это:

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 < < длина (м). Существуют ли эффективные способы для большой матрицы м, а также есть ли методы, которые могли бы помочь мне с дублирует в сценариях, как, когда один хочет, чтобы получить Top K имена столбцов

Например: с matrix 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

Answer 1

Вот сравнение подхода ФПА, в @ предложении Баркера заменить функциональность частичной сортировки АиРа и способ использования quantile:

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

который дает

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 

Я вынула округление OP для этого примера. Тонкая настройка параметров n и k может привести к разному ранжированию подходов. Мой предпочтительный способ: setDT(melt(m))[order(value, partial = 1:k)], но похоже, что он еще не доступен в R.