C++矩阵产品:只需少量更改即可提高速度

Question

我正在写一段代码，将一个稀疏矩阵与一个完整矩阵相乘。

我已经创建了两个类: SparseMatrix和Matrix，它们将数据存储为指向向量的共享指针的向量。在SparseMatrix示例中，我将item保存为一个名为SparseMatrixItem的对象，该对象具有两个属性:位置和值。在Matrix的情况下，我只是简单地保存该值。根据bool属性的值，它们都可以是基于行或列的。

现在我正试着在这两个矩阵之间写一个标准乘积的有效版本。在第一个实现中，我只考虑第一个矩阵是基于行的SparseMatrix和第二个是基于列的矩阵的情况。我通过重载操作符*将代码写入SparseMatrix类。

我发布了我的实现：

template <typename scalar>
Matrix<scalar> SparseVectorMatrix<scalar>::operator*(Matrix<scalar> &input2) {
    Matrix<scalar> newMatrix(getNumberOfRows(),input2.getNumberOfColumns(),true);
    int numberOfRow=newMatrix.getNumberOfRows();
    int numberOfColumn=newMatrix.getNumberOfColumns();

    for (int i=0; i<numberOfRow; i++) {
    vector<SparseMatrixItem<scalar>>& readRow(*horizontalVectorMatrix[i]);
    vector<scalar>& writeRow(*newMatrix.internalMatrix[i]);

        for (int j=0; j<numeroColonne; j++) {
            vector<scalar>& readColumn1(*input2.internalMatrix[j]);
            writeRow[j]=fastScalarProduct(readRow, readColumn1);

        }
    }
}

奇怪的是，我不能理解的是，如果我改变了2循环的顺序，性能会快得多。我用2个矩阵进行了测试: 6040x4000和4000*6040，第一个实现花了将近30秒，而第二个实现只花了12秒。我把它贴出来：

template <typename scalar>
Matrix<scalar> SparseVectorMatrix<scalar>::operator*(Matrix<scalar> &input2) {
    Matrix<scalar> newMatrix(getNumberOfRows(),input2.getNumberOfColumns(),true);
    int numberOfRow=newMatrix.getNumberOfRows();
    int numeroColonne=newMatrix.getNumberOfColumns();

    for (int j=0; j<numeroColonne; j++) {
        vector<scalar>& readColumn(*input2.internalMatrix[j]);
        vector<scalar>& writeColumn(*newMatrix.internalMatrix[j]);

        for (int i=0; i<numberOfRow; i++) {
            vector<SparseMatrixItem<scalar>>& readRow(*matriceOrizzontaleVettori[i]);
            writeColumn[i]=fastScalarProduct(readRow, readColumn);
        }
    }
}

我还发布了我使用的函数fastScalarProduct()的代码：

template <typename scalar>
scalar SparseVectorMatrix<scalar>::fastScalarProduct
    ( vector<SparseMatrixItem<scalar>> &vector1
    , const vector<scalar> &vector2
    ) {
    int totalSum=0;
    int position;
    auto sizeVector1=vector1.size();

    for (int i=0; i<sizeVector1; i++) {
        position=vector1[i].position-1;
        if (vector2[position]) {
            totalSum+=(vector1[i].value)*vector2[position];
        }
    }
    return totalSum;
}

我用MATLAB试了一下同样的产品，大概只需要1.5秒。我认为缓存存在问题，但由于我对这类问题还不熟悉，所以我找不到真正的问题所在。

我也在尝试写一个高效的全矩阵乘积，我也面临着同样的问题。

Answer 1

您说得对，“问题”出在缓存上。我建议你阅读引用局部性(http://en.wikipedia.org/wiki/Locality_of_reference)，它解释了为什么当迭代次数最多的循环在迭代次数较少的循环中时，程序运行得更快。基本上，数组是线性数据结构，它们充分利用了空间局部性。

至于在matlab vs C++中运行算法所花费的时间，我建议你阅读这篇文章：Why is MATLAB so fast in matrix multiplication?