Самый быстрый способ сортировки каждой строки большой матрицы в R

Question

У меня большая матрица:

set.seed(1)
a <- matrix(runif(9e+07),ncol=300)

Я хочу отсортировать каждую строку в матрице:

> system.time(sorted <- t(apply(a,1,sort)))
   user  system elapsed 
  42.48    3.40   45.88 

У меня много оперативной памяти, но я хотел бы ускорить выполнение этой операции.

Answer 1

Ну, я не знаю, сколько способов сортировать быстрее в R, и проблема в том, что вы сортируете только 300 значений, но много раз. Тем не менее, вы можете получить дополнительную производительность вне очереди, напрямую позвонив sort.int и используя method='quick':

set.seed(1)
a <- matrix(runif(9e+07),ncol=300)

# Your original code
system.time(sorted <- t(apply(a,1,sort))) # 31 secs

# sort.int with method='quick'
system.time(sorted2 <- t(apply(a,1,sort.int, method='quick'))) # 27 secs

# using a for-loop is slightly faster than apply (and avoids transpose):
system.time({sorted3 <- a; for(i in seq_len(nrow(a))) sorted3[i,] <- sort.int(a[i,], method='quick') }) # 26 secs

Но лучше использовать параллельный пакет для параллельной сортировки частей матрицы. Однако накладные расходы на передачу данных кажутся слишком большими, и на моей машине он начинает меняться, поскольку у меня «только» 8 ГБ памяти:

library(parallel)
cl <- makeCluster(4)
system.time(sorted4 <- t(parApply(cl,a,1,sort.int, method='quick'))) # Forever...
stopCluster(cl)

Answer 2

Пакет grr содержит альтернативный метод сортировки, который можно использовать для ускорения этой конкретной операции (я несколько уменьшил размер матрицы, чтобы этот тест не длился вечно):

> set.seed(1)
> a <- matrix(runif(9e+06),ncol=300)
> microbenchmark::microbenchmark(sorted <- t(apply(a,1,sort))
+                                ,sorted2 <- t(apply(a,1,sort.int, method='quick'))
+                                ,sorted3 <- t(apply(a,1,grr::sort2)),times=3,unit='s')
Unit: seconds
                                                  expr       min       lq     mean   median       uq      max neval
                        sorted <- t(apply(a, 1, sort)) 1.7699799 1.865829 1.961853 1.961678 2.057790 2.153902     3
 sorted2 <- t(apply(a, 1, sort.int, method = "quick")) 1.6162934 1.619922 1.694914 1.623551 1.734224 1.844898     3
                 sorted3 <- t(apply(a, 1, grr::sort2)) 0.9316073 1.003978 1.050569 1.076348 1.110049 1.143750     3

Разница становится существенной, когда матрица содержит символы:

> set.seed(1)
> a <- matrix(sample(letters,size = 9e6,replace = TRUE),ncol=300)
> microbenchmark::microbenchmark(sorted <- t(apply(a,1,sort))
+                                ,sorted2 <- t(apply(a,1,sort.int, method='quick'))
+                                ,sorted3 <- t(apply(a,1,grr::sort2)),times=3)
Unit: seconds
                                                  expr       min        lq      mean    median        uq      max neval
                        sorted <- t(apply(a, 1, sort)) 15.436045 15.479742 15.552009 15.523440 15.609991 15.69654     3
 sorted2 <- t(apply(a, 1, sort.int, method = "quick")) 15.099618 15.340577 15.447823 15.581536 15.621925 15.66231     3
                 sorted3 <- t(apply(a, 1, grr::sort2))  1.728663  1.733756  1.780737  1.738848  1.806774  1.87470     3

Результаты идентичны для всех трех.

> identical(sorted,sorted2,sorted3)
[1] TRUE