performance - 快速功能通過名稱添加矢量元素



vector rcpp (4)

data.table包在執行聚合和其他操作方面非常出色。 我不是一個真正的專家,但是

library(data.table)
add_vectors5 <- function(...)
{
    vals <- do.call(c, list(...))
    dt <- data.table(nm=names(vals), v=vals, key="nm")
    dt <- dt[,sum(v), by=nm]
    setNames(dt[[2]], dt[[1]])
}

似乎比其他純R實現快兩倍。 更神秘的實現是

add_vectors6 <- function(..., method="radix")
{
    vals <- do.call(c, list(...))
    ## order by name, but use integers for faster order algo
    idx <- match(names(vals), unique(names(vals)))
    o <- sort.list(idx, method=method, na.last=NA)

    ## cummulative sum of ordered values
    csum <- cumsum(vals[o])

    ## subset where ordering factor changes, and then diff
    idxo <- idx[o]
    diff(c(0, csum[idxo != c(idxo[-1], TRUE)]))
}

容易出現數值溢出; 如果有少於100,000個名字,使用method =“radix”,如?sort.list ,否則method =“quick”。

我寫了這個R函數,給定任意數量的向量( ... )通過基於它們的名字對各個元素值進行求和來合併它們。

add_vectors <- function(...) {
  a <- list(...)
  nms <- sort(unique(unlist(lapply(a, names))))
  out <- numeric(length(nms))
  names(out) <- nms
  for (v in a) out[names(v)] <- out[names(v)] + v

  out
}

例:

v1 <- c(a=2,b=3,e=4)
v2 <- c(b=1,c=6,d=0,a=4)
add_vectors(v1, v2)
#
a b c d e 
6 4 6 0 4

我試圖寫一個相當快的功能。

不幸的是,現在我不知道如何在R實現這一點,所以我想Rcpp 。 但是,為了在Rcpp轉換這個功能,我錯過了一些概念:

  1. 如何管理...參數。 用RcppList類型的參數?
  2. 如何迭代...參數中的向量。
  3. 如何通過名稱訪問(然後求和)向量的元素(這在R是非常微不足道的,但是我不知道如何在Rcpp做)。

所以我正在尋找能夠幫助我改進這個功能的表現的人(在RRcpp ,或者兩者都有)。

任何幫助表示讚賞,謝謝。


使用編譯器軟件包編譯為字節碼可以提供一些改進。 這個軟件包附帶R.

library(compiler)
library(microbenchmark)

add_vectors_cmp <- cmpfun(add_vectors)

set.seed(1)
v <- rpois(length(letters), 10)
names(v) <- letters
vs <- replicate(150, v, simplify=FALSE)

not_compiled <- function(l) do.call(add_vectors, l)
compiled <- function(l) do.call(add_vectors_cmp, l)

plot(microbenchmark(not_compiled(vs), compiled(vs)))


我只是在Rcpp寫了一個這個函數的二進製版本(2個輸入)。

我不知道如何在Rcpp使用...參數(以及如何迭代它),所以我將這個函數封裝在一個簡單的R函數中。

library(Rcpp)
cppFunction(
  code = '
  NumericVector add_vectors_cpp(NumericVector v1, NumericVector v2) {
    // merging names, sorting them and removing duplicates
    std::vector<std::string> nms1 = v1.names();
    std::vector<std::string> nms2 = v2.names();
    std::vector<std::string> nms;
    nms.resize(nms1.size() + nms2.size());
    std::merge(nms1.begin(), nms1.end(), nms2.begin(), nms2.end(), nms.begin());
    std::sort(nms.begin(), nms.end());
    nms.erase(std::unique(nms.begin(), nms.end()), nms.end());
    // summing vector elements by their names and storing them in an associative data structure
    int num_names = nms.size();
    std::tr1::unordered_map<std::string, double> map(num_names);
    for (std::vector<int>::size_type i1 = 0; i1 != nms1.size(); i1++) {
        map[nms1[i1]] += v1[i1];
    }
    for (std::vector<int>::size_type i2 = 0; i2 != nms2.size(); i2++) {
        map[nms2[i2]] += v2[i2];
    }
    // extracting map values (to use as result vector) and keys (to use as result vector names)
    NumericVector vals(map.size());
    for (unsigned r = 0; r < num_names; ++r) {
        vals[r] = map[nms[r]];
    }
    vals.names() = nms;
    return vals;
  }',
  includes = '
  #include <vector>
  #include <tr1/unordered_map>
  #include <algorithm>'
)

然後封裝在一個R函數中:

add_vectors_2 <- function(...) {
  Reduce(function(x, y) add_vectors_cpp(x, y), list(...))
}

請注意,此解決方案使用STL庫。 我不知道這是一個寫得很好的C ++解決方案,還是可以編寫一個更有效的解決方案(可能),但肯定是一個好的(和工作的)起點。

使用示例

v1 <- c(b = 1, d = 2, c = 3, a = 4, e = 6, f = 5)
v2 <- c(d = 2, c = 3, a = 4, e = 6, f = 5)
add_vectors(v1, v2, v1, v2)
#  a  b  c  d  e  f 
# 16  2 12  8 24 20
add_vectors_2(v1, v2, v1, v2)
#  a  b  c  d  e  f 
# 16  2 12  8 24 20 

注意:這個函數也適用於哪些名稱不是唯一的矢量。

v1 <- c(b = 1, d = 2, c = 3, a = 4, e = 6, f = 5)
v2 <- c(d = 2, c = 3, a = 4, e = 6, f = 5, f = 10, a = 12)
add_vectors(v1, v2)
#  a  b  c  d  e  f 
# 16  1  6  4 12 15 
add_vectors_2(v1, v2)
#  a  b  c  d  e  f 
# 20  1  6  4 12 20

如最後一個例子所示,即使輸入向量具有非唯一名稱,該解決方案也可以工作,將相同名稱的同一向量的元素求和

基準

在最簡單的情況下,我的解決方案比R解決方案快兩倍(兩個向量)。 這是一個很好的結果,但是用一個更好的C++解決方案可能有進一步的小改進的餘地。

Unit: microseconds
                 expr    min     lq median      uq     max neval
  add_vectors(v1, v2) 65.460 68.569 70.913 73.5205 614.274   100
add_vectors_2(v1, v2) 20.743 23.389 25.142 26.9920 337.544   100

當把這個函數應用到更多的矢量時,性能會降低一點(只有2倍的速度)。

Unit: microseconds
                                 expr     min       lq  median       uq     max neval
  add_vectors(v1, v2, v1, v2, v1, v1) 105.994 195.7565 205.174 212.5745 993.756   100
add_vectors_2(v1, v2, v1, v2, v1, v1)  66.168 125.2110 135.060 139.7725 666.975   100

所以現在的最後一個目標是直接用Rcpp去除管理... (或類似的,例如List )參數的R 包裝函數。

我認為這是可能的,因為Rcpp糖具有類似於它的特徵(例如移植 sapply函數),但是會感激一些反饋。


我會用這樣的東西:

#include <Rcpp.h>
using namespace Rcpp; 

// [[Rcpp::export]]
NumericVector add_all(List vectors){
    RCPP_UNORDERED_MAP<std::string,double> out ; 
    int n = vectors.size() ;
    for( int i=0; i<n; i++){
        NumericVector x = vectors[i] ;
        CharacterVector names = x.attr("names") ;
        int m = x.size() ;

        for( int j=0; j<m; j++){
            String name = names[j] ;
            out[ name ] += x[j] ;   
        }
    }
    return wrap(out) ;
}

用下面的包裝:

add_vectors_cpp <- function(...){
    add_all( list(...) )
}

RCPP_UNORDERED_MAP只是一個typedef到unordered_map ,無論是在std::或在std::tr1::取決於你的編譯器等...

這裡的訣竅是使用經典list(...)創建一個常規列表。

如果你真的想直接傳遞...在C + +內部處理,你將不得不使用。外部接口。 這是很少使用的,所以Rcpp屬性不支持.External接口。

.External ,它會看起來像這樣(未經測試):

SEXP add_vectors(SEXP args){
    RCPP_UNORDERED_MAP<std::string,double> out ; 
    args = CDR(args) ;
    while( args != R_NilValue ){
        NumericVector x = CAR(args) ;

        CharacterVector names = x.attr("names") ;
        int m = x.size() ;

        for( int j=0; j<m; j++){
            String name = names[j] ;
            out[ name ] += x[j] ;   
        }        
        args = CDR(args) ;
    }   
    return wrap(out) ;
}




rcpp