TL;DR

在科学计算和机器学习中，我们经常遇到稀疏矩阵——大部分元素为零的矩阵。如果用传统的二维数组存储，既浪费内存又影响计算效率。CSR (Compressed Sparse Row) 格式是解决这一问题的经典方案。

我其实很早就知道 CSR 的概念了，但我一直没有搞清楚到底如何存储和读取。后来通过交互式演示一下子就明白了，希望对其他人理解 CSR 有帮助。

CSR 格式详解

三个数组的含义

数组 全称 作用
Values (A) Value Array 按行优先顺序存储所有非零元素
Column Indices (JA) Column Index Array 记录每个非零元素的列号
Row Pointers (IA) Row Pointer Array 记录每行第一个非零元素在 Values 中的位置

如何读取第 i 行？

1
2
3
4
5
# 伪代码
start = IA[i]
end = IA[i + 1]
row_values = A[start:end]
row_cols = JA[start:end]

空间复杂度

设矩阵大小为 $n \times m$，非零元素个数为 $nnz$：

  • 传统存储: $O(n \times m)$
  • CSR 存储: $O(nnz + n + 1)$

当 $nnz \ll n \times m$ 时，CSR 的优势非常明显。

常见操作时间复杂度

设第 $i$ 行的非零元素个数为 $nnz_i$：

操作 时间复杂度
遍历所有非零元素 $O(nnz)$
访问第 $i$ 行 $O(1)$ 定位，遍历需要 $O(nnz_i)$
查找元素 $A_{ij}$ 未排序时 $O(nnz_i)$；列索引有序时 $O(\log nnz_i)$
稀疏矩阵向量乘法 $O(nnz)$
矩阵加法 $O(nnz_A + nnz_B)$
转置 CSR $O(nnz + n + m)$
插入或删除元素 $O(nnz)$
按列访问 $O(nnz)$

变体格式

格式 特点 适用场景
CSC (Compressed Sparse Column) 按列压缩 列优先访问
COO (Coordinate List) 坐标列表 矩阵构建阶段
BSR (Block Sparse Row) 块状压缩 规则的块结构