modo più veloce per ordinare ciascuna riga di una grande matrice R

Question

Ho una grande matrice:

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

voglio ordinare ciascuna riga della matrice:

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

ho un sacco di RAM con cui lavorare, ma mi piacerebbe un modo più veloce per eseguire questa operazione.

Answer 1

Bene, non sono a conoscenza di molti modi per ordinare più velocemente in R, e il problema è che si stanno solo ordinando 300 valori, ma molte volte. Ancora, è possibile EEK alcune prestazioni fuori sorta chiamando direttamente sort.int e utilizzando 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 

Ma un modo migliore dovrebbe essere quello di utilizzare il pacchetto in parallelo per ordinare parti della matrice in parallelo. Tuttavia, il sovraccarico di trasferimento dei dati sembra essere troppo grande, e sulla mia macchina inizia scambiando dato che "solo" ho 8 GB memoria:

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

Answer 2

Il pacchetto grr contiene un metodo di ordinamento alternativo che può essere utilizzato per velocizzare questa particolare operazione (ho ridotto la dimensione della matrice leggermente in modo che questo riferimento non tiene sempre):

> 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 differenza diventa drammatica quando la matrice contiene caratteri:

> 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 

I risultati sono identici per tutti e tre.

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