稀疏矩阵的压缩存储/快速逆置/基本运算

2017-04-25 18:40 阅读 916 次 评论 0 条

稀疏矩阵的压缩存储

M*N的矩阵,矩阵中有效值得个数远小于无效值的个数,且这些数据的分布没有规律。如下图所示的矩阵就是一个稀疏矩阵。

图中不难看出,0属于无效元素,且有效元素之间不存在任何关联,在矩阵中的分布也没有任何规律。

压缩存储值存储极少数的有效数据。使用{row,col,value}三元组(Trituple)存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放。

当我们遍历矩阵的时候,需要将有效值存储起来,这里就用到了右图所示的三元组,将有效元素的行、列、值保存起来,忽视掉无效元素。

稀疏矩阵的逆置

稀疏矩阵的逆置也就是将矩阵的行、列进行交换,即原矩阵的[i][j]和[j][i]位置上的数据对换。

这里我们使用行优先来存储有效元素,可以使用一个顺序表类型的迭代器遍历三元组,遍历过程如下:

将上面遍历的结构存储于_sm顺序表中,即存储稀疏矩阵中的有效元素。当我们进行逆置时,需将矩阵的行、列、无效值赋给当前的顺序表,对行与列取反赋值,即行表示列,列表示行。

但是很遗憾,当你看了代码之后,你会发现其时间复杂度f(n)= O(列数*有效元素的个数+有效元素的个数) = O(M*N)。这样的复杂度遍历一次需要的时间也是可想而知,因此就引入了快速转置。

稀疏矩阵的快速逆置

快速逆置是用空间来换时间的解决方案。这里我们创建了两个数组:

我们通过遍历一次存放有效元素的顺序表,即得到pRowCount的大小;pRowStart每一行的起始位置只需要上一行的起始位置+上一行有效元素的个数,当然,第一行(下标为0)的起始地址为0。

上图很好的说明了快速逆置的设计思想,我们遍历了一次顺序表,用来计算每行有效元素的个数,又遍历了一次矩阵的列来统计每行的起始位置。因此时间复杂度为f(n)= O(M+N),比普通的逆置快速了不少。

稀疏矩阵的加法与减法

加法与减法的算法理念一致,对两个同行同列的矩阵的对应坐标上的元素进行加减运算。当然直接遍历两个矩阵进行相加减是可以实现的,但是这样的算法时间复杂度太高,不推荐使用。既然我们都有了三元组存储有效元素的理念,我们就可以用三元组的思想来完成基本运算。

源代码及注释

这就是稀疏矩阵的各项操作,当然,如果不限麻烦,你可以试试写一写稀疏矩阵的乘法和除法,掌握了思想想必写起来也不会太过麻烦,动手试试吧。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:稀疏矩阵的压缩存储/快速逆置/基本运算 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情