稀疏矩阵的压缩存储及转置算法

发布时间:2020-07-16 22:39:47 作者:马尾和披肩
来源:网络 阅读:1683

只怪 博主智商无下限,花了一个周末终于把系数矩阵的压缩存储及其转置给弄明白了,所以今天就和大家分享一下我的学习过程啦!!!

稀疏矩阵是指矩阵中大多数元素为零的矩阵,从直观上讲,非零元素的个数低于总元素的30%时,这样的矩阵称为稀疏矩阵。

稀疏矩阵的压缩存储及转置算法


1.稀疏矩阵的三元组组表示法

对于稀疏矩阵的压缩存储,采取只存储非零元素的方法,由于稀疏矩阵中非零元素的分布没有规律,所以呢???在存储非零元素的时候必须给每个元素做个标记(非零元素在矩阵中所处的行号和列号)。

稀疏矩阵的压缩存储及转置算法

//稀疏矩阵三元组表类型的定义
struct Triple
{
T _value;
size_t _row;
size_t _col;

Triple(size_t row=0,size_t col=0,const T& value=T())
:_value(value)
,_row(row)
,_col(col)
{}
};


(1)Triple是包含三个域的结构体类型,其元素是为了存储非零元的三元组


2.稀疏矩阵的压缩存储

就上图给出的矩阵而言,运用三元组压缩存储的方法存储后的结果是酱紫滴


稀疏矩阵的压缩存储及转置算法

源代码是酱紫滴:


//用三元组表示实现稀疏矩阵的压缩存储
	SpareMatrix(T* a,size_t m,size_t n,const T& invalid)
		:_rowsize(m)
		,_colsize(n)
		,_invalid(invalid)
	{
		for(size_t i=0;i<m;i++)
		{
			for(size_t j=0;j<n;j++)
			{
				if(a[i*n+j]!=invalid)
				{
				_a.push_back(Triple<T>(i,j,a[i*n+j]));
				}
			}
		}
	
	}



3.稀疏矩阵的列序递增转置法


采用被转置矩阵按照列序递增的的顺序进行转置,并依此将将其送入转置后的三元组表中,这样子的话转置后的三元组表恰好是以行序号为主的哦 。

具体做法:



(1)找出转置后的第一行元素:第一遍从头至尾扫描三元组表,找出所有_col为1的三元组,转置后按顺序放到开辟好新的三元组表中

(2)找出转置后的第二行元素:第一遍从头至尾扫描三元组表,找出所有_col为2的三元组,转置后按顺序放到开辟好新的三元组表中

 源代码是酱紫滴:
//稀疏矩阵的转置
SpareMatrix<T> Transport()
{
      SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  //给构建好的匿名对象开辟空间,但是不改变size的大小,开辟后初始化的值为原来的。
  tmp._a.reserve(_a.size());
  for(size_t i=0;i<_colsize;i++)
  {
  size_t index=0;
  for(index=0;index<_a.size();index++)
  {
   if(_a[index]._col==i)
   {
   Triple <T> tp;
   tp._row=_a[index]._col;
   tp._col=_a[index]._row;
   tp._value=_a[index]._value;
   tmp._a.push_back(tp);
   }
  }
  }
  return tmp;
  
}

注释:虽然构建了一个 SpareMatrix<T> tmp类型的对象但是并没有给它开辟和_a一样大小的空间,所以要调用reserve或者resize两个函数中任意一个即可,否则当你在运行程序的时候会奔溃哦,智商无下线的博主昨天就是犯了这个错误,程序跑起来的时候,老是弹出这样的框框:

稀疏矩阵的压缩存储及转置算法

最后调试了好久才发现问题所在稀疏矩阵的压缩存储及转置算法气死宝宝啦,



算法分析:

算法主要耗费在双重循环中,其时间复杂度为o(_colsize*_a.size());


4.稀疏矩阵的一次定位快速转置算法

 

算法思想:

(1)计算待转置矩阵三元组表中每一列非零元素的个数,即转置后矩阵三元组表每一行中非零元素的个数。

(2)计算待转置矩阵每一列中第一个非零元素三元组表中的具体位置。

源代码是酱紫滴:

/稀疏矩阵的快速转置
SpareMatrix<T> FastTransport()
{
  SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  int* rowcounts=new int[tmp._rowsize];
  int* rowstart=new int[tmp._rowsize];
  memset(rowcounts,0,sizeof((int*)_colsize));
  memset(rowstart,0,sizeof((int*)_colsize));
  size_t index=0;
 
  //计算待转置矩阵每一列非零元素的个数
  while(index<_a.size())
  {
  rowcounts[_a[index]._col]++;
  index++;
  }


//计算待转置矩阵每一列第一个非零元素在三元组表中的位置
rowstart[0]=0;
for(size_t i=1;i<_colsize;i++)
{
rowstart[i]=rowstart[i-1]+rowcounts[i-1];
}

index=0;
//给_a的匿名对象开辟_a大小的空间
    tmp._a.resize(_a.size());
while(index<_a.size())
{/*
size_t rowindex=_a[index]._col;*/
int& start=rowstart[_a[index]._col];

Triple<T> tp;
tp._value=_a[index]._value;
tp._row=_a[index]._col;
tp._col=_a[index]._row;
tmp._a[start++]=tp;
index++;
}
return tmp;
}



算法分析:

一次定位快速转置算法时间主要耗费在三个并列的循环中,因而时间复杂度为o(_a.size+_colsize).

 

完整的源代码:


 

//稀疏矩阵的压缩存储
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
//稀疏矩阵三元组表类型的定义
struct Triple
{
T _value;
size_t _row;
size_t _col;

Triple(size_t row=0,size_t col=0,const T& value=T())
:_value(value)
,_row(row)
,_col(col)
{}

};
template<typename T>
//稀疏矩阵
class SpareMatrix
{
public:

SpareMatrix()
:_rowsize(0)
,_colsize(0)
,_invalid(0)
{}
//用三元组表示实现稀疏矩阵的压缩存储
SpareMatrix(T* a,size_t m,size_t n,const T& invalid)
:_rowsize(m)
,_colsize(n)
,_invalid(invalid)
{
for(size_t i=0;i<m;i++)
{
for(size_t j=0;j<n;j++)
{
if(a[i*n+j]!=invalid)
{
_a.push_back(Triple<T>(i,j,a[i*n+j]));
}
}
}

}
//稀疏矩阵的转置
SpareMatrix<T> Transport()
{
      SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  //给构建好的匿名对象开辟空间,但是不改变size的大小,开辟后初始化的值为原来的。
  tmp._a.reserve(_a.size());
  for(size_t i=0;i<_colsize;i++)
  {
  size_t index=0;
  for(index=0;index<_a.size();index++)
  {
   if(_a[index]._col==i)
   {
   Triple <T> tp;
   tp._row=_a[index]._col;
   tp._col=_a[index]._row;
   tp._value=_a[index]._value;
   tmp._a.push_back(tp);
   }
  }
  }
  return tmp;
  
}
//稀疏矩阵的快速转置
SpareMatrix<T> FastTransport()
{
  SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  int* rowcounts=new int[tmp._rowsize];
  int* rowstart=new int[tmp._rowsize];
  memset(rowcounts,0,sizeof((int*)_colsize));
  memset(rowstart,0,sizeof((int*)_colsize));
  size_t index=0;
 
  //计算待转置矩阵每一列非零元素的个数
  while(index<_a.size())
  {
  rowcounts[_a[index]._col]++;
  index++;
  }


//计算待转置矩阵每一列第一个非零元素在三元组表中的位置
rowstart[0]=0;
for(size_t i=1;i<_colsize;i++)
{
rowstart[i]=rowstart[i-1]+rowcounts[i-1];
}

index=0;
//给_a的匿名对象开辟_a大小的空间
    tmp._a.resize(_a.size());
while(index<=_a.size())
{/*
size_t rowindex=_a[index]._col;*/
int& start=rowstart[_a[index]._col];

Triple<T> tp;
tp._value=_a[index]._value;
tp._row=_a[index]._col;
tp._col=_a[index]._row;
tmp._a[start++]=tp;
index++;
}
return tmp;
}
void display()
{
   size_t index=0;
for(size_t i=0;i<_rowsize;i++)
{
for(size_t j=0;j<_colsize;j++)
{
   if(index<_a.size() && _a[index]._row==i && _a[index]._col==j)
   {
        cout<<_a[index++]._value<<" ";
   }
   else
   {
   cout<<_invalid<<" ";
   }
}
cout<<endl;
}
cout<<endl;
}


protected:
vector<Triple <T> > _a;
size_t _rowsize;
size_t _colsize;
T _invalid;

};

void test()
{
    int a[4][4]={{1,0,0,0},
                 {2,2,0,0},
                 {0,1,3,0},
                 {1,0,0,4}};
SpareMatrix<int>sm1((int*)a,4,4,0);
sm1.display();

SpareMatrix<int> sm2=sm1.Transport();
sm1.display();

SpareMatrix<int> sm3=sm1.FastTransport();
sm1.display();
}
int main()
{
test();
getchar();
return 0;
}





















推荐阅读:
  1. 稀疏矩阵的转置与快速转置
  2. c++稀疏矩阵的压缩存储

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

压缩 矩阵 稀疏

上一篇:我来试试哈

下一篇:ActiveReports 报表应用教程 (6)---分组报表

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》