# 稀疏矩陣表示| 系列 3（CSR） > 原文： [https://www.geeksforgeeks.org/sparse-matrix-representations-set-3-csr/](https://www.geeksforgeeks.org/sparse-matrix-representations-set-3-csr/) 如果矩陣中的大多數元素為零，則該矩陣稱為稀疏矩陣。 將零元素存儲在矩陣中非常浪費，因為它們不會影響我們的計算結果。 這就是為什么我們以比標準 2D 數組更有效的表示形式實現這些矩陣的原因。 使用更有效的表示，我們可以顯著減少操作的空間和時間復雜性。 我們在以下文章中討論了 4 種不同的表示形式： 1. [稀疏矩陣表示| 系列 1](https://www.geeksforgeeks.org/sparse-matrix-representation/) 2. [稀疏矩陣表示| 系列 2](https://www.geeksforgeeks.org/sparse-matrix-representations-using-list-lists-dictionary-keys/) 。 在本文中，我們將討論稀疏矩陣的另一種表示形式，通常稱為耶魯格式。 [CSR（壓縮稀疏行）或耶魯格式](https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR, _CRS_or_Yale_format))與稀疏矩陣的數組表示（在組 1 中討論）相似。 我們用三個一維數組或稱為 A，IA，JA 的向量表示矩陣 M（m * n）。 令 **NNZ** 表示 M 中非零元素的數量，并注意使用基于 0 的索引。 * A 向量的大小為 NNZ，它存儲矩陣的非零元素的值。 值以逐行遍歷矩陣的順序顯示 * 大小為 m + 1 的 IA 向量存儲直到（不包括）第 i 行的非零元素的累積數量。 它由遞歸關系定義： * IA [0] = 0 * IA [i] = IA [i-1] +矩陣第（i-1）行中的非零元素個數 * JA 向量將每個元素的列索引存儲在 A 向量中。 因此，它的大小也為 NNZ。 要找到第 i 行中非零元素的數量，我們執行 IA [i + 1] – IA [i]。 請注意，此表示形式與基于數組的實現有何不同，在后者中，第二個矢量存儲非零元素的行索引。 以下示例顯示了如何表示這些矩陣。 例子： ``` Input : 0 0 0 0 5 8 0 0 0 0 3 0 0 6 0 0 Solution: When the matrix is read row by row, the A vector is [ 5 8 3 6] The JA vector stores column indices of elements in A hence, JA = [ 0 1 2 1]. IA[0] = 0\. IA[1] = IA[0] + no of non-zero elements in row 0 i.e 0 + 0 = 0. Similarly, IA[2] = IA[1] + 2 = 2 IA[3] = IA[2] + 1 = 3 IA[4] = IA[3]+1 = 4 Therefore IA = [0 0 2 3 4] The trick is remember that IA[i] stores NNZ upto and not-including i row. Input : 10 20 0 0 0 0 0 30 0 4 0 0 0 0 50 60 70 0 0 0 0 0 0 80 Output : A = [10 20 30 4 50 60 70 80], IA = [0 2 4 7 8] JA = [0 1 1 3 2 3 4 5] ``` 算法 ``` SPARSIFY (MATRIX) Step 1: Set M to number of rows in MATRIX Step 2: Set N to number of columns in MATRIX Step 3: I = 0, NNZ = 0\. Declare A, JA, and IA. Set IA[0] to 0 Step 4: for I = 0 ... N-1 Step 5: for J = 0 ... N-1 Step 5: If MATRIX [I][J] is not zero Add MATRIX[I][J] to A Add J to JA NNZ = NNZ + 1 [End of IF] Step 6: [ End of J loop ] Add NNZ to IA [ End of I loop ] Step 7: Print vectors A, IA, JA Step 8: END ``` ``` // CPP program to find sparse matrix rep- // resentation using CSR #include <algorithm> #include <iostream> #include <vector> using namespace std; typedef std::vector<int> vi; typedef vector<vector<int> > matrix; // Utility Function to print a Matrix void printMatrix(const matrix& M) { ????int m = M.size(); ????int n = M[0].size(); ????for (int i = 0; i < m; i++) { ????????for (int j = 0; j < n; j++)? ????????????cout << M[i][j] << " ";???????? ????????cout << endl; ????} } // Utility Function to print A, IA, JA vectors // with some decoration. void printVector(const vi& V, char* msg) { ????cout << msg << "[ "; ????for_each(V.begin(), V.end(), [](int a) { ????????cout << a << " "; ????}); ????cout << "]" << endl; } // Generate the three vectors A, IA, JA? void sparesify(const matrix& M) { ????int m = M.size(); ????int n = M[0].size(), i, j; ????vi A; ????vi IA = { 0 }; // IA matrix has N+1 rows ????vi JA; ????int NNZ = 0; ????for (i = 0; i < m; i++) { ????????for (j = 0; j < n; j++) { ????????????if (M[i][j] != 0) { ????????????????A.push_back(M[i][j]); ????????????????JA.push_back(j); ????????????????// Count Number of Non Zero? ????????????????// Elements in row i ????????????????NNZ++; ????????????} ????????} ????????IA.push_back(NNZ); ????} ????printMatrix(M); ????printVector(A, (char*)"A = "); ????printVector(IA, (char*)"IA = "); ????printVector(JA, (char*)"JA = "); } // Driver code int main() { ????matrix M = { ????????{ 0, 0, 0, 0, 1 }, ????????{ 5, 8, 0, 0, 0 }, ????????{ 0, 0, 3, 0, 0 }, ????????{ 0, 6, 0, 0, 1 }, ????}; ????sparesify(M); ????return 0; } ``` 輸出： ``` 0 0 0 0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 A = [ 1 5 8 3 6 1 ] IA = [ 0 1 3 4 6 ] JA = [ 4 0 1 2 1 4 ] ``` **注釋** * 矩陣的稀疏度=（元素總數–非零元素數）/（元素總數）或（1 – NNZ / mn）或（1 – size（A）/ mn）。 * 基于直接數組的表示形式需要內存 3 * NNZ，而 CSR 需要（2 * NNZ + m + 1）內存。 * 只要，CSR 矩陣就可以提高存儲效率。 * 與 CSR 相似，退出 CSC 代表壓縮稀疏列。 它是 CSR 的列類似物。 * “新”耶魯格式進一步將 A 和 JA 向量壓縮為 1 個向量。 **參考** [https://zh.wikipedia.org/wiki/Sparse_matrix](https://en.wikipedia.org/wiki/Sparse_matrix) * * * * * *