1

rowsumC++ / Rcpp / Eigen または Armadillo でR 関数の高速な代替手段を探しています。

a目的は、グループ化ベクトルに従ってベクトル内の要素の合計を取得することですb。例えば:

> a
 [1] 2 2 2 2 2 2 2 2 2 2    
> b
 [1] 1 1 1 1 1 2 2 2 2 2
> rowsum(a,b)
  [,1]
1   10
2   10

単純な for ループを記述するのRcppは非常に遅いですが、私のコードが非効率だったのかもしれません。

の関数も呼び出してみrowsumましたRcppが、rowsumあまり高速ではありません。

4

4 に答える 4

5

答えではありませんが、問題を組み立てるのに役立つかもしれません。最悪の場合のパフォーマンスは、多くの短いグループを合計することであり、これはベクトルのサイズに比例してスケーリングするようです

> n = 100000; x = runif(n); f = sample(n/2, n, TRUE)
> system.time(rowsum(x, f))
   user  system elapsed 
  0.228   0.000   0.229 
> n = 1000000; x = runif(n); f = sample(n/2, n, TRUE)
> system.time(rowsum(x, f)) 
   user  system elapsed 
  1.468   0.040   1.514 
> n = 10000000; x = runif(n); f = sample(n/2, n, TRUE)
> system.time(rowsum(x, f))
   user  system elapsed 
 17.369   0.748  18.166 

再注文を避けて、2つのショートカットが利用できるようです

> n = 10000000; x = runif(n); f = sample(n/2, n, TRUE)
> system.time(rowsum(x, f, reorder=FALSE))
   user  system elapsed 
 16.501   0.476  17.025 

キャラクターへの内的強制を避ける

> n = 10000000; x = runif(n); f = as.character(sample(n/2, n, TRUE)); 
> system.time(rowsum(x, f, reorder=FALSE))
   user  system elapsed 
  8.652   0.268   8.949 

そして、関連しているように見える基本的な操作-グループ化係数の一意の値を見つけ出し(結果ベクトルを事前に割り当てるため)、合計を実行します

> n = 10000000; x = runif(n); f = sample(n/2, n, TRUE)
> system.time({ t = tabulate(f); sum(x) })
   user  system elapsed 
  0.640   0.000   0.643 

そうです、より高速な単一目的の実装にはかなりの余地があるようです。これは自然な for のように思わdata.tableれ、C で実装するのはそれほど難しくありません。R を使用して集計を行い、「従来の」C インターフェイスを使用して合計を行う混合ソリューションを次に示します。

library(inline)

rowsum1.1 <- function(x, f) {
    t <- tabulate(f)
    crowsum1(x, f, t)
}

crowsum1 = cfunction(c(x_in="numeric", f_in="integer", t_in = "integer"), "
    SEXP res_out;
    double *x = REAL(x_in), *res;
    int len = Rf_length(x_in), *f = INTEGER(f_in);

    res_out = PROTECT(Rf_allocVector(REALSXP, Rf_length(t_in)));
    res = REAL(res_out);
    memset(res, 0, Rf_length(t_in) * sizeof(double));
    for (int i = 0; i < len; ++i)
        res[f[i] - 1] += x[i];
    UNPROTECT(1);
    return res_out;
")

> system.time(r1.1 <- rowsum1.1(x, f))
   user  system elapsed 
  1.276   0.092   1.373 

と同じ結果を実際に返すにはrowsum、これを適切な次元名を持つマトリックスとして形成する必要があります

rowsum1 <- function(x, f) {
    t <- tabulate(f)
    r <- crowsum1(x, f, t)
    keep <- which(t != 0)
    matrix(r[keep], ncol=1, dimnames=list(keep, NULL))
}

> system.time(r1 <- rowsum1(x, f))
   user  system elapsed 
  9.312   0.300   9.641

そのため、すべての作業で 2 倍の速さしかありません (そして、一般性ははるかに低くなります。x は数値でなければならず、f は整数でなければなりません。NA 値はありません)。はい、たとえば、カウントのないスペース レベルを割り当てるなどの非効率性があります (ただし、これにより、名前の文字ベクトルへの高価な強制が回避されます)。

于 2013-06-07T12:36:27.523 に答える
1

これを使用してこれを行う私の試みはRcpp次のとおりです(パッケージを初めて使用するため、私の非効率性を指摘してください):

library(inline)
library(Rcpp)

rowsum_helper = cxxfunction(signature(x = "numeric", y = "integer"), '
  NumericVector var(x);
  IntegerVector factor(y);

  std::vector<double> sum(*std::max_element(factor.begin(), factor.end()) + 1,
                          std::numeric_limits<double>::quiet_NaN());
  for (int i = 0, size = var.size(); i < size; ++i) {
    if (sum[factor[i]] != sum[factor[i]]) sum[factor[i]] = var[i];
    else sum[factor[i]] += var[i];
  }

  return NumericVector(sum.begin(), sum.end());
', plugin = "Rcpp")

rowsum_fast = function(x, y) {
  res = rowsum_helper(x, y)
  elements = which(!is.nan(res))
  list(elements - 1, res[elements])
}

Martin のサンプル データではかなり高速ですが、因子が非負の整数で構成され、因子ベクトルの最大の整数のオーダーでメモリを消費する場合にのみ機能します (上記の明らかな改善点の 1 つは、最大から最小を減算することです)。メモリ使用量を減らします - これは R 関数または C++ 関数のいずれかで実行できます)。

n = 1e7; x = runif(n); f = sample(n/2, n, T)

system.time(rowsum(x,f))
#    user  system elapsed 
#   14.241  0.170  14.412

system.time({tabulate(f); sum(x)})
#    user  system elapsed 
#   0.216   0.027   0.252

system.time(rowsum_fast(x,f))
#    user  system elapsed 
#   0.313   0.045   0.358

また、( と比較してtabulate) 多くの速度低下が R コードで発生することにも注意してください。そのため、代わりに C++ に移動すると、さらに改善が見られるはずです。

system.time(rowsum_helper(x,f))
#    user  system elapsed 
#   0.210   0.018   0.228

ほとんどすべての を処理する一般化を次に示しyますが、少し遅くなります (実際には Rcpp でこれを行うことを好みますが、そこで任意の R 型を処理する方法がわかりません)。

rowsum_fast = function(x, y) {
  if (is.numeric(y)) {
    y.min = min(y)
    y = y - y.min
    res = rowsum_helper(x, y)
  } else {
    y = as.factor(y)
    res = rowsum_helper(x, as.numeric(y))
  }

  elements = which(!is.nan(res))

  if (is.factor(y)) {
    list(levels(y)[elements-1], res[elements])
  } else {
    list(elements - 1 + y.min, res[elements])
  }
}
于 2013-06-07T18:09:57.137 に答える