第 06 讲

稀疏矩阵及其压缩存储

稀疏矩阵是矩阵压缩里很实用的一类:非零元很少,位置又没有规律,不能再用「下标公式」直接压平。 本章只保留稀疏矩阵这一节:三元组顺序表、朴素转置与快速转置(num[] / cpot[]), 以及工程里常见的稀疏结构选型。

预计 45 分钟 前置:数组与矩阵的基本概念 关键词:稀疏矩阵 · 三元组 · 快速转置 · num/cpot

6.1 稀疏矩阵及其压缩存储

6.1.1 什么是稀疏矩阵:公式法为什么在这里失灵

稀疏矩阵(sparse matrix)是指非零元素个数远小于矩阵元素总数的矩阵。 国内教材通常给出一个量化标准:若非零元个数占元素总数的比例不超过 5% (即 tu / (mu × nu) ≤ 0.05),就认为它是稀疏的。

这个「5%」只是个工程上的经验界,不要当成数学定义去较真。真正要抓住的是两点:

现在回答关键问题:为什么不能像规整矩阵那样,用「下标公式」直接算出某个元素的位置?

如果非零元的位置有规律(例如只落在某几条对角线上),可以用下标不等式描述「哪些元素要存」, 再用等差数列算出「前面有多少个元素」,最终得到闭式的 k = f(i,j)。

而一般稀疏矩阵的零元素是东一个西一个、毫无规律的:它可能出现在 (0,3),也可能出现在 (17,92),两个非零元之间没有任何位置上的约束关系。 既然写不出不等式,也就数不出「前面有多少个」,公式法直接失灵。

于是只剩一条路:把「位置」也存下来 既然位置算不出来,那就把位置和值一起存:每个非零元存成一个 (行号, 列号, 值) 的三元组。这样虽然每个元素多花了两个整数的开销, 但比起「用 mu × nu 个单元去存一大堆 0」,当稀疏度足够低时仍然是稳赚的。
代价是:按下标随机取值(随机存取)的能力基本上没有了——要找一个元素, 只能按某种顺序去查找。

6.1.2 三元组顺序表:最朴素也最常用的方案

三元组顺序表(sequential list of triples)是稀疏矩阵最经典的顺序存储结构。 它的定义短得可以背下来:用一个结构体数组,按行优先顺序 (行号升序;同一行内列号升序)存放全部非零元,每个元素包含 row、col、value 三个域; 另外用 mu、nu、tu 记录行数、列数和非零元个数。

为什么要规定「按行优先有序」?因为有序带来三个直接好处: 可以按行处理(矩阵加法、乘法都要按行归并)、转置时能一次定位、 打印和调试时输出可读。代价是插入或修改一个元素时可能要搬移后续元素—— 和顺序表一样的老毛病。

稀疏矩阵 M(4 × 5,20 个元素,6 个非零元)与它的三元组顺序表 j=0 1 2 3 4 i=0 0 3 0 0 7 i=1 0 0 5 0 0 i=2 4 0 0 6 0 i=3 0 2 0 0 0 mu = 4, nu = 5, tu = 6 用二维数组存要 20 个单元;三元组表要 6 × 3 = 18 个整数 这个教学例子还不够稀疏(30%),真实场景里 nnz 常在 1% 以下, 那时三元组表的优势是压倒性的。 三元组顺序表 data[](按行优先有序) 下标 row col value 0 0 1 3 1 0 4 7 2 1 2 5 3 2 0 4 4 2 3 6 5 3 1 2 行号必须升序:0,0,1,2,2,3;同一行内列号也必须升序:1 < 4,0 < 3。 正是这个「有序」,让转置、加法、乘法都能按行归并着做。
图 6-1 稀疏矩阵的三元组顺序表:每个非零元存位置 + 值,整体按行优先有序

结构定义与「朴素转置」的实现在下面。请特别留意朴素转置的复杂度是怎么来的—— 它其实就是「按列扫描 + 全表查找」这个笨办法的代价:

#include <bits/stdc++.h>
using namespace std;

/* ============================================================
   稀疏矩阵的三元组顺序表 + 朴素转置(竞赛写法:全局数组 + 自由函数)
   三元组:(row, col, value),按"行优先"排列(行号升序,同行按列号升序)。
   struct Triple 只描述"一个非零元长什么样",属于结点型,保留;
   矩阵本体就是一个三元组数组 + 三个计数器(mu / nu / tu),不必再套一层 struct。

   朴素转置的思路:
       转置后 T 的第 col 行 = M 的第 col 列。
       于是依次枚举 M 的每一列 col = 0, 1, ..., nu-1,
       为了找到该列的所有非零元,每次都要把整个三元组表扫一遍。
       扫描次数 = nu * tu,所以时间复杂度 O(nu * tu)。
   ============================================================ */

struct Triple {                 /* 结点型:一个非零元 = 行号 + 列号 + 值 */
    int r, c, v;
};

const int MAXT = 100;           /* 数组开够:本题非零元个数 ≤ 100(竞赛里按题目上限开) */

Triple t[MAXT];                 /* 转置结果 T 的三元组表 */
int mu, nu, tu;                 /* T 的行数、列数、非零元个数 */

/* 往 T 里追加一个非零元 —— 三元组表的"插入"就是这一步 */
void pushTriple(int r, int c, int v) {
    t[tu].r = r; t[tu].c = c; t[tu].v = v;
    ++tu;
}

void printMatrix(const char* name) {
    cout << name << " : " << mu << " x " << nu << ", tu = " << tu << "\n";
    for (int p = 0; p < tu; ++p)
        cout << "   [" << p << "] (" << t[p].r << ", " << t[p].c
             << ", " << t[p].v << ")\n";
}

/* 朴素转置:把 src(stu 个非零元、smu 行 snu 列)转置后存进全局的 t[],O(snu * stu) */
void naiveTranspose(const Triple src[], int stu, int smu, int snu) {
    mu = snu; nu = smu;                 /* 行列互换 */
    tu = stu;
    if (stu == 0) return;
    int q = 0;
    for (int col = 0; col < snu; ++col)               /* 枚举原矩阵的每一列 */
        for (int p = 0; p < stu; ++p)                 /* 每列都重扫整个三元组表 */
            if (src[p].c == col) {
                t[q].r = src[p].c;                    /* 行列互换 */
                t[q].c = src[p].r;
                t[q].v = src[p].v;
                ++q;
            }
}

int main() {
    /* 4 行 5 列,6 个非零元;总元素 20 个,稀疏度 30%(教学用小例子,真实场景常 < 5%) */
    Triple M[MAXT];
    int Mtu = 0;
    M[Mtu++] = {0, 1, 3};
    M[Mtu++] = {0, 4, 7};
    M[Mtu++] = {1, 2, 5};
    M[Mtu++] = {2, 0, 4};
    M[Mtu++] = {2, 3, 6};
    M[Mtu++] = {3, 1, 2};

    /* 为了能同框打印两个矩阵,把 M 的内容也放进全局表里,用 printMatrix 输出 */
    mu = 4; nu = 5; tu = 0;
    for (int p = 0; p < Mtu; ++p) pushTriple(M[p].r, M[p].c, M[p].v);
    printMatrix("M");

    naiveTranspose(M, Mtu, 4, 5);
    printMatrix("T = M^T (naive transpose)");
    return 0;
}

6.1.3 转置:朴素算法为什么慢

矩阵转置(transpose)在数学上很简单:T[j][i] = M[i][j]。 对三元组表来说,把每个三元组的 row 和 col 交换一下就行。 但请注意:光交换还不够。交换之后,数组里的顺序变成了「按原来的列优先」, 不再是「按行优先有序」了,而我们的结构约定要求它必须有序,所以还得重新排。

朴素算法的想法是:不去排序,而是按目标顺序直接产生。 转置后 T 的第 col 行来自 M 的第 col 列, 于是我按 col = 0, 1, …, nu−1 的顺序,依次把 M 中所有列号为 col 的三元组找出来、交换行列、追加到 T 里。 因为「先处理列号小的」,产出的 T 自然就是按行有序的。

问题在于「找出来」这一步:为了找第 col 列的所有非零元, 我们必须把整个三元组表从头到尾扫一遍。一共有 nu 列, 每列都扫 tu 个元素,于是:

时间复杂度 = O(nu × tu) 空间复杂度 = O(tu)(存放结果)

这个复杂度有多糟?考虑一个 n × n 的稀疏矩阵,若 tu 与 n 同阶 (比如每行平均只有常数个非零元),那 O(nu × tu) = O(n²)—— 和直接把稠密二维数组转置一遍一样慢,等于白折腾。显然需要改进。

6.1.4 快速转置:num[] 与 cpot[] 的递推

快速转置(fast transpose)的核心洞察只有一句话: 如果能事先知道「转置后第 col 行的第一个元素应该放在哪个位置」, 那么只需要扫一遍 M.data,边扫边放,转置就完成了。

为此需要两个辅助数组,长度都是 nu(转置后的行数):

num[col]
M 中第 col 列的非零元个数。 因为 M 的列就是 T 的行,所以它同时也是 T 中第 col 行的元素个数。
cpot[col]
T 中第 col 行的第一个元素应该放在 T.data 的哪个下标处(cpot = column position)。

num 很好求:扫一遍 M.data,对每个三元组 ++num[它的 col] 即可。 cpot 则用前缀和递推出来:

cpot[0] = 0
cpot[col] = cpot[col−1] + num[col−1] (col = 1, 2, …, nu−1)

这两行的意思很直白:第 col 行的起点 = 第 col−1 行的起点 + 第 col−1 行有多少个元素。 就像排队时分座位:前面那队有多少人,我这队就从下一个空位开始坐。

用图 6-1 里的矩阵 M 实际推一遍(mu=4, nu=5, tu=6):

col01234说明
num[col] 12111 M 的第 0 列只有 (2,0,4);第 1 列有 (0,1,3) 与 (3,1,2)……
cpot[col] 01345 逐项递推,见下
快速转置的预处理:num[] 统计每列有多少个,cpot[] 前缀和算出每行的落点 列号 col 0 1 2 3 4 num[col] 1 2 1 1 1 合计 6 = tu ✅ cpot[col] 0 1 3 4 5 5 + 1 = 6 = tu ✅ +num[0]=+1 +num[1]=+2 +1 +1 递推式:cpot[0] = 0;cpot[col] = cpot[col−1] + num[col−1] —— 第 col 行的起点 = 上一行起点 + 上一行元素个数 有了 cpot[],转置时每读到一个三元组就知道该放哪儿,整趟只需 O(nu + tu)。
图 6-2 快速转置的两个辅助数组:num[] 统计个数,cpot[] 前缀和算出每行的起始落点

快速转置的完整实现如下,三个步骤在注释里标了序号:

易错:最后一遍扫描的顺序不能乱 第三步必须按 M.data 原有的顺序(也就是行优先序)从头扫到尾。 为什么呢?因为 M.data 是按行号升序排列的, 所以当同一列(即 T 的同一行)的多个非零元被依次读到时, 它们的行号也一定是递增的,落进 T 的同一行后自然保持列号递增, 转置结果就仍然是有序的。
如果你自作聪明地按别的顺序扫描,转置结果的「行内有序」性质就没了, 后续的加法、乘法都会出错。
考点:两种转置的复杂度对比
算法时间辅助空间关键动作
朴素转置O(nu × tu)O(1)双重循环:外层枚举列,内层扫全表
快速转置O(nu + tu)O(nu)用 num/cpot 换时间(典型的空间换时间)
注意快速转置的空间是 O(nu),不是 O(1)—— 考试问「辅助空间」时要答 O(nu)(有些书写 O(n),n 指列数)。
本节从略快速转置的完整代码从略:掌握 num[] / cpot[] 的递推思路即可。

6.1.5 动画演示:稀疏矩阵到三元组表的转换

最后用一个动画把「扫描稀疏矩阵、生成三元组表」的过程走一遍。 请留意两点:扫描顺序是行优先(保证了结果有序), 以及零元素被直接跳过(这就是省空间的来源):

四种稀疏结构的选型建议
  • 只读、要转置、要考试 → 三元组顺序表(写起来最简单,考试也只考它)。
  • 要按行反复访问 → 行逻辑链接的顺序表(加一个 rpos[],改动最小、收益最大)。
  • 结构频繁增删 → 十字链表。
  • 真刀真枪做数值计算 → CSR / CSC,配合稀疏 BLAS 库。