怎样在C++中实现稀疏矩阵_稀疏矩阵存储方案对比

在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++免费学习笔记（深入）”；

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

   登录后复制

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

   登录后复制

3. Compressed Sparse Column (CSC)

   • 存储方式： 类似于CSR，但是按列存储。
     • values: 存储所有非零元素的值。
     • row_index: 存储每个非零元素对应的行索引。
     • col_ptr: 存储每一列第一个非零元素在values和row_index中的起始位置。
   • 优点： 适合进行列操作。
   • 缺点： 修改矩阵结构比较困难。
   • 适用场景： 需要频繁进行列操作。

4. 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格式。

以上就是怎样在C++中实现稀疏矩阵_稀疏矩阵存储方案对比的详细内容，更多请关注php中文网其它相关文章！