Tốc độ lên máy tính trung bình hàng khôn ngoan của mỗi 3-tuple của cột

Question

Nếu tôi có một khung dữ liệu như vậy:

df = data.frame(matrix(rnorm(100), 5000, 100)) 

tôi có thể sử dụng chức năng sau đây để nhận được tất cả sự kết hợp của hàng trung vị ba hạn -wise:

median_df = t(apply(df, 1, combn, 3, median)) 

Vấn đề là, chức năng này sẽ mất vài giờ để chạy. Thủ phạm là trung bình(), mất khoảng 10 lần để chạy so với max() hoặc min().

Làm cách nào để tăng tốc chức năng này, có thể bằng cách viết phiên bản trung bình nhanh hơn() hoặc làm việc với dữ liệu gốc khác nhau?

Cập nhật:

Nếu tôi chạy đoạn mã trên nhưng chỉ cho df [, 1: 10] như vậy:

median_df = t(apply(df[,1:10], 1, combn, 3, median)) 

mất 29 giây

fastMedian_df = t(apply(df[,1:10], 1, combn, 3, fastMedian)) 

từ gói ccaPP mất 6,5 giây

max_df = t(apply(df[,1:10], 1, combn, 3, max)) 

mất 2,5 giây

Vì vậy, chúng tôi thấy sự cải thiện đáng kể với fastMedian(). Chúng ta có thể làm tốt hơn không?

Answer 1

Một cách tiếp cận để tăng tốc mọi thứ sẽ là lưu ý rằng trung bình của ba số là tổng của chúng trừ đi giá trị cực đại trừ phút tối thiểu của chúng. Điều này có nghĩa là chúng ta có thể vector hóa tính toán trung bình của chúng tôi bằng cách xử lý mỗi ba cột một lần (thực hiện trung vị cho tất cả các hàng trong cùng một phép tính) thay vì xử lý nó một lần cho mỗi hàng.

set.seed(144) 
# Fully random matrix 
df = matrix(rnorm(50000), 5000, 10) 
original <- function(df) t(apply(df, 1, combn, 3, median)) 
josilber <- function(df) { 
    combos <- combn(seq_len(ncol(df)), 3) 
    apply(combos, 2, function(x) rowSums(df[,x]) - pmin(df[,x[1]], df[,x[2]], df[,x[3]]) - pmax(df[,x[1]], df[,x[2]], df[,x[3]])) 
} 
system.time(res.josilber <- josilber(df)) 
# user system elapsed 
# 0.117 0.009 0.149 
system.time(res.original <- original(df)) 
# user system elapsed 
# 15.107 1.864 16.960 
all.equal(res.josilber, res.original) 
# [1] TRUE 

Vectorization mang lại tốc độ 110x khi có 10 cột và 5000 hàng. Thật không may, tôi không có một máy có đủ bộ nhớ để lưu trữ 808,5 triệu con số trong đầu ra cho ví dụ đầy đủ của bạn. Bạn có thể tăng tốc độ này bằng cách thực hiện một hàm Rcpp lấy làm đầu vào biểu diễn vector của ma trận (còn gọi là véc tơ thu được bằng cách đọc ma trận xuống các cột) cùng với số hàng và trả về giá trị trung bình của mỗi cột. Hàm dựa rất nhiều vào hàm std::nth_element, hàm này tuyến tính theo số lượng các phần tử bạn đang dùng trung bình. (Lưu ý rằng tôi không trung bình giữa hai giá trị khi tôi lấy trung bình của một vectơ có độ dài bằng nhau; thay vào đó tôi lấy giá trị trung bình của hai giá trị này).

library(Rcpp) 
cppFunction(
"NumericVector vectorizedMedian(NumericVector x, int chunkSize) { 
const int n = x.size()/chunkSize; 
std::vector<double> input = Rcpp::as<std::vector<double> >(x); 
    NumericVector res(n); 
    for (int i=0; i < n; ++i) { 
    std::nth_element(input.begin()+i*chunkSize, input.begin()+i*chunkSize+chunkSize/2, 
        input.begin()+(i+1)*chunkSize); 
    res[i] = input[i*chunkSize+chunkSize/2]; 
    } 
    return res; 
}") 

Bây giờ chúng ta chỉ cần gọi chức năng này thay vì sử dụng rowSums, pmin và pmax:

josilber.rcpp <- function(df) { 
    combos <- combn(seq_len(ncol(df)), 3) 
    apply(combos, 2, function(x) vectorizedMedian(as.vector(t(df[,x])), 3)) 
} 
system.time(josilber.rcpp(df)) 
# user system elapsed 
# 0.049 0.008 0.081 
all.equal(josilber(df), josilber.rcpp(df)) 
# [1] TRUE 

Trong tổng số do đó chúng tôi có được một tăng tốc 210x; 110x của quá trình tăng tốc là từ việc chuyển đổi từ ứng dụng không được vector hóa là median sang ứng dụng được vector hóa và tăng tốc 2x còn lại là từ việc chuyển đổi từ sự kết hợp của rowSums, pmin và pmax để tính trung bình theo cách được vector hóa theo Rcpp tiếp cận.