Thực hiện tổng tích luỹ nhanh hơn

Question

Tôi đang cố gắng lấy tổng tích lũy cho mỗi cột của ma trận. Dưới đây là mã của tôi trong R:

testMatrix = matrix(1:65536, ncol=256); 
microbenchmark(apply(testMatrix, 2, cumsum), times=100L); 

Unit: milliseconds 
         expr  min  lq  mean median  uq  max neval 
apply(testMatrix, 2, cumsum) 1.599051 1.766112 2.329932 2.15326 2.221538 93.84911 10000 

tôi đã sử dụng Rcpp để so sánh:

cppFunction('NumericMatrix apply_cumsum_col(NumericMatrix m) { 
    for (int j = 0; j < m.ncol(); ++j) { 
     for (int i = 1; i < m.nrow(); ++i) { 
      m(i, j) += m(i - 1, j); 
     } 
    } 
    return m; 
}'); 
microbenchmark(apply_cumsum_col(testMatrix), times=10000L); 

Unit: microseconds 
         expr  min  lq  mean median  uq  max neval 
apply_cumsum_col(testMatrix) 205.833 257.719 309.9949 265.986 276.534 96398.93 10000 

Vì vậy, cáC++ mã C là 7,5 lần càng nhanh. Có thể làm tốt hơn apply(testMatrix, 2, cumsum) trong R thuần túy không? Nó cảm thấy như tôi có một thứ tự của cường độ trên không vì lý do nào.

Answer 1

Sử dụng byte được biên dịch cho vòng lặp nhanh hơn một chút so với cuộc gọi apply trên hệ thống của tôi. Tôi mong đợi nó sẽ nhanh hơn vì nó ít hoạt động hơn apply. Như mong đợi, vòng lặp R vẫn chậm hơn hàm C++ đơn giản mà bạn đã viết.

colCumsum <- compiler::cmpfun(function(x) { 
    for (i in 1:ncol(x)) 
    x[,i] <- cumsum(x[,i]) 
    x 
}) 

testMatrix <- matrix(1:65536, ncol=256) 
m <- testMatrix 
require(microbenchmark) 
microbenchmark(colCumsum(m), apply_cumsum_col(m), apply(m, 2, cumsum), times=100L) 
# Unit: microseconds 
#     expr  min  lq median  uq  max neval 
#  matrixCumsum(m) 1478.671 1540.5945 1586.1185 2199.9530 37377.114 100 
# apply_cumsum_col(m) 178.214 192.4375 204.3905 234.8245 1616.030 100 
# apply(m, 2, cumsum) 1879.850 1940.1615 1991.3125 2745.8975 4346.802 100 
all.equal(colCumsum(m), apply(m, 2, cumsum)) 
# [1] TRUE 

Answer 2

Rất khó để đánh bại C++ chỉ với mã R. Cách nhanh nhất mà tôi có thể nghĩ đến là thực hiện nếu bạn sẵn sàng chia ma trận của mình thành một danh sách. Bằng cách đó, R đang sử dụng các hàm nguyên thủy và không sao chép đối tượng với mỗi lần lặp lại (apply về cơ bản là một vòng lặp khá). Bạn có thể thấy rằng C++ vẫn thắng nhưng có một tốc độ đáng kể với cách tiếp cận list nếu bạn thực sự chỉ muốn sử dụng mã R.

fun1 <- function(){ 
    apply(testMatrix, 2, cumsum) 
} 

testList <- split(testMatrix, col(testMatrix)) 

fun2 <- function(){ 
    lapply(testList, cumsum) 
} 

microbenchmark(fun1(), 
       fun2(), 
       apply_cumsum_col(testMatrix), 
       times=100L) 


Unit: microseconds 
         expr  min  lq  mean median  uq  max neval 
         fun1() 3298.534 3411.9910 4376.4544 3477.608 3699.2485 9249.919 100 
         fun2() 558.800 596.0605 766.2377 630.841 659.3015 5153.100 100 
apply_cumsum_col(testMatrix) 219.651 282.8570 576.9958 311.562 339.5680 4915.290 100 

EDIT Xin lưu ý rằng phương pháp này là chậm hơn so với fun1 nếu bạn bao gồm thời gian để chia ma trận vào một danh sách.