C++稀疏矩阵压缩（从零开始掌握稀疏矩阵的高效存储与实现）

常见的稀疏矩阵压缩格式

在C++中，常用的稀疏矩阵压缩方法包括：

• 三元组格式（Triplet Format）：每个非零元素用 (行索引, 列索引, 值) 表示。
• COO格式（Coordinate Format）：与三元组类似，常用于构建稀疏矩阵。
• CSC/CSR格式：适用于矩阵运算，但实现较复杂。

本文将重点讲解最基础也最易理解的三元组压缩方法，这也是理解其他格式的基础。

C++实现三元组压缩

我们可以定义一个结构体来表示每个非零元素，并用一个vector存储所有非零项。

#include <iostream>#include <vector>// 定义三元组结构体struct Triplet {    int row;      // 行索引    int col;      // 列索引    double value; // 非零值    // 构造函数    Triplet(int r, int c, double v) : row(r), col(c), value(v) {}};// 稀疏矩阵类class SparseMatrix {private:    std::vector<Triplet> data; // 存储所有非零元素    int rows, cols;            // 矩阵维度public:    SparseMatrix(int r, int c) : rows(r), cols(c) {}    // 添加非零元素    void addElement(int r, int c, double val) {        if (val != 0.0) {            data.emplace_back(r, c, val);        }    }    // 打印压缩后的三元组    void printTriplets() const {        std::cout << "(行, 列, 值):\n";        for (const auto& t : data) {            std::cout << "(" << t.row << ", " << t.col                       << ", " << t.value << ")\n";        }    }    // 获取原始矩阵中某位置的值（模拟访问）    double getValue(int r, int c) const {        for (const auto& t : data) {            if (t.row == r && t.col == c) {                return t.value;            }        }        return 0.0; // 默认为0    }};// 示例使用int main() {    SparseMatrix mat(4, 4);    // 添加非零元素    mat.addElement(0, 1, 5.0);    mat.addElement(1, 3, -2.0);    mat.addElement(2, 2, 7.0);    mat.addElement(3, 0, 3.5);    std::cout << "压缩后的三元组表示：\n";    mat.printTriplets();    std::cout << "\n获取 (2,2) 位置的值: " << mat.getValue(2, 2) << std::endl;    std::cout << "获取 (1,1) 位置的值: " << mat.getValue(1, 1) << std::endl; // 应为0    return 0;}

代码解析

上述代码实现了基本的C++三元组压缩：

• Triplet 结构体保存每个非零元素的位置和值。
• SparseMatrix 类用 std::vector<Triplet> 存储数据。
• addElement 方法只在值非零时才添加，避免冗余。
• getValue 模拟了对原始矩阵的随机访问（实际应用中可优化为哈希表或排序后二分查找）。

进阶：COO格式与性能优化

三元组格式本质上就是COO格式（Coordinate Format）。在实际工程中，为了提升访问速度，可将行、列、值分别存入三个独立的数组（便于缓存友好和并行处理）：

class COOSparseMatrix {public:    std::vector<int> rows;    std::vector<int> cols;    std::vector<double> values;    int nrows, ncols;    COOSparseMatrix(int r, int c) : nrows(r), ncols(c) {}    void add(int i, int j, double v) {        if (v != 0.0) {            rows.push_back(i);            cols.push_back(j);            values.push_back(v);        }    }};

总结

通过本教程，你已经掌握了C++稀疏矩阵压缩的基本原理与实现方法。三元组（COO）格式简单直观，适合初学者理解和快速实现。在实际项目中，可根据需求选择更高效的格式如CSR/CSC。

记住，压缩的核心思想是：只存非零，记录位置。这不仅能节省内存，还能加速后续的矩阵运算。

希望这篇教程能帮助你入门稀疏矩阵存储格式，为后续学习高性能数值计算打下坚实基础！