深入解析 CSR 格式：优化稀疏矩阵存储的高效指南

2026-02-10 06:56:57 0条评论 2次阅读 0人点赞

在处理大规模数据科学、图形算法或机器学习模型时，我们经常遇到一种特殊的“胖子”矩阵——稀疏矩阵。这些矩阵的大部分元素都是零，如果我们在内存中老老实实地把它们按二维数组存下来，不仅是对存储空间的极大浪费，更会拖慢我们计算的速度。想象一下，一个 $10000 \times 10000$ 的矩阵，如果只有 0.1% 的元素是非零的，我们却要分配 1 亿个单元的空间，这显然是不可接受的。

为了解决这个问题，我们在之前的文章中探讨了几种稀疏矩阵的表示方法。在本文中，我们将深入研究工业界最常用、也是最标准的稀疏矩阵表示法之一：CSR（Compressed Sparse Row，压缩稀疏行）格式，有时也被称为 Yale 格式。

什么是 CSR 格式？

简单来说，CSR 格式就是一种“按行压缩”的存储策略。与我们在 Set 1 中讨论过的数组表示法相比，CSR 更进一步，它通过三个一维数组（向量）将一个 $m \times n$ 的矩阵 $M$ 完美地复刻下来。这三个向量通常被命名为 A、IA 和 JA。

让我们定义一下符号：

  • NNZ：矩阵中非零元素的数量。
  • 索引：本文默认使用基于 0 的索引。

1. 数据数组 A (Values)

这是一个长度为 NNZ 的数组。它的作用非常直观：按行优先的顺序，存储矩阵中所有非零元素的值。也就是我们从头到尾一行一行地扫描矩阵，把遇到的非 0 数值按顺序塞进 A 里。

2. 列索引数组 JA (Column Indices)

这也是一个长度为 NNZ 的数组。它与数组 A 一一对应。JA[i] 存储的就是 A[i] 这个数值在原矩阵中的列号。通过 A 和 JA 的配合，我们就知道了“某个非零值是多少”以及“它在哪一列”。

3. 行偏移数组 IA (Row Offsets)

这是 CSR 格式的核心，也是初学者最容易晕的地方。IA 的大小为 $m + 1$（行数 + 1）。IA[i] 存储的是：从矩阵第 0 行到第 i-1 行（即不包括第 i 行）中，非零元素的总数。

通常定义如下：

  • IA[0] = 0（第一行之前肯定没有元素）
  • IA[i] = IA[i-1] + (第 i-1 行中的非零元素个数)

或者换个更实用的角度理解：第 i 行的非零元素，存储在数组 A 和 JA 的 IA[i] 到 IA[i+1] – 1 的区间内。 这种表示法让我们可以极快地通过行号定位数据。

让我们通过一个例子来看看

光说不练假把式。让我们来看一个具体的 $4 \times 4$ 矩阵，看看它是如何被转化成 CSR 格式的。

输入矩阵：

   0   0   0   0
   5   8   0   0
   0   0   3   0
   0   6   0   0

转化过程

  • 构建 A (数值)：逐行扫描，遇到的非零数是 5, 8, 3, 6。

* A = [5, 8, 3, 6]

  • 构建 JA (列索引)：看看这些数分别在那一列。

* 5 在第 0 列，8 在第 1 列，3 在第 2 列，6 在第 1 列。

* JA = [0, 1, 2, 1]

  • 构建 IA (行偏移)：这是关键，我们累加每一行的非零元素数量。

* 第 0 行：全是 0，数量为 0。累计 = 0。 -> IA[0] = 0

* 第 1 行：有 5, 8，数量为 2。累计 = 0 + 2 = 2。 -> IA[1] = 2

* 第 2 行：有 3，数量为 1。累计 = 2 + 1 = 3。 -> IA[2] = 3

* 第 3 行：有 6，数量为 1。累计 = 3 + 1 = 4。 -> IA[3] = 4

* 结束标志：NNZ 总数为 4。 -> IA[4] = 4

* IA = [0, 0, 2, 3, 4]

你可以看到，通过 IA 数组，我们可以瞬间算出任何一行的非零元素个数。比如第 1 行（索引为1），元素个数就是 IA[2] - IA[1] = 2 - 0 = 2。

算法逻辑

了解了原理，让我们把它转化成算法步骤。这个过程通常被称为“稀疏化”。

算法 SPARSIFY (MATRIX)
// 输入：普通二维矩阵 MATRIX
// 输出：A, JA, IA 三个向量

步骤 1: 初始化。
        设 M 为矩阵行数，N 为矩阵列数。
        创建向量 A, JA 用于存储数据。
        创建向量 IA，并初始化 IA[0] = 0。
        设 NNZ = 0 (当前非零元素计数器)。

步骤 2: 外层循环。遍历每一行 I (从 0 到 M-1)。
        
        步骤 3: 内层循环。遍历该行的每一列 J (从 0 到 N-1)。
        
        步骤 4: 检查元素 MATRIX[I][J]。
                如果 MATRIX[I][J] 不等于 0：
                    1. 将 MATRIX[I][J] 加入 A。
                    2. 将 J 加入 JA。
                    3. NNZ 计数加 1。
                
        步骤 5: [结束内层循环]
                将当前的 NNZ 值加入到 IA 中。
                (这一步记录了截至当前行，我们一共找到了多少个非零元素)

步骤 6: [结束外层循环]

步骤 7: 输出 A, IA, JA。

C++ 代码实现

让我们把上面的算法翻译成实际的代码。这里我们使用 std::vector 来实现动态数组，这样更安全也更现代。

#include 
#include 

using namespace std;

// 定义矩阵类型的别名，方便使用
typedef vector<vector> Matrix;

/**
 * 辅助函数：打印普通的二维矩阵
 */
void printMatrix(const Matrix& M) {
    for (const auto& row : M) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

/**
 * 辅助函数：打印 CSR 向量
 * @param V 要打印的向量
 * @param name 向量的名称（如 "A"）
 */
void printVector(const vector& V, const string& name) {
    cout << name << " = [ ";
    for (int val : V) {
        cout << val << " ";
    }
    cout << "]" << endl;
}

/**
 * 核心函数：将普通矩阵转换为 CSR 格式
 * @param M 输入的稀疏矩阵
 */
void sparsifyCSR(const Matrix& M) {
    vector A;    // 存储非零元素的值
    vector JA;   // 存储非零元素的列索引
    vector IA;   // 存储行偏移量
    
    IA.push_back(0); // IA[0] 永远是 0
    int NNZ = 0;     // 非零元素计数器

    // 获取矩阵的行数和列数
    int rows = M.size();
    if (rows == 0) return;
    int cols = M[0].size();

    // 外层循环遍历行
    for (int i = 0; i < rows; i++) {
        // 内层循环遍历列
        for (int j = 0; j < cols; j++) {
            // 如果发现非零元素
            if (M[i][j] != 0) {
                A.push_back(M[i][j]); // 值存入 A
                JA.push_back(j);      // 列索引存入 JA
                NNZ++;                // 计数加 1
            }
        }
        // 当前行扫描完毕，将目前的总非零数存入 IA
        IA.push_back(NNZ);
    }

    // 打印结果对比
    cout << "原始矩阵:" << endl;
    printMatrix(M);
    cout << "
CSR 表示结果:" << endl;
    printVector(A, "A");
    printVector(IA, "IA");
    printVector(JA, "JA");
}

int main() {
    // 测试用例 1：简单矩阵
    Matrix M1 = {
        {0, 0, 0, 0},
        {5, 8, 0, 0},
        {0, 0, 3, 0},
        {0, 6, 0, 0}
    };

    sparsifyCSR(M1);
    
    cout << "-----------------------------" << endl;

    // 测试用例 2：较大规模的矩阵
    Matrix M2 = {
        {10, 20, 0, 0, 0, 0},
        {0, 30, 0, 4, 0, 0},
        {0, 0, 50, 60, 70, 0},
        {0, 0, 0, 0, 0, 80}
    };
    sparsifyCSR(M2);

    return 0;
}

代码深度解析

  • 数据结构选择：我们使用了 INLINECODEc4e95215 而不是原生数组。这是 C++ 中的最佳实践，因为它能自动管理内存。我们不需要预先知道非零元素的具体数量，INLINECODE4b054f6f 会自动帮我们扩容。
  • IA 的构建细节：请注意 INLINECODEea50ef29 这一行。它位于外层 INLINECODE01c07542 循环的末尾。每当扫描完一行，我们就把当前的“累计总数”记录下来。这完美符合了 IA 的定义：“截至第 i 行，有多少个非零元素”。
  • 输入输出的灵活性：虽然代码示例使用了 INLINECODEf027d882，但在实际工程中，根据数值范围，你可能会使用 INLINECODE29894e07 或 INLINECODEf8a518fe 作为 A 数组的类型，而 JA 和 IA 通常保持为整型（INLINECODEbc6410af 或 size_t）。

CSR 的优势与应用场景

为什么要费这么大劲把一个矩阵拆成三段？

  • 空间复杂度：对于一个 $90\%$ 都是零的矩阵，CSR 可以节省 $90\%$ 左右的存储空间。我们只存储有意义的数据。
  • 算术运算加速：特别是在稀疏矩阵-向量乘法 中，CSR 表现极其出色。计算 $y = Ax$ 时，我们可以直接遍历 A 数组，利用 JA 找到对应的 $x$ 分量，利用 IA 快速跳过全零行，避免了对 0 的无用乘法运算。
  • 行业标准：许多科学计算库（如 Intel MKL, SuiteSparse, Scikit-learn）的底层默认稀疏格式就是 CSR。

实战中的最佳实践与注意事项

虽然 CSR 很强大，但在实际开发中，有几个坑是你一定要注意的：

  • 随机访问的代价：如果你想直接获取 Matrix[10][20] 的值，在 CSR 格式中是非常慢的。你需要先定位 IA[10] 的范围，然后在 JA 中查找 20。如果是这种需求，可能需要考虑 DIA (对角线存储) 或 COO (坐标列表) 格式。
  • 修改的困难：CSR 是一种“只读友好”的格式。如果你要在矩阵中间插入一个非零元素，可能会导致后面的所有元素都要移动索引，甚至需要重新分配内存。最佳实践是：先构建好矩阵，然后再转换为 CSR 格式进行计算。
  • 索引类型的溢出：在处理超大规模矩阵（比如数十亿非零元素）时，IA 数组中的值可能会超过 32 位整数的范围。这种情况下，记得将 IA 和 JA 定义为 INLINECODE881d32a1 或 INLINECODEfdc59cd9 类型，防止溢出。

总结

在这篇文章中，我们深入探讨了稀疏矩阵的 CSR（压缩稀疏行）表示法。我们学习了它由三个核心数组（A, IA, JA）构成，理解了行偏移数组 IA 的精妙设计，并亲手实现了从普通矩阵到 CSR 的转换算法。

掌握 CSR 格式是进入高性能计算和科学编程领域的门票。当你下一次遇到 SparseMatrix 相关的报错或性能瓶颈时，你会明白底层数据是如何流动的。在未来的文章中，我们将探讨 CSR 如何与 CSC（压缩稀疏列）配合进行矩阵转置，以及更高级的稀疏矩阵运算技巧。继续加油！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/42063.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年