1. 稀疏矩阵存储格式选型与内存评估

问题界定与评估口径

给定一个大型稀疏矩阵，格式选型的核心不是“哪个格式最好”，而是“在什么操作模式下、以什么内存与构建代价，换取什么样的访问效率”。本例以三个可量化指标作为选型依据：

• 存储内存：索引数组与数值数组的总字节数，按各格式真实字段计算。
• 构建开销：从三元组（COO 式输入）构造目标格式所需的排序、计数、前缀和与拷贝工作量。
• 访问适配：按行遍历（如 SpMV）偏好 CSR，按列遍历偏好 CSC，纯装配/转换阶段偏好 COO。

下面用一个具体算例贯穿：矩阵规模 m = 2,000,000 行、n = 2,000,000 列、非零元 nnz = 50,000,000，索引使用 32 位整数（4 字节），数值使用双精度（8 字节）。

三种格式的字段结构与内存公式

设 nnz 为非零元个数，m 为行数，n 为列数，s 为索引字节数，v 为数值字节数：

• COO：row[nnz] + col[nnz] + val[nnz]，内存 = nnz·(2s + v)。无压缩，允许重复索引与乱序。
• CSR：row_ptr[m+1] + col_idx[nnz] + val[nnz]，内存 = (m+1)·s + nnz·(s + v)。
• CSC：col_ptr[n+1] + row_idx[nnz] + val[nnz]，内存 = (n+1)·s + nnz·(s + v)。

代入算例数据：

可见 CSR 与 CSC 内存相同（当 m = n 时），比 COO 节省约 24%，节省量正好等于一份行/列索引数组。若矩阵极度“高瘦”或“矮胖”，m 与 n 差异会打破这一对称性，此时指针数组长度成为次要但可测的差异项。

构建开销的量化估算

构建开销不能只看渐近阶，还要看实际遍历次数与临时内存。以 CSR 为例，从 COO 三元组构造的典型路径是：

1. 统计每行非零元个数：遍历 row 数组一次，O(nnz)，写 row_ptr 计数区。
2. 对 row_ptr 做前缀和：O(m)，得到每行起始偏移。
3. 按行散射：再遍历一次三元组，把 col 与 val 写入 CSR 的 col_idx 与 val，O(nnz)。

因此 CSR 构建约需 2 次 nnz 遍历 + 1 次 m 遍历，峰值临时内存为 row_ptr 计数区（(m+1)·s）加上目标数组本身。COO 构建只需 1 次 nnz 遍历直接写入，但若输入本身乱序且后续需要按行访问，则每次访问都要额外承担随机寻址代价。

用算例估算：nnz = 5×10⁷，两次遍历共 10⁸ 次元素访问；若单次随机访问约 100 ns（受缓存未命中影响），仅散射阶段就约 5 s 量级。这是示例性量级估算，实际取决于内存带宽、是否多线程与输入有序程度，不能当作实测值。

选型决策与量化依据

把上述指标整理成可执行的判断规则：

本例的量化结论：在 m = n = 2×10⁶、nnz = 5×10⁷ 且以按行迭代求解为主时，选 CSR。理由是内存从 800 MB 降到约 608 MB（节省 24%），构建仅多出一次前缀和与一次散射遍历，而按行访问的局部性收益在迭代求解中会被反复放大。若后续算法以按列访问为主，则对称地选 CSC，内存结论不变。