La forma más rápida para ordenar cada fila de una matriz grande en I

Question

Tengo una gran matriz:

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

Quiero ordenar cada fila de la matriz:

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

Tengo un montón de RAM para trabajar, pero me gustaría una forma más rápida de realizar esta operación.

Answer 1

Bueno, no conozco muchas maneras de ordenar más rápido en R, y el problema es que solo está ordenando 300 valores, pero muchas veces. Aún así, puede EEK algo de rendimiento extra de clase llamando directamente sort.int y el uso de 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 

Pero una mejor manera debe ser utilizar el paquete paralelo para ordenar partes de la matriz en paralelo. Sin embargo, la sobrecarga de la transferencia de datos parece ser demasiado grande, y en mi máquina se inicia el canje ya que "sólo" tengo 8 GB de memoria:

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

Answer 2

El paquete grr contiene un método para ordenar alternativo que se puede utilizar para acelerar esta operación en particular (he reducido el tamaño de la matriz algo para que esta referencia no tienen en para siempre):

> 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 

la diferencia se vuelve dramática cuando la matriz contiene caracteres:

> 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 

Los resultados son idénticos para los tres.

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