Cách nhanh nhất để sắp xếp mỗi hàng của một ma trận lớn trong R

Question

Tôi có một ma trận lớn:

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

Tôi muốn sắp xếp mỗi hàng trong ma trận:

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

tôi có rất nhiều RAM để làm việc với, nhưng tôi muốn một cách nhanh hơn để thực hiện thao tác này.

Answer 1

Vâng, tôi không biết nhiều cách sắp xếp nhanh hơn trong R và vấn đề là bạn chỉ phân loại 300 giá trị, nhưng nhiều lần. Tuy nhiên, bạn có thể eek một số hiệu suất thêm ra của loại bằng cách trực tiếp gọi sort.int và sử dụng 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 

Nhưng một cách tốt hơn nên sử dụng gói song song để sắp xếp các bộ phận của ma trận song song. Tuy nhiên, chi phí truyền dữ liệu có vẻ là quá lớn, và trên máy tính của tôi nó bắt đầu trao đổi kể từ khi tôi "chỉ" có 8 GB bộ nhớ:

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

Answer 2

Gói grr chứa một cách sắp xếp xen kẽ có thể được sử dụng để đẩy mạnh hoạt động đặc biệt này (tôi đã làm giảm kích thước ma trận phần nào để chuẩn này không mất mãi mãi):

> 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 

sự khác biệt trở nên kịch tính khi ma trận chứa các ký tự:

> 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 

Kết quả giống nhau cho cả ba.

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