Rcpp本征稀疏矩阵绑定

Question

我正在Rcpp（Eigen）中开发一种算法，该算法要求矩阵使用cbind。我发现R的绑定速度非常快，而使用Eigen的速度非常慢。我想找到一种优化此功能的方法，以便将算法保留在Rcpp中。到目前为止，我已经找到了另一个链接，但是它适用于密集矩阵上的cbind

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

using namespace Rcpp;
using namespace Eigen;

// [[Rcpp::export]]
Eigen::SparseMatrix<double> RcppMatrixCbind(Eigen::MappedSparseMatrix<double>& matrix1,
                                            Eigen::MappedSparseMatrix<double>& matrix2) {

  SparseMatrix<double> out(matrix1.rows(), matrix1.cols() + matrix2.cols());
  std::vector<Triplet<double> > tripletList;
  tripletList.reserve(matrix1.nonZeros() + matrix2.nonZeros());
  for (int k = 0; k < matrix1.outerSize(); ++k)
  {
    for (MappedSparseMatrix<double>::InnerIterator it(matrix1, k); it; ++it)
    {
      tripletList.push_back(Triplet<double>(it.row(), it.col(), it.value()));
    }
  }
  for (int k = 0; k < matrix2.outerSize(); ++k)
  {
    for (MappedSparseMatrix<double>::InnerIterator it(matrix2, k); it; ++it)
    {
      tripletList.push_back(Triplet<double>(it.row(), it.col() + matrix1.cols(), it.value()));
    }
  }
  out.setFromTriplets(tripletList.begin(), tripletList.end());
  return out;
}

/*** R
require(Matrix)
x = rsparsematrix(10000, 500, .1)
system.time(foo <- cbind(x,x))
system.time(bar <- RcppMatrixCbind(x, x))
  */

Answer 1

这实际上更多地是一个本征问题：如何扩展稀疏矩阵？

您在解决方案中所做的就是逐元素进行所有操作，而且专用的逐块操作可能会胜过它。我们从Matrix解决方案中看到的是高效的代码，大概来自CHOLMD。

我快速浏览了Eigen文档。它警告：

关于读取访问，稀疏矩阵公开的API与稠密矩阵访问块，列和行等子矩阵的API相同。有关详细介绍，请参见阻止操作。但是，出于性能方面的考虑，写入子稀疏矩阵的限制更加有限，并且当前只有列大（respon。row-major）SparseMatrix的连续列（列）可写。此外，必须在编译时知道此信息，而忽略诸如block(...)和的方法corner*(...)。

但是我们很幸运，也很幸运cbind()。那么一个非常简单的解决方案是

// [[Rcpp::export]]
Eigen::SparseMatrix<double>
RcppMatrixCb2(Eigen::MappedSparseMatrix<double>& matrix1,
              Eigen::MappedSparseMatrix<double>& matrix2) {

  SparseMatrix<double> out(matrix1.rows(), matrix1.cols() + matrix2.cols());

  out.leftCols(matrix1.cols()) = matrix1; 
  out.rightCols(matrix2.cols()) = matrix2; 
  return out;
}

击败了之前的两次尝试：

> benchmark(Matrix=cbind(x,x), 
+           prevSol=RcppMatrixCbind(x,x), 
+           newSol=RcppMatrixCb2(x,x),
+           order="relative")[,1:4]
     test replications elapsed relative
3  newSol          100   0.585    1.000
1  Matrix          100   0.686    1.173
2 prevSol          100   4.603    7.868
> 

我的完整文件如下。它在两个功能上都缺乏测试：我们需要确保矩阵一和二具有相同的行。

// cf /sf/ask/3211296791/

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

using namespace Rcpp;
using namespace Eigen;

// [[Rcpp::export]]
Eigen::SparseMatrix<double> RcppMatrixCbind(Eigen::MappedSparseMatrix<double>& matrix1,
                                            Eigen::MappedSparseMatrix<double>& matrix2) {

  SparseMatrix<double> out(matrix1.rows(), matrix1.cols() + matrix2.cols());
  std::vector<Triplet<double> > tripletList;
  tripletList.reserve(matrix1.nonZeros() + matrix2.nonZeros());
  for (int k = 0; k < matrix1.outerSize(); ++k) {
    for (MappedSparseMatrix<double>::InnerIterator it(matrix1, k); it; ++it) {
      tripletList.push_back(Triplet<double>(it.row(), it.col(), it.value()));
    }
  }
  for (int k = 0; k < matrix2.outerSize(); ++k) {
    for (MappedSparseMatrix<double>::InnerIterator it(matrix2, k); it; ++it) {
      tripletList.push_back(Triplet<double>(it.row(), it.col() + matrix1.cols(), it.value()));
    }
  }
  out.setFromTriplets(tripletList.begin(), tripletList.end());
  return out;
}

// [[Rcpp::export]]
Eigen::SparseMatrix<double> RcppMatrixCb2(Eigen::MappedSparseMatrix<double>& matrix1,
                                          Eigen::MappedSparseMatrix<double>& matrix2) {

  SparseMatrix<double> out(matrix1.rows(), matrix1.cols() + matrix2.cols());

  out.leftCols(matrix1.cols()) = matrix1; 
  out.rightCols(matrix2.cols()) = matrix2; 
  return out;
}


/*** R
require(Matrix)
set.seed(42)
x = rsparsematrix(10000, 500, .1)
library(rbenchmark)
benchmark(Matrix=cbind(x,x), 
          prevSol=RcppMatrixCbind(x,x), 
          newSol=RcppMatrixCb2(x,x),
          order="relative")[,1:4]
*/