稀疏矩阵及其压缩存储
稀疏矩阵是矩阵压缩里很实用的一类:非零元很少,位置又没有规律,不能再用「下标公式」直接压平。
本章只保留稀疏矩阵这一节:三元组顺序表、朴素转置与快速转置(num[] / cpot[]),
以及工程里常见的稀疏结构选型。
6.1 稀疏矩阵及其压缩存储
6.1.1 什么是稀疏矩阵:公式法为什么在这里失灵
稀疏矩阵(sparse matrix)是指非零元素个数远小于矩阵元素总数的矩阵。
国内教材通常给出一个量化标准:若非零元个数占元素总数的比例不超过 5%
(即 tu / (mu × nu) ≤ 0.05),就认为它是稀疏的。
这个「5%」只是个工程上的经验界,不要当成数学定义去较真。真正要抓住的是两点:
- 稀疏是「比例」概念,不是「规模」概念。一个 1000000 × 1000000 的矩阵, 如果每个位置都非零,它依然是稠密矩阵;反过来,一个 10 × 10 的矩阵只要有 2 个非零元, 按比例说它也是稀疏的(只是这时候压缩反而可能不划算)。
- 稀疏矩阵的价值在于「省空间」和「省时间」。工程上(有限元、图计算、推荐系统) 动辄百万阶的稀疏矩阵,用稠密方式存根本开不出内存;而很多算法(比如稀疏矩阵向量乘) 可以做到只与非零元个数成正比,与矩阵阶数几乎无关。
现在回答关键问题:为什么不能像规整矩阵那样,用「下标公式」直接算出某个元素的位置?
如果非零元的位置有规律(例如只落在某几条对角线上),可以用下标不等式描述「哪些元素要存」,
再用等差数列算出「前面有多少个元素」,最终得到闭式的 k = f(i,j)。
而一般稀疏矩阵的零元素是东一个西一个、毫无规律的:它可能出现在
(0,3),也可能出现在 (17,92),两个非零元之间没有任何位置上的约束关系。
既然写不出不等式,也就数不出「前面有多少个」,公式法直接失灵。
(行号, 列号, 值) 的三元组。这样虽然每个元素多花了两个整数的开销,
但比起「用 mu × nu 个单元去存一大堆 0」,当稀疏度足够低时仍然是稳赚的。
代价是:按下标随机取值(随机存取)的能力基本上没有了——要找一个元素, 只能按某种顺序去查找。
6.1.2 三元组顺序表:最朴素也最常用的方案
三元组顺序表(sequential list of triples)是稀疏矩阵最经典的顺序存储结构。
它的定义短得可以背下来:用一个结构体数组,按行优先顺序
(行号升序;同一行内列号升序)存放全部非零元,每个元素包含
row、col、value 三个域;
另外用 mu、nu、tu 记录行数、列数和非零元个数。
为什么要规定「按行优先有序」?因为有序带来三个直接好处: 可以按行处理(矩阵加法、乘法都要按行归并)、转置时能一次定位、 打印和调试时输出可读。代价是插入或修改一个元素时可能要搬移后续元素—— 和顺序表一样的老毛病。
结构定义与「朴素转置」的实现在下面。请特别留意朴素转置的复杂度是怎么来的—— 它其实就是「按列扫描 + 全表查找」这个笨办法的代价:
#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 个元素,于是:
这个复杂度有多糟?考虑一个 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 则用前缀和递推出来:
这两行的意思很直白:第 col 行的起点 = 第 col−1 行的起点 + 第 col−1 行有多少个元素。 就像排队时分座位:前面那队有多少人,我这队就从下一个空位开始坐。
用图 6-1 里的矩阵 M 实际推一遍(mu=4, nu=5, tu=6):
| col | 0 | 1 | 2 | 3 | 4 | 说明 |
|---|---|---|---|---|---|---|
| num[col] | 1 | 2 | 1 | 1 | 1 | M 的第 0 列只有 (2,0,4);第 1 列有 (0,1,3) 与 (3,1,2)…… |
| cpot[col] | 0 | 1 | 3 | 4 | 5 | 逐项递推,见下 |
cpot[0] = 0(人为约定:第一行从 0 号位开始)。cpot[1] = cpot[0] + num[0] = 0 + 1 = 1。cpot[2] = cpot[1] + num[1] = 1 + 2 = 3。cpot[3] = cpot[2] + num[2] = 3 + 1 = 4。cpot[4] = cpot[3] + num[3] = 4 + 1 = 5。- 校验:
cpot[4] + num[4] = 5 + 1 = 6 = tu✅ 刚好把 6 个位置分配完, 这也是一条常用的自检规则。
快速转置的完整实现如下,三个步骤在注释里标了序号:
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 指列数)。
6.1.5 动画演示:稀疏矩阵到三元组表的转换
最后用一个动画把「扫描稀疏矩阵、生成三元组表」的过程走一遍。 请留意两点:扫描顺序是行优先(保证了结果有序), 以及零元素被直接跳过(这就是省空间的来源):
- 只读、要转置、要考试 → 三元组顺序表(写起来最简单,考试也只考它)。
- 要按行反复访问 → 行逻辑链接的顺序表(加一个
rpos[],改动最小、收益最大)。 - 结构频繁增删 → 十字链表。
- 真刀真枪做数值计算 → CSR / CSC,配合稀疏 BLAS 库。