C++实现稀疏矩阵的压缩存储实例

什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律。在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据。我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放。下面我们来看一下代码实现。

#include<iostream>
#include<vector>
#include<assert.h>
using namespace std; 

template<class T>
class SparseMatrix
{
  //三元组
  template<class T>
  struct Trituple
  {
    Trituple()//给一个默认构造函数
    {}
    Trituple(size_t row, size_t col, const T& data)
      :_row(row)
      ,_col(col)
      ,_data(data)
    {}
    size_t _row;
    size_t _col;
    T _data;
  };
public:
  //稀疏矩阵的压缩存储
  SparseMatrix()
  {}
  SparseMatrix(int* arr, size_t row, size_t col, const T& invalid)
    :_row(row)
    ,_col(col)
    ,_invalid(invalid)
  {
    for(int i = 0; i < row; i++)
    {
      for(int j = 0; j < col; ++j)
      {
        if(arr[i*col+j] != invalid)//将有效值存储在一个一维数组中
        _sm.push_back(Trituple<T>(i,j,arr[i*col+j]));//将三元组的无名对象push进去
      }
    }
  }
  //访问稀疏矩阵中row行col中的元素
  T& Acess(int row, int col)
  {
    //1、
    /*for(int idx = 0; idx < _sm.size(); idx++)//遍历一遍
    {
      if(_sm[idx]._row == row && _sm[idx]._col == col)//当前行列与我们要访问那个元素行列相同时返回这个有效值
        return _sm[idx]._data;
    }
    return _invalid;*/ //否则返回无效值
    //2、
    vector<Trituple<T>>::iterator it = _sm.begin();//定义一个迭代器,指向起始位置
    while(it != _sm.end())//未到最后一个元素时
    {
      if(it->_row == row && it->_col == col)//行列相等输出值
        return it->_data;
      ++it;//迭代器向后移动
    }
    return _invalid;
  }
  //还原稀疏矩阵
  template<typename T>
  friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//重载<<
  {
    size_t idex = 0;
    for(size_t i = 0; i < s._row; i++)
    {
      for(size_t j = 0; j < s._col; j++)
      {
        if(idex < s._sm.size()/*防止数组越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j)
        {
          _cout<<s._sm[idex]._data<<" ";
          ++idex;
        }
        else
          _cout<<s._invalid<<" "; 

      }
      _cout<<endl;
    }
    return _cout;
  }
  //实现稀疏矩阵的逆置 时间复杂度O(M*N)(M为元素个数N为矩阵列数)
  SparseMatrix<T> Transport()
  {
    SparseMatrix<T> sm;
    sm._row = _col;
    sm._col = _row;
    sm._invalid = _invalid;
    for(size_t i = 0; i < _col; i++)
    {
      vector<Trituple<T>>::iterator it = _sm.begin();
      while(it != _sm.end())
      {
        if(it->_col == i)//从原矩阵第0列开始,将每列中的有效值依次放入新的稀疏矩阵
          sm._sm.push_back(Trituple<T> (i, it->_row, it->_data));
        ++it;
      }
    }
    return sm;
  }
  //实现稀疏矩阵的快速转置 时间复杂度O(N)+O(M)
  SparseMatrix<T> FastTransport()
  {
    SparseMatrix<T> sm;
    sm._col = _row;
    sm._row = _col;
    sm._invalid = _invalid;
    sm._sm.resize(_sm.size());//开辟空间
    //1、统计原矩阵中每一列有多少个有效元素
    int* pCount = new int[_col];//开辟原矩阵中列个数的空间
    memset(pCount, 0, _col*sizeof(pCount[0]));
    for(int i = 0; i < _sm.size(); i++)
      pCount[_sm[i]._col]++;
    //2、原矩阵每一列在新矩阵中的起始位值
    int* pAddr = new int[_col];
    memset(pAddr, 0, _col*sizeof(pAddr[0]));
    for(int i = 1/*从1开始,第一个位置起始为0已经放入*/; i < _sm.size(); i++)
    {
      pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一个起始位值+前一列有效元素个数
    }
    //3、放置元素到新空间
    for(int i = 0; i < _sm.size(); i++)
    {
      int& addr = pAddr[_sm[i]._col];
      sm._sm[addr] = Trituple<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data);
      addr++;
    }
    return sm;
  }
  //实现稀疏矩阵的加法操作1
  /*SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
  {
    int i = 0, j = 0, k = 0;
    T v;
    SparseMatrix<T> s;
    if(this->_col != sp._col || this->_row != sp._row)
      exit(1);
    s._row = sp._row;
    s._col = sp._col;
    s._invalid = sp._invalid;
    while(i < this->_sm.size() && j < sp._sm.size())
    {
      if(this->_sm[i]._row == sp._sm[j]._row)
      {
        if(this->_sm[i]._col < sp._sm[j]._col)
        {
          s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
          i++;
          k++;
        }
        else if(this->_sm[i]._col > sp._sm[j]._col)
        {
          s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
          j++;
          k++;
        }
        else
        {
          v = this->_sm[i]._data + sp._sm[j]._data;
          if(v)
          {
            s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, v));
            k++;
          }
          i++;
          j++;
        }
      }
      else if(this->_sm[i]._row < sp._sm[j]._row)
      {
        s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
        i++;
        k++;
      }
      else
      {
        s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
        j++;
        k++;
      }
    }
    return s;
  }*/
  //实现稀疏矩阵的加法操作2
  SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
  {
    assert(_row == sp._row && _col == sp._col);//检测两个相加的矩阵行列是否相等
    SparseMatrix<T> ret;
    ret._row = _row;
    ret._col = _col;
    ret._invalid = _invalid;
    int iLidx = 0, iRidx = 0;//定义两个索引 

    while(iLidx < _sm.size() && iRidx < sp._sm.size())
    {
      size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左边矩阵的起始位值
      size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右边矩阵起始位值
      if(AddrLeft < AddrRight)//左<右,将左边有效值放入和矩阵中,左边的索引加加
      {
        ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
        iLidx++;
      }
      else if(AddrLeft > AddrRight)
      {
        ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
        iRidx++;
      }
      else//当左边等于右边判断相加后和是否为0,不为0放入
      {
        Trituple<T> temp(_sm[iLidx]);
        temp._data += sp._sm[iRidx]._data;
        if(temp._data)
        {
          ret._sm.push_back(temp);
          iLidx++;
          iRidx++;
        }
      }
    }
    while(iLidx < _sm.size())//左边还有剩余则放入剩余元素
    {
      ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
      iLidx++;
    }
    while(iRidx < sp._sm.size())
    {
      ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
      iRidx++;
    }
    return ret;
  }
private:
  size_t _row;
  size_t _col;
  vector<Trituple<T>> _sm;
  T _invalid;//无效值
}; 

int main()
{
  int arr[6][5] = {
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,0,0,0},
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,0,0,0}};
  int arr1[6][5] = {
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,2,4,0},
    {1,0,3,0,5},
    {0,0,0,1,0},
    {0,0,0,0,1}};
  SparseMatrix<int> s((int*)arr,6,5,0);
  SparseMatrix<int> s1((int*)arr1,6,5,0);
  cout<<"访问三行四列元素"<<endl;
  cout<<s.Acess(3,4)<<endl;
  cout<<s<<endl;
  cout<<"快速转置"<<endl;
  cout<<s.FastTransport();
  cout<<endl;
  cout<<"矩阵s:"<<endl;
  cout<<s<<endl;
  cout<<"矩阵s1:"<<endl;
  cout<<s1<<endl;
  cout<<"s+s1求和:"<<endl;
  cout<<s1+s<<endl;
  system("pause");
  return 0;
}

运行结果截图:

在上面的代码中用到C++模板、标准库中vector容器,以及迭代器实现了一些基本的操作,如访问稀疏矩阵中某个元素,输出稀疏矩阵、稀疏矩阵的转置以及快速转置还有两个稀疏矩阵的加法。

快速转置操作的基本思路是:

(1)统计原矩阵中每一列有多少个有效元素;

(2)原矩阵中每一列在新矩阵中的起始地址;

(3)放置元素到新空间中。

还需注意的是,在我们打印这个稀疏矩阵时虽然也可以直接调用访问元素的Acess接口,但是每次进去之后都得遍历一遍,时间复杂度较高,所以我们不采取这种办法,而是比较当前行列的值,若相等输出有效元素,不等则输出无效元素0。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-06-08

Python 稀疏矩阵-sparse 存储和转换

稀疏矩阵-sparsep from scipy import sparse 稀疏矩阵的储存形式 在科学与工程领域中求解线性模型时经常出现许多大型的矩阵,这些矩阵中大部分的元素都为0,被称为稀疏矩阵.用NumPy的ndarray数组保存这样的矩阵,将很浪费内存,由于矩阵的稀疏特性,可以通过只保存非零元素的相关信息,从而节约内存的使用.此外,针对这种特殊结构的矩阵编写运算函数,也可以提高矩阵的运算速度. scipy.sparse库中提供了多种表示稀疏矩阵的格式,每种格式都有不同的用处,其中dok_m

C语言实现稀疏矩阵

本文实例为大家分享了C语言实现稀疏矩阵的具体代码,供大家参考,具体内容如下 #include "stdio.h" #define maxsize 10 typedef struct { int i,j; //非零元素的行.列 int v; //非零元素的值 }Triple; typedef struct { Triple data[maxsize]; int m,n; //矩阵的行.列 }TSMarix; InitTriple(TSMarix *M) { int i,j,k,v,t;

C++ 实现稀疏矩阵的压缩存储的实例

C++ 实现稀疏矩阵的压缩存储的实例 稀疏矩阵:M*N的矩阵,矩阵中有效值的个数远小于无效值的个数,且这些数据的分布没有规律. 稀疏矩阵的压缩存储:压缩存储值存储极少数的有效数据.使用{row,col,value}三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放. 实现代码: #include <iostream> #include <vector> using namespace std; template<class T> struct

python实现稀疏矩阵示例代码

工程实践中,多数情况下,大矩阵一般都为稀疏矩阵,所以如何处理稀疏矩阵在实际中就非常重要.本文以Python里中的实现为例,首先来探讨一下稀疏矩阵是如何存储表示的. 1.sparse模块初探 python中scipy模块中,有一个模块叫sparse模块,就是专门为了解决稀疏矩阵而生.本文的大部分内容,其实就是基于sparse模块而来的. 第一步自然就是导入sparse模块 >>> from scipy import sparse 然后help一把,先来看个大概 >>> h

C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储

对称矩阵及稀疏矩阵的压缩存储 1.稀疏矩阵 对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse). 人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律. 实现代码: //稀疏矩阵及其压缩存储 #pragma once #include <vector> #include <iostream> using namespace std; templa

Python使用稀疏矩阵节省内存实例

推荐系统中经常需要处理类似user_id, item_id, rating这样的数据,其实就是数学里面的稀疏矩阵,scipy中提供了sparse模块来解决这个问题,但scipy.sparse有很多问题不太合用: 1.不能很好的同时支持data[i, ...].data[..., j].data[i, j]快速切片: 2.由于数据保存在内存中,不能很好的支持海量数据处理. 要支持data[i, ...].data[..., j]的快速切片,需要i或者j的数据集中存储:同时,为了保存海量的数据,也需

python如何为创建大量实例节省内存

python如何为创建大量实例节省内存,具体内容如下 案例: 某网络游戏中,定义了玩家类Player(id, name, status,....),每有一个在线玩家,在服务器程序内有一个Player的实例,当在线人数很多时,将产生大量实例(百万级别) 需求: 如何降低这些大量实例的内存开销? 如何做? 首先要明白,python中的类可以动态的添加属性,实则在内存中有个__dict__方法维护了这种动态添加属性,它占有内存,把它关掉,不就达到省内存要求了? #!/usr/bin/python3 i

python使用__slots__让你的代码更加节省内存

前言 在默认情况下,Python的新类和旧类的实例都有一个字典来存储属性值.这对于那些没有实例属性的对象来说太浪费空间了,当需要创建大量实例的时候,这个问题变得尤为突出. 因此这种默认的做法可以通过在新式类中定义了一个__slots__属性从而得到了解决.__slots__声明中包含若干实例变量,并为每个实例预留恰好足够的空间来保存每个变量,因此没有为每个实例都创建一个字典,从而节省空间. 本文主要介绍了关于python使用__slots__让你的代码更加节省内存的相关内容,分享出来供大家参考学

python使用pandas处理大数据节省内存技巧(推荐)

一般来说,用pandas处理小于100兆的数据,性能不是问题.当用pandas来处理100兆至几个G的数据时,将会比较耗时,同时会导致程序因内存不足而运行失败. 当然,像Spark这类的工具能够胜任处理100G至几个T的大数据集,但要想充分发挥这些工具的优势,通常需要比较贵的硬件设备.而且,这些工具不像pandas那样具有丰富的进行高质量数据清洗.探索和分析的特性.对于中等规模的数据,我们的愿望是尽量让pandas继续发挥其优势,而不是换用其他工具. 本文我们讨论pandas的内存使用,展示怎样

python 基本数据类型占用内存空间大小的实例

python中基本数据类型和其他的语言占用的内存空间大小有很大差别 import sys a = 100 b = True c = 100L d = 1.1 e ="" f = [] g =() h = {} i = set([]) print " %s size is %d "%(type(a),sys.getsizeof(a)) print " %s size is %d "%(type(b),sys.getsizeof(b)) print

python多进程中的内存复制(实例讲解)

比较好奇python对于多进程中copy on write机制的实际使用情况.目前从实验结果来看,python 使用multiprocessing来创建多进程时,无论数据是否不会被更改,子进程都会复制父进程的状态(内存空间数据等).所以如果主进程耗的资源较多时,不小心就会造成不必要的大量的内存复制,从而可能导致内存爆满的情况. 示例 举个例子,假设主进程读取了一个大文件对象的所有行,然后通过multiprocessing创建工作进程,并循环地将每一行数据交给工作进程来处理: def parse_

Python数据处理numpy.median的实例讲解

numpy模块下的median作用为: 计算沿指定轴的中位数 返回数组元素的中位数 其函数接口为: median(a, axis=None, out=None, overwrite_input=False, keepdims=False) 其中各参数为: a:输入的数组: axis:计算哪个轴上的中位数,比如输入是二维数组,那么axis=0对应行,axis=1对应列: out:用于放置求取中位数后的数组. 它必须具有与预期输出相同的形状和缓冲区长度: overwrite_input:一个bool

Python迭代器与生成器用法实例分析

本文实例讲述了Python迭代器与生成器用法.分享给大家供大家参考,具体如下: 迭代器,迭代的工具 什么是迭代器? 指的是一个重复的过程,每一次重复称为一次迭代,并且每一次重复的结果是下一次重复的初始值 l=['a','b','c'] count=0 while count <len(l): print(l[count]) count+=1 为什么要有迭代器 1.对于序列类型:str,list,tuple,可以依赖索引来迭代取值 2.对于dict,set,文件,python必须为我们提供一种不依

理解Python中的类与实例

面向对象最重要的概念就是类(Class)和实例(Instance),必须牢记类是抽象的模板,比如Student类,而实例是根据类创建出来的一个个具体的"对象",每个对象都拥有相同的方法,但各自的数据可能不同. 仍以Student类为例,在Python中,定义类是通过class关键字: class Student(object): pass class后面紧接着是类名,即Student,类名通常是大写开头的单词,紧接着是(object),表示该类是从哪个类继承下来的,继承的概念我们后面再

python中查看变量内存地址的方法

本文实例讲述了python中查看变量内存地址的方法.分享给大家供大家参考.具体实现方法如下: 这里可以使用id >>> print id.__doc__ id(object) -> integer Return the identity of an object. This is guaranteed to be unique among simultaneously existing objects. (Hint: it's the object's memory address