C++ 매트릭스 제품 : 약간의 변경으로 속도 향상

Question

전체 매트릭스로 희소 행렬을 곱하는 코드를 작성하고 있습니다.

저는 SparseMatrix와 Matrix를 만들었습니다. SparseMatrix와 Matrix는 데이터를 벡터에 대한 공유 포인터의 벡터로 저장합니다. SparseMatrix의 경우 항목을 객체로 저장하고 SparseMatrixItem이라는 속성과 위치 및 값을 저장합니다. 매트릭스 경우에는 단순히 값을 저장합니다. bool 속성 값에 의해 행 기반 또는 열 기반이 될 수 있습니다.

이제 2 개의 매트릭스 사이에 효율적인 표준 버전의 제품을 작성하려고합니다. 첫 번째 구현에서 semplicity를 통해 첫 번째 행렬이 행 기반 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 매트릭스 : 6040x4000 및 4000 * 6040으로 테스트합니다. 첫 번째 구현은 거의 30 초가 걸렸지 만 두 번째 구현은 12 초 밖에 걸리지 않았습니다. 나는 그것을 게시 : 내가 MATLAB과 같은 제품을 시도하고 단지 1.5 초 더 많거나 적게 소요

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

: 나는 또한 기능 내가 사용 fastScalarProduct()의 코드를 게시

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

합니다. 나는 캐시 메모리에 문제가 있다고 생각하지만, 이런 종류의 문제에 익숙하지 않아서 나는 진짜 문제를 파악할 수 없다.

나는 효율적인 풀 매트릭스 제품을 작성하려고하는데, 나는 동일한 문제에 직면하고있다.

Answer 1

"문제"가 캐시 메모리라고 말하는 것이 옳습니다. 대부분의 반복이있는 루프가 반복이 적은 루프 내에있을 때 프로그램이 더 빨리 실행되는 이유를 설명하는 참조 위치 (http://en.wikipedia.org/wiki/Locality_of_reference)에 대해 읽으십시오. 기본적으로 배열은 선형 데이터 구조이며 공간 지역을 잘 활용합니다. 링크 된 위키 피 디아 문서의 핵심 문장의 일부를 인용하시기 바랍니다해야 Why is MATLAB so fast in matrix multiplication?