犰狳的有效距离计算 [英] efficient distance calculations in armadillo

问题描述

我是犰狳的新手.我有以下代码，我认为这是效率低下的.有什么建议可以使其更高效和/或更快速地存储吗?遵循 armadillo文档和

I'm new to armadillo. I have the below code, which I assume is inefficient. Any suggestions to make it more memory efficient and/or speedy? Following the armadillo docs and Rcpp gallery, I was unable to get .colptr's, uvec's, or batch insertion to work. But I assume any of them would be improvements.

输入 X (〜100 x 30000)，即使我愚蠢的大型工作VM也崩溃了.

With an input of X (~100 x 30000), even my stupidly large work VM crashes.

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的余弦相似度.

Note: these are distances because I am calculating cosine similarities where I have set L2 norm == 1.

推荐答案

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

It looks to me as if you're just computing the (upper triangular) matrix product t(X)%*%X. You can actually do that directly in R with the underused crossprod function.

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

这在我的笔记本电脑上花费了几分钟.如果将代码更改为使用Armadillo库，则可以使用

This takes a few minutes on my laptop. If you change your code to use the Armadillo library then you can use

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;
}

仍然需要几分钟.尽管它占用了大量内存，所以我怀疑您可以同时在内存中存储很多对象.

Still takes a few minutes. It uses an awful amount of memory though so I doubt you can have a lot of objects in memory at the same time.

可以对代码进行优化，使其仅计算下/上三角矩阵.

The code could probably be optimized to only compute the lower/upper triangular matrix.

仅显示100 * 800矩阵的加速:

Just to show the speedup for a 100*800 matrix:

> 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 

如您所见，通过蛮力强制可以大大提高速度.话虽这么说，我确信交叉乘积可以进一步优化.

As you can see there is a substantial speedup to be gained by brute-forcing it. That being said I'm sure that the cross product can be optimised further.

这篇关于犰狳的有效距离计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！