稀疏矩阵的压缩存储格式COO、CSR与CSC的内存效率对比

理解问题：为什么要用压缩格式？

观察一个大型矩阵。你会发现，如果这个矩阵的大部分元素都是零，就像一个巨大的电子表格，但几乎都是空白，只在零星几个位置有数字。这就是“稀疏矩阵”。

存储整个矩阵会浪费大量内存。例如，一个 $10000 \times 10000$ 的矩阵，即使只有 1% 的非零元素，也需要为那 99% 的零元素保留存储空间，这非常不经济。

选择压缩格式的目标，就是只存储非零元素及其位置信息，从而极大地节省内存。

认识三种压缩格式

1. COO：坐标格式

COO 格式最简单，就像给每个非零元素发一张“身份证”。

使用三个数组：

1. row 数组：存储每个非零元素所在的行号。
2. col 数组：存储每个非零元素所在的列号。
3. data 数组：存储每个非零元素的值。

构建一个示例矩阵来说明：

矩阵 M（3行4列）：

[1, 0, 0, 2]
[0, 0, 3, 0]
[4, 0, 0, 0]

它的 COO 存储可以是（假设按行顺序遍历）：

• row = [0, 0, 1, 2]
• col = [0, 3, 2, 0]
• data = [1, 2, 3, 4]

特点：结构极其直观，但访问某一行或某一列的数据时，需要遍历整个 row 或 col 数组来查找，效率较低。它常用于构建矩阵的初始阶段。

2. CSR：压缩稀疏行格式

CSR 格式专注于高效地按行访问数据。它在 COO 的基础上进一步压缩了行信息。

使用三个数组：

1. data 数组：存储所有非零元素的值（与 COO 相同）。
2. col 数组：存储每个非零元素所在的列号（与 COO 相同）。
3. row_ptr 数组：这是核心。它是一个长度为 (行数 + 1) 的数组。row_ptr[i] 表示前 i 行中所有非零元素的个数。通过 row_ptr[i] 和 row_ptr[i+1]，可以快速定位第 i 行的非零元素在 data 和 col 数组中的起始和结束位置。

同样以上面矩阵 M 为例：

• data = [1, 2, 3, 4]
• col = [0, 3, 2, 0]
• row_ptr = [0, 2, 3, 4]

解读 row_ptr：

• 第 0 行（row_ptr[0]=0 到 row_ptr[1]=2）：对应 data 和 col 的索引 [0, 2)，即 data[0]=1 (col=0) 和 data[1]=2 (col=3)。
• 第 1 行（row_ptr[1]=2 到 row_ptr[2]=3）：对应索引 [2, 3)，即 data[2]=3 (col=2)。
• 第 2 行（row_ptr[2]=3 到 row_ptr[3]=4）：对应索引 [3, 4)，即 data[3]=4 (col=0)。

特点：按行访问数据非常高效。只需要简单的索引计算。这是科学计算和机器学习中最常用的格式之一，因为很多算法（如矩阵向量乘法）是按行进行的。

3. CSC：压缩稀疏列格式

CSC 格式与 CSR 完全对称，只是它专注于高效地按列访问。

使用三个数组：

1. data 数组：存储所有非零元素的值。
2. row 数组：存储每个非零元素所在的行号。
3. col_ptr 数组：长度为 (列数 + 1)。col_ptr[j] 和 col_ptr[j+1] 定义了第 j 列的非零元素在 data 和 row 数组中的范围。

同样以上面矩阵 M 为例（按列顺序遍历存储非零元素）：

• data = [1, 4, 3, 2]
• row = [0, 2, 1, 0]
• col_ptr = [0, 2, 2, 3, 4]

解读 col_ptr：

• 第 0 列（col_ptr[0]=0 到 col_ptr[1]=2）：对应 data 和 row 的索引 [0, 2)，即 data[0]=1 (row=0) 和 data[1]=4 (row=2)。
• 第 1 列（col_ptr[1]=2 到 col_ptr[2]=2）：区间为空，表示此列无非零元素。
• 第 2 列（col_ptr[2]=2 到 col_ptr[3]=3）：对应索引 [2, 3)，即 data[2]=3 (row=1)。
• 第 3 列（col_ptr[3]=3 到 col_ptr[4]=4）：对应索引 [3, 4)，即 data[3]=2 (row=0)。

特点：按列访问数据非常高效。在需要处理矩阵列的场景（如某些优化问题）中很有用。

核心对比：内存效率分析

计算内存占用。我们不存储零元素，只存储非零元素的值、行号/列号以及用于快速定位的指针数组。

假设一个矩阵有 m 行，n 列，非零元素个数为 nnz。我们使用基础数据类型（如 double 或 int），每个数值占用 K 字节。

1. COO 格式：

   • data 数组：nnz * K 字节。
   • row 数组：nnz * K 字节。
   • col 数组：nnz * K 字节。
   • 总内存：3 * nnz * K 字节。
   • 内存效率公式：总内存 / (整个稠密矩阵内存) = (3 * nnz * K) / (m * n * K) = 3 * nnz / (m * n)。

2. CSR 格式：

   • data 数组：nnz * K 字节。
   • col 数组：nnz * K 字节。
   • row_ptr 数组：(m + 1) * K 字节。
   • 总内存：(2 * nnz + m + 1) * K 字节。
   • 内存效率公式：(2 * nnz + m + 1) / (m * n)。

3. CSC 格式：

   • data 数组：nnz * K 字节。
   • row 数组：nnz * K 字节。
   • col_ptr 数组：(n + 1) * K 字节。
   • 总内存：(2 * nnz + n + 1) * K 字节。
   • 内存效率公式：(2 * nnz + n + 1) / (m * n)。

进行数值比较。取一个具体例子：一个 10000 x 10000 的矩阵，nnz = 100000（即稀疏度为 0.1%）。假设 K=8 字节（double 类型）。

• 稠密存储：10000 * 10000 * 8 = 800,000,000 字节 ≈ 800 MB。
• COO 格式：3 * 100000 * 8 = 2,400,000 字节 ≈ 2.4 MB。
• CSR 格式：(2 * 100000 + 10001) * 8 = (200000 + 10001) * 8 = 1,680,008 字节 ≈ 1.68 MB。
• CSC 格式：(2 * 100000 + 10001) * 8 = 1,680,008 字节 ≈ 1.68 MB。

得出核心结论：

• COO：内存开销最大，因为它为每个元素都存储了完整的行、列坐标。优势是构建简单，易于理解和转换。
• CSR 和 CSC：内存效率远高于 COO。它们通过一个指针数组（row_ptr 或 col_ptr）共享了行或列的索引信息，避免了重复存储。在 m 和 n 很大且 nnz 较小时，指针数组的开销 (m+1) 或 (n+1) 相比 2*nnz 可以忽略不计，因此它们的内存占用接近于 2 * nnz * K，即只存储非零元素的值和一个维度的坐标。这是实践中最常用的高效格式。

实战选择指南

1. 选择 COO 格式，如果你：

   • 正在从零开始动态构建一个稀疏矩阵（例如，逐个添加元素）。
   • 需要最简单的数据结构进行调试或理解原理。
   • 准备将数据导入到另一个系统（如某些稀疏线性代数库），COO 常作为通用交换格式。

2. 选择 CSR 格式，如果你：

   • 需要高效地按行遍历矩阵或执行矩阵向量乘法（$y = A * x$）。这是最常见的操作。
   • 矩阵的行数 m 远大于列数 n，这样 row_ptr 数组的额外开销更小。

3. 选择 CSC 格式，如果你：

   • 需要高效地按列遍历矩阵，或者算法涉及矩阵的转置操作（CSC(A) 等价于 CSR(A^T)）。
   • 矩阵的列数 n 远大于行数 m，这样 col_ptr 数组的额外开销更小。

记住：许多数学库（如 Eigen, SciPy）提供了这三种格式之间的快速转换工具。通常，你会在数据加载或构建阶段使用 COO，然后在计算密集的核心循环前，转换为 CSR 或 CSC 格式以获得最佳性能。