想象你是城市边缘一座巨型仓库的仓管员。仓库里有 1 万排货架、每排 1 万个格子，总共一亿个位置，可真正放货的格子只有几千个——绝大多数格子空着落灰。如果按规矩给每个位置都画一张入库图，光是图纸就能铺满半个足球场，而且查一件货还要在密密麻麻的网格里数坐标。聪明的做法，是只拿一本小簿子，记下“哪里有货、货是什么”。存得少，查得快，这本簿子就是“稀疏矩阵”的独门心法。矩阵里绝大部分是 0，就像大部分货架空着；存储时别为每个 0 花地方，只精打细算地记非零元素和它的位置；计算时跳过空位置，只对有货处下手。这篇文章，就带你弄懂稀疏矩阵这本“账”怎么记、怎么查、怎么用。

岗位关联

掌握稀疏矩阵的存储与计算，是 AI 从业者处理大数据、跑图神经网络的必备基本功——它决定你能在有限内存里装下多大的数据、用多快的速度完成计算。

目录
  1. 可视化演示
  2. 稀疏矩阵定义
  3. COO坐标格式
  4. CSR压缩行
  5. CSC压缩列
  6. 格式对比选型
  7. 稀疏矩阵乘法
  8. 图与推荐应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

动态演示稀疏矩阵的核心机制，通过入门/进阶/实战/优化四种模式展示关键概念与交互流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

稀疏矩阵：稀疏矩阵 稀疏矩阵的定义与稀疏度度量 COO坐标存储格式与三元组表示 核心机制可视化 稀疏矩阵整体架构与关键组件

稀疏矩阵定义

仓管员小张刚上任时，按上级要求把整个仓库画成一张 10000×10000 的巨型图纸，每格代表一个货位，有货打勾、没货留空。图纸铺开能盖住半个足球场，可仔细一看，99% 的格子都是空白。他意识到：花同样的力气管理空位，是最大的浪费。

这套图纸，翻译成数学语言就是“矩阵”——一个 m 行 n 列的数字表格。表格里绝大多数元素是 0，就称为稀疏矩阵；反过来，零元素比例很低、绝大多数位置都有实际数字的，叫稠密矩阵。图计算、推荐系统、物理模拟里的大矩阵，几乎全是稀疏的。判断稀疏程度有个量化指标——稀疏度（sparsity），即零元素个数占总元素个数的比例，其中 nnz 表示非零元素个数（number of non-zeros）。

小张后来明白了：图纸本身的绝大部分是空白，真正值得管理的是那几个钩。数学上这类“大多数是空”的表格，就是稀疏矩阵。认识它，是学会“存得少算得快”的第一步。

稀疏度 ρ=mn−nnzmn×100%\text{稀疏度}\ \rho = \frac{m n - \text{nnz}}{m n} \times 100\%
稀疏度 ρ 就是“空货架占全部货架的比例”。工程上一般 ρ 超过 90% 就值得用稀疏格式存储；ρ 越大，画“全图纸”的浪费越严重。
  1. 分子（零元素个数）用总数 m×n 减去非零数 nnz，得到空货架的格数。
    mn−nnz\displaystyle m n - \text{nnz}
  2. 分母（总元素个数）矩阵所有格子数量，即行数乘列数。
    mn\displaystyle m n
  3. 比值即稀疏度零元素占比越高，矩阵越“稀”。
    ρ=mn−nnzmn×100%\displaystyle \rho = \frac{m n - \text{nnz}}{m n} \times 100\%
  4. 实用判据超过 90% 采用稀疏存储更划算。
    ρ>90%\displaystyle \rho > 90\%

COO坐标格式

小张换了一本“流水账法”：来一件货，就撕一张小票，写上“第几排第几列、什么货”。一晚上下来，簿子上只有寥寥几十条记录，比那张巨型图纸薄了无数倍。这种记录方式没有任何章法可言，好处是写起来最快。

在稀疏矩阵里，这就是最直观的存储格式——COO（Coordinate，坐标格式）。它用三个等长数组保存每个非零元素：row 数组记行号，col 数组记列号，values 数组记数值。三条记录一一对应，就像一张小票写着“位置+货物”。举个例子，下面这个 4×4 矩阵只有 6 个非零元素，完整存储要存 16 个数，而 COO 只需记录：row=[0,0,1,2,2,3]，col=[0,3,1,0,3,2]，values=[1,2,3,4,5,6]。

COO 像小张的流水小票，记起来毫不费力，但真要查“第 3 排有什么货”，得把整本簿子从头翻到尾。存得少的问题解决了，查得快的目标还差一步——这正是下一章压缩格式登场的理由。

SCOO=3×nnz×b,S稠密=m×n×bS_{\text{COO}} = 3 \times \text{nnz} \times b,\qquad S_{\text{稠密}} = m \times n \times b
其中 b 是单个数据占用的字节数。COO 要存三个等长数组，代价是 nnz 的 3 倍；但相比 m×n 的“满图纸”，当 nnz 远小于 mn 时，依然节省一个数量级以上。
  1. 三个等长数组行号、列号、数值各一条，长度都是 nnz。
    SCOO=3×nnz×b\displaystyle S_{\text{COO}} = 3 \times \text{nnz} \times b
  2. 稠密矩阵占用全部 m×n 个格子都存。
    S稠密=m×n×b\displaystyle S_{\text{稠密}} = m \times n \times b
  3. 比值优势nnz 远小于 mn，稀疏度越高差距越大。
    SCOOS稠密=3 nnzmn\displaystyle \frac{S_{\text{COO}}}{S_{\text{稠密}}} = \frac{3\,\text{nnz}}{m n}

CSR压缩行

小张发现，客户最爱问“某一排货架上都放了什么”。流水账虽然记得快，查起来却要翻遍整本。于是他把小票重抄了一遍：按排数整理，每排开头注明“本排货物从第几条记录开始”。这样查某排时，直接跳转到对应起始记录即可。

这就是 CSR（Compressed Sparse Row，压缩稀疏行）格式的思路：按行压缩。它仍用三个数组，但含义变了——values 存所有非零元素；col_ind 存每个非零元素所在列号；row_ptr 存每行非零元素在 values 中的起始下标，长度是 m+1，最后一项是总非零数 nnz。还是上面那个 4×4 矩阵，CSR 表示为 values=[1,2,3,4,5,6]、col_ind=[0,3,1,0,3,2]、row_ptr=[0,2,3,5,6]。row_ptr[i+1]−row_ptr[i] 就是第 i 行的非零个数，例如第 0 行差值为 2，对应 values 里下标 [0,2) 的两个元素 1 和 2。

用了 row_ptr 之后，小张查“第 3 排有什么货”只要两步：看排索引、顺着记录往下数。客户问一排，他翻一页。CSR 也因此成为当今最主流的稀疏格式，SciPy、TensorFlow 里的稀疏张量大多以它为默认。

row_ptr[i+1]−row_ptr[i]=第 i 行的非零个数\text{row\_ptr}[i+1] - \text{row\_ptr}[i] = \text{第 } i \text{ 行的非零个数}
row_ptr 本质是前缀和：把每行非零个数逐个累加。因此相邻两项之差天然给出该行元素个数，查任意一行只需 O(1) 定位起点，再按个数顺序取，无需扫描全表。
  1. 行起点第 i 行的第一个非零元素在 values 中的下标。
    row_ptr[i]\displaystyle \text{row\_ptr}[i]
  2. 行终点下一行起点即本行终点，区间左闭右开。
    row_ptr[i+1]\displaystyle \text{row\_ptr}[i+1]
  3. 区间长度相邻两项之差即该行非零个数。
    row_ptr[i+1]−row_ptr[i]\displaystyle \text{row\_ptr}[i+1] - \text{row\_ptr}[i]
  4. 占用对比CSR 比 COO 少存一套完整的行号数组，更省空间。
    SCSR≈(m+1+2 nnz)×b\displaystyle S_{\text{CSR}} \approx (m + 1 + 2\,\text{nnz}) \times b

CSC压缩列

小张后来又遇到一类客户：质检部门每次抽查“某列货架上的所有货物”。按行整理的簿子查列就很慢——得把所有排都翻一遍。小张灵机一动：把簿子按列重新整理，每列开头注明“本列货物从第几条记录开始”，问题迎刃而解。

这就是 CSC（Compressed Sparse Column，压缩稀疏列）格式：按列压缩，与 CSR 完全对称。它同样用三个数组：values 存非零值；row_ind 存每个非零值所在的行号；col_ptr 存每列非零值在 values 中的起始下标，长度 n+1。同样矩阵的 CSC 表示为 values=[1,4,3,6,2,5]、row_ind=[0,2,1,3,0,2]、col_ptr=[0,2,3,4,6]。col_ptr[j+1]−col_ptr[j] 就是第 j 列非零个数，例如第 0 列有 2 个元素（行 0 的值 1、行 2 的值 4），对应下标 [0,2)。

从流水账到按行整理、再到按列整理，小张的簿子越来越贴合使用习惯。COO、CSR、CSC 没有绝对优劣，只有“合不合适”——看的是你的算法平时按行问，还是按列问。

col_ptr[j+1]−col_ptr[j]=第 j 列的非零个数\text{col\_ptr}[j+1] - \text{col\_ptr}[j] = \text{第 } j \text{ 列的非零个数}
CSC 是 CSR 的“转置视角”：把行列角色互换，列偏移数组承担与 row_ptr 完全相同的定位职责，只是服务的访问方向从“按行”变成了“按列”。
  1. 列起点第 j 列首个非零元素在 values 中的下标。
    col_ptr[j]\displaystyle \text{col\_ptr}[j]
  2. 列区间本列与下一列起点之间的元素都属于第 j 列。
    [ col_ptr[j], col_ptr[j+1] )\displaystyle [\,\text{col\_ptr}[j],\ \text{col\_ptr}[j+1]\,)
  3. 占用对称与 CSR 相同数量级，只是索引含义不同。
    SCSC≈(n+1+2 nnz)×b\displaystyle S_{\text{CSC}} \approx (n + 1 + 2\,\text{nnz}) \times b

格式对比选型

小张桌上摆着三本簿子：流水账、按行簿、按列簿。记账员喜欢流水账——写起来不用动脑；客户按行问时用按行簿最快；质检按列查时按列簿最优。哪本“最好”取决于你是谁。

技术选型同理。COO 构建最简单、元素可任意追加，但查询要线性扫描，适合“先快速收集非零元素再转换”的阶段（比如从数据文件读入、组装矩阵）。CSR 行访问高效、空间最紧凑（比 COO 少一整行整数数组），是数值计算和机器学习的主力。CSC 列访问高效，适合列优先算法、矩阵转置和按列切割。

选型口诀：先想“谁来读数据”。构建阶段用 COO 最省事；行操作为主用 CSR；列操作为主用 CSC；在大多数 AI 框架里，CSR 就是默认答案。

SCOO>SCSR≈SCSC,收益比例≈mn2 nnzS_{\text{COO}} > S_{\text{CSR}} \approx S_{\text{CSC}},\qquad \text{收益比例} \approx \frac{m n}{2\,\text{nnz}}
三者空间依次为 3nnz、2nnz+m+1、2nnz+n+1 个单元。稀疏收益比例 mn/(2nnz) 越大，说明稀疏存储越划算；而 COO/CSR/CSC 的取舍，核心看访问模式。
  1. COO 最大三个等长数组，多一套完整坐标开销。
    SCOO=3 nnz⋅b\displaystyle S_{\text{COO}} = 3\,\text{nnz} \cdot b
  2. CSR 居中用 m+1 项行指针换掉整行坐标。
    SCSR=(2 nnz+m+1)⋅b\displaystyle S_{\text{CSR}} = (2\,\text{nnz} + m + 1) \cdot b
  3. 选型靠访问模式按行访问选 CSR，按列访问选 CSC。
    按行访问→CSR,按列访问→CSC\displaystyle \text{按行访问} \to \text{CSR},\qquad \text{按列访问} \to \text{CSC}

稀疏矩阵乘法

货要发运时，小张要算“每排货的总重量”。按行簿让他很快列出一排所有的货，但笨办法是把整面墙的格子全看一遍再挑出有货的——空位再多，也要一格一格走过去。他想要的，是直接从簿子上的记录开算。

稀疏矩阵的核心计算“矩阵乘向量 y=Ax”，就是逐行求内积。用平凡做法遍历所有元素，复杂度是 O(mn)；用 CSR，只取每行非零元素，计算量正比于 nnz，空位置完全不用碰。具体算法是：对每一行 i，取 row_ptr[i] 到 row_ptr[i+1] 之间的非零元素，把 values[j] 与 x[col_ind[j]] 相乘并累加，得到 y[i]；矩阵乘矩阵则对 A 的每个非零元素，与 B 对应行的非零元素相乘，再用累加器按列合并。

小张发现，发货计算从“巡逻全场”变成“按单子点货”。整个仓库的效率来自一个朴素道理：别在空货架前浪费时间。这也是所有深度学习框架在稀疏场景下能跑得更快的原因。

yi=∑j: Aij≠0Aij xj,T=O(nnz)y_i = \sum_{j:\ A_{ij} \ne 0} A_{ij}\, x_j,\qquad T = O(\text{nnz})
公式表示 y 的第 i 个分量只需遍历 A 第 i 行里的非零项。总时间从 O(mn) 降到 O(nnz)，零元素占比越高，收益越大。
  1. 输出分量目标向量 y 的第 i 个元素。
    yi\displaystyle y_i
  2. 只遍历非零下标 j 只在 A 的第 i 行非零项中取。
    ∑j: Aij≠0\displaystyle \sum_{j:\ A_{ij} \ne 0}
  3. 乘加过程每个非零元素乘对应 x 分量再累加。
    Aij xj\displaystyle A_{ij}\, x_j
  4. 复杂度总操作数与 nnz 成正比，而不是 m×n。
    O(nnz)≪O(mn)\displaystyle O(\text{nnz}) \ll O(m n)

图与推荐应用

小张的仓库渐渐变成了一张关系网：哪些客户买过哪些货、哪些货架之间常被一起提货。他忽然意识到，这张网和稀疏矩阵长得一模一样——绝大多数“关系”都不存在，只有少量联系值得记录。

一张图可以用邻接矩阵表示：有边为 1（或权重），无边为 0。真实网络（社交、网页、分子）的边数远小于可能边数，邻接矩阵是典型稀疏矩阵。图神经网络（GNN）做节点特征聚合时，本质就是稀疏矩阵乘法——每个节点聚合邻居特征，用 CSR 存邻接矩阵才能避免内存爆炸。推荐系统同理：用户-物品交互矩阵里 99% 是“未购买/未评分”，用稀疏格式存交互记录，协同过滤才能在千万用户上算出相似度。

小张终于明白，稀疏矩阵不是课本上的冷门技巧，而是让“关系网”“交互史”这类天然稀疏的大数据能跑起来的底层基建。仓库、图、推荐系统，背后都是同一句话：只记有用的，才装得下整个世界。

非零占比=2∣E∣n2,∣E∣≪n2\text{非零占比} = \frac{2|E|}{n^2},\qquad |E| \ll n^2
n 个节点的图，邻接矩阵有 n² 个位置，只有 2|E| 个非零。社交网络里这个比例往往只有百万分之一量级，稠密矩阵根本装不下，稀疏存储是唯一选择。
  1. 矩阵规模邻接矩阵大小是 n²，非零个数是边数的两倍 2|E|。
    n2,2∣E∣\displaystyle n^2,\quad 2|E|
  2. 非零占比图越稀疏，占比越小。
    2∣E∣n2\displaystyle \frac{2|E|}{n^2}
  3. 规模意义n=100 万、E=1 亿时，占比约万分之一。
    2×1081012=2×10−4\displaystyle \frac{2 \times 10^8}{10^{12}} = 2 \times 10^{-4}

AI 应用场景

图神经网络中的邻接矩阵存储

阶段：数据预处理与特征聚合

解决的问题：图数据用稠密邻接矩阵存储时，百万节点就是万亿级内存，根本无法加载。用 CSR 存邻接矩阵只记录有边的位置，图卷积的消息聚合变成稀疏矩阵乘向量操作，训练才能跑起来。

具体案例：社交推荐中“好友关系图 + 用户特征”，把 1 亿人对 1 亿人的邻接矩阵用 CSR 存储，内存规模从 10¹⁶ 字节级别降到 GB 级，GCN 完成两跳邻居聚合只需毫秒级稀疏乘加。

推荐系统协同过滤

阶段：特征工程与相似度计算

解决的问题：用户-物品评分矩阵几乎全空，直接稠密存储不可行，计算相似度更是 O(n²) 灾难。用 COO 先收集点击日志、再转成 CSR，按行列快速取用户或物品的非零项，才能算余弦相似度、跑矩阵分解。

具体案例：视频平台“用户-播放记录”，100 万用户 × 10 万视频的矩阵非零占比仅 0.1%。用稀疏格式存储后，ALS 矩阵分解一个 epoch 从数小时降到十几分钟。

大规模稀疏线性系统求解

阶段：模型推理与数值优化

解决的问题：物理仿真、PageRank 都要解 Ax=b，而 A 极端稀疏。稠密消元会内存爆炸；用迭代法（如共轭梯度）每步只需一次稀疏矩阵乘向量——CSR 乘向量快，迭代就快。

具体案例：PageRank 把整个网页图转成稀疏矩阵，幂迭代每轮一次稀疏乘向量，几十轮收敛；稠密方法在 10 亿网页规模下从一开始就不可行。

Python 演示

python85 行
"""CSR 稀疏矩阵演示: 稠密矩阵转 CSR, 并实现乘向量与矩阵乘法"""  class CSRMatrix:    def __init__(self, values, col_ind, row_ptr):        self.values = values        self.col_ind = col_ind        self.row_ptr = row_ptr     def matvec(self, x):        """稀疏矩阵乘向量: y = A x, 复杂度 O(nnz)"""        n = len(self.row_ptr) - 1        y = [0.0] * n        for i in range(n):            s = 0.0            for j in range(self.row_ptr[i], self.row_ptr[i + 1]):                s += self.values[j] * x[self.col_ind[j]]            y[i] = s        return y     def spmm(self, other):        """稀疏矩阵乘稀疏矩阵: C = A x B, 用字典累加器合并"""        b_rows = []        for i in range(len(other.row_ptr) - 1):            row = {}            for j in range(other.row_ptr[i], other.row_ptr[i + 1]):                row[other.col_ind[j]] = other.values[j]            b_rows.append(row)        rows, cols, vals = [], [], []        for i in range(len(self.row_ptr) - 1):            acc = {}            for j in range(self.row_ptr[i], self.row_ptr[i + 1]):                a_col = self.col_ind[j]                a_val = self.values[j]                for b_col, b_val in b_rows[a_col].items():                    acc[b_col] = acc.get(b_col, 0.0) + a_val * b_val            for c in sorted(acc):                if acc[c] != 0.0:                    rows.append(i)                    cols.append(c)                    vals.append(acc[c])        return rows, cols, vals  def dense_to_csr(A):    """把稠密矩阵转为 CSR 三数组"""    values, col_ind, row_ptr = [], [], [0]    for row in A:        for j, v in enumerate(row):            if v != 0:                values.append(v)                col_ind.append(j)        row_ptr.append(len(values))    return CSRMatrix(values, col_ind, row_ptr)  def main():    A = [        [1, 0, 0, 2],        [0, 3, 0, 0],        [4, 0, 0, 5],        [0, 0, 6, 0],    ]    csr = dense_to_csr(A)    x = [1, 2, 3, 4]    print("values:", csr.values)    print("col_ind:", csr.col_ind)    print("row_ptr:", csr.row_ptr)    print("y = A x =", csr.matvec(x))     B = [        [0, 1, 0, 0],        [2, 0, 0, 0],        [0, 0, 3, 0],        [0, 0, 0, 4],    ]    csr_b = dense_to_csr(B)    rows, cols, vals = csr.spmm(csr_b)    print("C = A B (COO):")    for r, c, v in zip(rows, cols, vals):        print("  A[%d][%d] = %g" % (r, c, v))  if __name__ == "__main__":    main()
目的：完整演示“稠密矩阵 → CSR 三数组”的转换，并用 CSR 实现稀疏矩阵乘向量和稀疏矩阵乘矩阵，输出与手工推导一致。

常见误区

误区CSR 压缩完还是一个矩阵，我照样写 A[i][j] 就能取到第 i 行第 j 列的值，只是省了内存而已。

正解CSR 是三个一维数组，没有二维下标。要取 A[i][j]，先查 row_ptr[i] 到 row_ptr[i+1] 的区间，再在其中线性搜索列号等于 j 的项，找不到说明该位置是 0——访问是 O(k) 而不是 O(1)。它牺牲了“随机访问”，换来“按行遍历 + 省内存”，所以代码里必须改用“扫一行”的思维。

为何常见：我们学矩阵时一直用 a[i][j] 下标，天然以为压缩只是“删掉零再拼回来”，忽略了索引结构带来的访问方式变化。

误区零元素这么多，不管什么操作，稀疏格式肯定比稠密格式快，内存也肯定省。

正解稀疏格式多了索引数组和查找开销。矩阵太小（如 10×10）或非零占比不低（如 30%）时，CSR 可能比稠密更费内存、更慢；省略的零存储有限，索引开销反而占大头。工程上通常要稀疏度超过 90% 才值得上稀疏格式。

为何常见：“存得少算得快”的口号让人忽略了 overhead——任何压缩都有元数据成本，小矩阵时元数据占比反而更高。

误区反正都是记录非零元素和位置，三种格式跑什么算法都一样，随便选一个就行。

正解三种格式的索引结构决定了访问模式：CSR 一行一个区间扫得飞快，按列访问却要反复跳指针；CSC 反之；COO 定位最灵活但查询需全表扫描，多用于构建中间态。选错格式，比如图神经网络按行聚合邻居时用 CSC，会明显变慢。

为何常见：只看到“存了哪些信息”，忽略“信息如何组织”，不理解索引结构决定缓存友好性和时间复杂度。

误区我在稠密乘法里加个 if，碰到零就 continue，这不就是稀疏乘法了吗？

正解加 if 的稠密循环仍然扫过全部 m×n 个元素，复杂度还是 O(mn)。真正的稀疏乘法只遍历非零项的索引区间，复杂度 O(nnz)。必须在数据结构和循环上都按非零组织，才能把“扫全场”变成“按单点货”。

为何常见：从“结果”看两者输出相同，从“过程”看忽略了遍历策略——而稀疏加速的本质正是改变遍历对象，不改变遍历对象就谈不上加速。

误区存稀疏矩阵就是留下非零值，变成一个更小的普通矩阵，需要时再把零补回来。

正解只留数值会丢失位置信息，无法还原也无法参与运算。必须同时记录每个非零值在原始矩阵中的行列位置（COO），或保存能推导出位置的索引结构（CSR/CSC）。“压缩”不是“裁剪”，是“带坐标的记账”。

为何常见：直观上“删零”最好理解，但忽略了坐标是元素身份的一部分，这也是为什么稀疏格式总需要两套索引数组。

面试题

Q1. 通常认为矩阵达到什么程度就可以算“稀疏矩阵”？

单选题 · easy

  • A.非零元素占比超过 50%
  • B.零元素占比超过 70%
  • C.零元素占比超过 90%← 正确答案
  • D.非零元素占比超过 90%

答案：C。稀疏没有唯一标准，但工程上通常零元素占 90% 以上（稀疏度 ρ>90%）才值得用稀疏格式存储。A、D 说的都是“非零多”该算稠密，B 的 70% 还不够稀疏，无法显著节省空间。

Q2. COO 坐标格式用三个等长数组记录每个非零元素，这三个数组分别是？

单选题 · easy

  • A.行号、列号、数值← 正确答案
  • B.行偏移、列索引、数值
  • C.列偏移、行索引、数值
  • D.对角元、非零元、零元

答案：A。COO 像流水账，每条记录写“行号、列号、数值”一一对应。B 是 CSR 的三数组，C 是 CSC 的三数组，D 不是标准稀疏存储格式。

Q3. 对 m 行矩阵做 CSR 压缩，行偏移数组 row_ptr 的长度应该是？

单选题 · easy

  • A.长度等于矩阵行数 m
  • B.长度等于行数加一 m+1← 正确答案
  • C.长度等于非零数 nnz
  • D.长度等于非零数加一 nnz+1

答案：B。row_ptr 需要 m+1 个位置：row_ptr[i] 是第 i 行起点，row_ptr[i+1] 是下一行起点（即本行终点），最后用 row_ptr[m]=nnz 收尾。少了最后一项就无法表示最后一行的区间。

Q4. CSR 中 row_ptr=[0,2,3,5,6]，第 2 行（从 0 编号）的非零元素在 values 里的下标范围是？

单选题 · mid

  • A.下标 2 到 3 之前的半开区间
  • B.下标 3 到 5 之前的半开区间← 正确答案
  • C.下标 0 到 2 之前的半开区间
  • D.下标 5 到 6 之前的半开区间

答案：B。第 i 行对应 [row_ptr[i], row_ptr[i+1])。第 2 行取 [row_ptr[2], row_ptr[3]) = [3,5)，即下标 3、4 两个元素。A、C、D 分别是第 1、0、3 行的区间，属于位置错位。

Q5. 相比稠密矩阵，用 CSR 存储稀疏矩阵的优势包括哪些？

多选题 · mid

  • A.大幅降低零元素的存储开销← 正确答案
  • B.任意位置 a[i][j] 随机访问更快
  • C.乘向量时天然跳过零元素运算← 正确答案
  • D.所有矩阵运算都比稠密更快

答案：AC。CSR 只存非零元和索引，A 对；乘向量按 row_ptr 取每行非零元，跳过零运算，C 对。B 错：CSR 没有 O(1) 二维下标，随机查 a[i][j] 反而要查索引；D 错：小矩阵或非零占比高时索引开销会让稀疏更慢。

Q6. 构建 CSR 时，row_ptr 由每行非零个数累加得到，这种累加结构本质上是？

单选题 · mid

  • A.前缀和数组← 正确答案
  • B.哈希表结构
  • C.单链表结构
  • D.平衡二叉树

答案：A。row_ptr[i+1] = row_ptr[i] + 第 i 行非零个数，是典型的前缀和（prefix sum）。前缀和能用 O(1) 时间定位任意一行的起止区间；哈希表、链表、二叉树都无法线性定位连续区间。

Q7. 高效稀疏矩阵乘法的关键技巧包括哪些？

多选题 · hard

  • A.把矩阵补成稠密方阵再运算
  • B.只遍历 A 的非零元素参与乘加← 正确答案
  • C.用累加器字典合并部分和← 正确答案
  • D.用随机数填充零以保持形状

答案：BC。稀疏乘法只取 A 的非零元，与 B 对应行的非零元相乘（B 对），再把部分和按列号在累加器中合并（C 对）。A 补零、D 填零都会重新引入海量零运算，与稀疏初衷背道而驰。

Q8. 10000×10000 矩阵、nnz=1e4，CSR 空间约 (2nnz+m+1) 个单元，相比稠密矩阵约为多少？

单选题 · hard

  • A.大约是稠密空间的 3×10^-6
  • B.大约是稠密空间的 3×10^-4← 正确答案
  • C.大约是稠密空间的 3×10^-2
  • D.大约是稠密空间的 3×10^-1

答案：B。稠密要存 10⁸ 个单元，CSR 约为 2×10⁴+10⁴+1≈3×10⁴ 个单元，比值 3×10⁴/10⁸=3×10⁻⁴。B 正确，其余选项量级都不对。这直观体现了“存得少”的数量级优势。

Q9. 哪些场景应该优先选 CSC 压缩列格式？

多选题 · hard

  • A.频繁按列提取数据← 正确答案
  • B.频繁按行提取数据
  • C.列优先的数值迭代计算← 正确答案
  • D.行优先的矩阵乘法

答案：AC。CSC 用列偏移定位每一列，按列访问只需 O(1) 定位加该列非零数遍历，A、C 对。按行访问和行优先计算都要跨列跳指针，B、D 更适合 CSR。

Q10. n×n 矩阵零占比 99%（nnz≈0.01n²），y=Ax 用 CSR 实现，运算量约为稠密实现的多少？

单选题 · extreme

  • A.与稠密实现完全一样
  • B.约是稠密实现的百分之一← 正确答案
  • C.约是稠密实现的千分之一
  • D.约是稠密实现的万分之一

答案：B。稠密乘法要遍历 n² 个元素，CSR 只遍历 nnz≈0.01n² 个非零元，实际运算量约为百分之一。注意：大 O 记号下 0.01n² 仍是 O(n²)，但实际乘法次数按比例就是 1/100，这正是稀疏格式的意义所在。