在c++++中處理稀疏矩陣的合適方式是選擇特定的存儲結構以節省內存并提高效率。1. coordinate list (coo) 使用三個數組分別存儲行索引、列索引和值，適合構造階段或遍歷非零元素；2. compressed sparse row (csr) 用values、col_index和row_ptr三個數組存儲數據，適合行操作及矩陣向量乘法；3. compressed sparse column (csc) 類似csr但按列存儲，適合頻繁的列操作；4. dictionary of keys (dok) 利用字典存儲非零元素，適合需要頻繁修改矩陣結構的情況；5. 稀疏程度高、結構變化大時選dok，結構固定且需高效運算時優先考慮csr或csc；6. 可使用現成庫如eigen進行稀疏矩陣操作，避免自行實現復雜度高的存儲與運算邏輯。選擇合適的存儲方案能顯著優化空間與性能，同時提升開發效率。
稀疏矩陣，簡單來說，就是矩陣里大部分元素都是零。在c++里處理這種矩陣，如果還傻乎乎地用二維數組，那內存就浪費大了！所以，得想辦法只存那些非零元素，這才能省空間。
解決方案
在C++中實現稀疏矩陣，核心在于選擇合適的存儲結構。以下是一些常見的方案，以及它們各自的優缺點：
立即學習“C++免費學習筆記（深入）”；
-
Coordinate List (COO)
- 存儲方式： 用三個數組分別存儲非零元素的行索引、列索引和值。
- 優點： 簡單易懂，易于構造。
- 缺點： 隨機訪問效率低，不適合進行矩陣運算。
- 適用場景： 矩陣構造階段，或者只需要遍歷所有非零元素的情況。
- 示例代碼：
#include <iostream> #include <vector> struct COO { std::vector<int> row; std::vector<int> col; std::vector<double> val; void insert(int r, int c, double v) { row.push_back(r); col.push_back(c); val.push_back(v); } }; int main() { COO matrix; matrix.insert(0, 0, 1.0); matrix.insert(1, 2, 2.5); matrix.insert(2, 1, -1.0); for (size_t i = 0; i < matrix.row.size(); ++i) { std::cout << "(" << matrix.row[i] << ", " << matrix.col[i] << ") = " << matrix.val[i] << std::endl; } return 0; } -
Compressed Sparse Row (CSR)
- 存儲方式： 用三個數組存儲：
- values: 存儲所有非零元素的值。
- col_index: 存儲每個非零元素對應的列索引。
- row_ptr: 存儲每一行第一個非零元素在values和col_index中的起始位置。
- 優點： 適合進行行操作，矩陣向量乘法效率高。
- 缺點： 修改矩陣結構比較困難。
- 適用場景： 矩陣結構基本固定，需要頻繁進行行操作或者矩陣向量乘法。
- 示例代碼：
#include <iostream> #include <vector> struct CSR { std::vector<double> values; std::vector<int> col_index; std::vector<int> row_ptr; int rows; int cols; CSR(int r, int c) : rows(r), cols(c) { row_ptr.resize(rows + 1, 0); // 初始化row_ptr，所有行起始位置默認為0 } void insert(int r, int c, double v) { values.push_back(v); col_index.push_back(c); // 更新row_ptr，需要遍歷所有行，找到插入位置并更新 for (int i = r + 1; i <= rows; ++i) { row_ptr[i]++; } } void finalize() { // 將row_ptr轉換為前綴和 for (int i = 1; i <= rows; ++i) { row_ptr[i] += row_ptr[i - 1]; } } }; int main() { CSR matrix(3, 3); matrix.insert(0, 0, 1.0); matrix.insert(1, 2, 2.5); matrix.insert(2, 1, -1.0); matrix.finalize(); std::cout << "Values: "; for (double v : matrix.values) std::cout << v << " "; std::cout << std::endl; std::cout << "Column Indices: "; for (int c : matrix.col_index) std::cout << c << " "; std::cout << std::endl; std::cout << "Row Pointers: "; for (int p : matrix.row_ptr) std::cout << p << " "; std::cout << std::endl; return 0; } - 存儲方式： 用三個數組存儲：
-
Compressed Sparse Column (CSC)
- 存儲方式： 類似于CSR，但是按列存儲。
- values: 存儲所有非零元素的值。
- row_index: 存儲每個非零元素對應的行索引。
- col_ptr: 存儲每一列第一個非零元素在values和row_index中的起始位置。
- 優點： 適合進行列操作。
- 缺點： 修改矩陣結構比較困難。
- 適用場景： 需要頻繁進行列操作。
- 存儲方式： 類似于CSR，但是按列存儲。
-
Dictionary of Keys (DOK)
- 存儲方式： 使用字典（例如C++中的std::map）存儲非零元素，鍵為(row, col)，值為對應元素的值。
- 優點： 易于修改矩陣結構，插入和刪除元素效率高。
- 缺點： 隨機訪問效率較低，空間占用可能較大。
- 適用場景： 矩陣結構需要頻繁修改，或者矩陣非常稀疏。
- 示例代碼：
#include <iostream> #include <map> struct DOK { std::map<std::pair<int, int>, double> data; void insert(int r, int c, double v) { data[{r, c}] = v; } double get(int r, int c) { auto it = data.find({r, c}); if (it != data.end()) { return it->second; } else { return 0.0; // 默認返回0，表示該位置是零元素 } } }; int main() { DOK matrix; matrix.insert(0, 0, 1.0); matrix.insert(1, 2, 2.5); matrix.insert(2, 1, -1.0); std::cout << "Matrix[1,2] = " << matrix.get(1, 2) << std::endl; std::cout << "Matrix[0,1] = " << matrix.get(0, 1) << std::endl; return 0; }
如何選擇合適的存儲方案？
- 矩陣的稀疏程度： 如果矩陣非常稀疏，DOK可能更合適。
- 矩陣的結構是否變化： 如果矩陣結構經常變化，DOK更靈活。如果結構基本固定，CSR或CSC效率更高。
- 需要進行的操作： 如果需要頻繁進行行操作，CSR更合適。如果需要頻繁進行列操作，CSC更合適。如果只需要遍歷非零元素，COO足夠了。
- 內存占用： CSR和CSC通常比DOK更節省內存。
C++中有沒有現成的稀疏矩陣庫？
當然有！ Eigen庫就提供了稀疏矩陣的支持。使用現成的庫可以省去很多自己實現的麻煩，而且通常性能也更好。
#include <iostream> #include <Eigen/Sparse> int main() { Eigen::SparseMatrix<double> matrix(3, 3); // 定義一個3x3的稀疏矩陣 // 插入非零元素 matrix.insert(0, 0) = 1.0; matrix.insert(1, 2) = 2.5; matrix.insert(2, 1) = -1.0; matrix.makeCompressed(); // 完成插入后，必須調用makeCompressed() std::cout << "Sparse Matrix:" << std::endl; std::cout << matrix << std::endl; return 0; }
稀疏矩陣的運算有哪些需要注意的地方？
稀疏矩陣的運算，比如加法、乘法，都需要針對稀疏的特性進行優化。直接用二維數組的算法肯定是不行的，效率會非常低。 Eigen庫已經對這些運算進行了優化，可以直接使用。
如何將一個普通的二維數組轉換為稀疏矩陣？
遍歷二維數組，只將非零元素插入到稀疏矩陣中。選擇合適的稀疏矩陣存儲結構，比如DOK，然后逐個插入非零元素。插入完成后，如果需要，可以再轉換為CSR或CSC格式。
