犰狳中的有效距离计算

Question

我是犰狳的新手。我有以下代码，我认为它效率低下。有什么建议可以提高内存效率and/or 速度吗？在 armadillo docs and Rcpp gallery 之后，我无法让 .colptr、uvec 或批量插入工作。但我认为其中任何一个都会有所改进。

输入 X (~100 x 30000)，即使是我那愚蠢的大型工作 VM 也会崩溃。

Linux release 7.3.1611 (Core)
117GB RAM / 0GB SWAP
(24 x 2.494 GHz) processor(s)

R version 3.3.2 (2016-10-31)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: CentOS Linux 7 (Core)

代码

#include <RcppArmadillo.h>
// [[Rcpp::depends(RcppArmadillo)]]

using namespace Rcpp;
using namespace arma;

// [[Rcpp::export]]
sp_mat arma_distmat_LT(const arma::mat& x) { // input expected X_{n x p} n << p
  int nr, nc;
  Col<double> col0, col1;

  nr = x.n_rows;
  nc = x.n_cols;

  sp_mat out(nc, nc);
  for (int i = 0; i < nc; i++) {
    col0 = x.col(i);
    for (int j = i + 1; j < nc; j++) {
      col1 = x.col(j);
      out(j, i) = as_scalar(col0.t() * col1);
    }
  }
  return out;
}

通话：sourceCpp("<file>"); dist_x <- arma_distmat_LT(X)

注意：这些是距离，因为我正在计算余弦相似度，其中我设置了 L2 范数 == 1。

Answer 1

在我看来，您好像只是在计算（上三角）矩阵乘积 t(X)%*%X。实际上，您可以直接在 R 中使用未充分利用的 crossprod 函数来执行此操作。

X <- matrix(rnorm(100*30000), ncol=30000)
res <- crossprod(X, X)

这在我的笔记本电脑上需要几分钟时间。如果您更改代码以使用 Armadillo 库，那么您可以使用

sp_mat arma_distmat_LT2(const arma::mat& x) { // input expected X_{n x p} n << p                               
  int nr, nc;
  Col<double> col0, col1;

  nr = x.n_rows;
  nc = x.n_cols;

  sp_mat out(nc, nc);
  out = trimatl(x.t() * x, k=-1);
  return out;
}

还需要几分钟。它使用了大量的内存，所以我怀疑你可以同时在内存中有很多对象。

代码可以优化为仅计算 lower/upper 三角矩阵。

只是为了显示 100*800 矩阵的加速：

> microbenchmark(crossprod(X, X), arma_distmat_LT(X), arma_distmat_LT2(X))
Unit: milliseconds
                expr        min         lq       mean     median         uq
     crossprod(X, X)   50.25574   53.72049   57.98812   56.29532   58.71277
  arma_distmat_LT(X) 1331.83243 1471.42465 1523.74060 1492.84611 1512.45416
 arma_distmat_LT2(X)   29.69420   33.23954   36.24613   35.54700   38.05208
        max neval cld
  160.81227   100  a 
 3080.37891   100   b
   66.07351   100  a

如您所见，通过暴力破解可以显着提高速度。话虽如此，我确信叉积可以进一步优化。

犰狳中的有效距离计算

efficient distance calculations in armadillo

c++

r

armadillo

rcpp

代码