稀疏矩阵的快速转置算法
三元组表示法
有矩阵A
| 2 | 0 | 0 |
|---|---|---|
| 1 | 0 | 0 |
| 0 | 3 | 0 |
三元组表示为
| Element | row | col | value |
|---|---|---|---|
| Elem[0] | 0 | 0 | 2 |
| Elem[1] | 1 | 0 | 1 |
| Elem[2] | 2 | 1 | 3 |
转置
在讨论转置之前，应注意到三元组Elem对元素的存储顺序有要求：按照行序存储，同一行按列序存储。
这也跟元素在内存中的存储顺序一致。
若忽略这个要求，求其转置只需要把Elem内的元素行列号交换就可以了。而为了达到对存储顺序的要求，有两种转置算法。
1. 简单转置算法
按照数学方法一列一列转换：在三元组中找出每列元素，交换行列号，按行顺序依次放入三元组。
查找每列元素需要扫描三元组cols遍，扫描三元组需要O(n)，复杂度O(cols*n)。
是为保证转置后三元组元素的顺序，小心翼翼一列列转换的笨方法。
2. 快速转置算法
尝试直接计算出元素位置。
这个问题可以转变为有m列元素，每列有若干个非零元素，将其按顺序放入一维数组中，求每个元素的位置。
三列，第1列：3个，第2/3列：2个
如图，只需求出每出各列第一个元素即可得到列内全部元素的位置。
而第一个元素可以累加前面各列元素的个数求得。
根据上述思想，可建立如下表，A_col表示原列号，num表示每列元素个数，B_idx表示每列第一个元素所在位置。
| A_col | 0 | 1 | 2 |
|---|---|---|---|
| num | 2 | 1 | 0 |
| B_idx | 0 | 0+2=2 | 1+2=3 |
时间复杂度O(n)。
