符合中小企业对网站设计、功能常规化式的企业展示型网站建设
本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...
商城网站建设因基本功能的需求不同费用上面也有很大的差别...
手机微信网站开发、微信官网、微信商城网站...
稀疏矩阵的特点
创新互联是一家专业提供麻山企业网站建设,专注与网站设计制作、做网站、HTML5、小程序制作等业务。10年已为麻山众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。M*N矩阵,矩阵中有效值的个数远远小于无效值的个数,并且这些数据的分布没有规律。
例如下面的矩阵
稀疏矩阵的压缩存储
压缩矩阵值存储极少数的有效数据。使用三元组来存储每一个数据,三元组数据按照矩阵中的位置,以行优先顺序依次存放。
则上述矩阵的存储结构为
三元组结构
//三元组的定义 templatestruct Triple { public: //默认无参构造函数 Triple() {} //构造函数 Triple(const T& d,size_t row=0,size_t col=0) :_value(d) ,_row(row) ,_col(col) {} public: T _value;//数据域 size_t _row;//行 size_t _col;//列 };
稀疏矩阵的压缩
templateclass SparseMatrix { public: //无参构造函数 SparseMatrix() {} SparseMatrix(const T* a, size_t row, size_t col, const T& invalid); void Display();//打印 SparseMatrix Transport();//列转置 SparseMatrix FastTransport();//快速转置 private: vector > _a;//三元组类型的顺序表 size_t _rowSize;//行数 size_t _colSize;//列数 T _invalid;//非法值 }; //矩阵的压缩 template SparseMatrix ::SparseMatrix(const T* a, size_t row, size_t col, const T& invalid) :_rowSize(row) , _colSize(col) , _invalid(invalid) { //行遍历 for (size_t i = 0; i < row; i++) { //列遍历 for (size_t j = 0; j < col; j++) { if (a[i*col + j] != invalid) { _a.push_back(Triple (a[i*col + j], i, j)); //不能通过数组创建,但是可以通过数组形式访问 } } } }
转置
将原矩阵的行、列互换,也就是将[row][col]和[col][row]位置上的数据对换。
列转置
算法思想:
采用按照被转置矩阵三元组表A的序列(即转置后三元组表B的行序)递增的顺序进行转置,并以此送入转置后矩阵的算远足表B中,这样一来,转置后矩阵的三元组表B恰好是以“行序为主序的”.
实现代码
//列转置 templateSparseMatrix SparseMatrix ::Transport() { SparseMatrix result; //行列size互换 result._rowSize = _colSize; result._colSize = _rowSize; result._invalid = _invalid; //按照列扫描 for (size_t j = 0; j < _colSize; j++) { //在三元组数组中找到相同列的元素 for (size_t index = 0; index < _a.size(); index++) { if (_a[index]._col == j) { result._a.push_back(Triple (_a[index]._value, _a[index]._col, _a[index]._row)); //按照列优先的顺序存到压缩数组中 } } } return result; }
算法分析:
算法的时间主要消耗在双重循环中,其时间复杂度为O(_colSize*_a.size)。
一次定位快速转置
算法思想:
在列转置中算法的时间浪费主要在双重循环中,要改善算法的性能,必须去掉双重循环,使得整个转置过程通过一次循环来完成。
为了能使得被转置的三元组表A中元素一次定位到三元组表B中,需要预先计算一下数据:
1)rowCounts,三元组表A中每一列有效值的个数,即转置后矩阵三元组表B中每一行有效值的个数。
2)rowStart,三元组表B中每一行有效值的起始位置。
rowStart[col]=rowStart[col-1]+rowCounts[col-1]
上述矩阵的两个数组为:
代码实现:
//快速转置 templateSparseMatrix SparseMatrix ::FastTransport() { assert(_a.size() < 0); SparseMatrix result; //行列size互换 result._rowSize = _colSize; result._colSize = _rowSize; result._invalid = _invalid; //建立rowCounts和rowStart int* rowCounts = new int[_colSize]; int* rowStart = new int[_colSize]; memset(rowCounts, 0, sizeof(int)*_colSize);//初始化为0 memset(rowStart, 0, sizeof(int)*_colSize);//初始化为0 result._a.resize(_a.size());//复制顺序表_a,容量相同,但是数据不同。 //初始化 for (size_t i = 0; i < _colSize; i++) { rowCounts[_a[i]._col]++; } rowStart[0] = 0; for (size_t i = 1; i < _colSize; i++) { rowStart[i] = rowCounts[i - 1] + rowStart[i - 1]; } //快速转置 size_t index = 0; Triple tmp; while (index < _a.size()) { int row = _a[index]._col;//行数 int rowIndex = rowStart[row];//当前行的起始位置 //交换行和列 tmp._value = _a[index]._value; tmp._row = _a[index]._col; tmp._col = _a[index]._row; result._a[rowIndex] = tmp; rowStart[row]++; index++; } delete[] rowCounts; delete[] rowStart; return result; }
算法分析:
一次定位快速转置算法时间主要浪费在3个并列的循环中,分别执行了_colSize,_col_Size,_a.size()次,总的时间复杂度为O(_colSize+_a.size())。远远小于O(_colSize*_a.size)。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。