c++ - C++ Matrix产品:几乎没有变化的速度提高了

我正在编写代码以将稀疏矩阵与完整矩阵相乘。

我创建了2类:SparseMatrix和Matrix，它们将数据存储为 vector 的共享指针的 vector 。在SparseMatrix的情况下，我将项目另存为一个名为SparseMatrixItem的对象，它具有2个属性:位置和值。在矩阵的情况下，我只是保存值。
通过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秒。我认为高速缓存存在一些问题，但是由于我是这种问题的新手，所以我无法弄清真正的问题。

我也在尝试编写一种高效的全矩阵产品，并且面临着同样的问题。

最佳答案

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

至于在matlab与C++中运行算法所花费的时间，我建议您阅读以下文章:Why is MATLAB so fast in matrix multiplication?