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

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

稀疏矩阵:M*N的矩阵,矩阵中有效值的个数远小于无效值的个数,且这些数据的分布没有规律。

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

实现代码:

#include <iostream>
#include <vector>
using namespace std; 

template<class T>
struct Triple    //三元组
{
  size_t _row;  //行
  size_t _col;  //列
  T _value;  //值 

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

template<class T>
class SparseMatrix   //稀疏矩阵
{
protected:
  vector<Triple<T>> _matrix; //可以实现动态增容的压缩矩阵
  size_t _m;  //行
  size_t _n;  //列
  T _invalid;   //默认值 

public:
  SparseMatrix(T* a, size_t m, size_t n, const T& invalid= T())
    :_m(m)
    , _n(n)
    , _invalid(invalid)
  {
    for (size_t i = 0; i < m; ++i)
    {
      for (size_t j = 0; j < n; ++j)
      {
        Triple<T> t(i, j, a[i*n + j]);
        _matrix.push_back(t);
      }
    }
  } 

  void Display()
  {
    size_t index = 0;
    for (size_t i = 0; i < _m; ++i)
    {
      for (size_t j = 0; j < _n; ++j)
      {
        if (index < _matrix.size()
          && _matrix[index]._row== i
          &&_matrix[index]._col ==j)
        {
          cout << _matrix[index]._value << " ";
          ++index;
        }
        else
        {
          cout << _invalid << " ";
        }
      }
      cout << endl;
    }
    cout << endl;
  } 

}; 
#include <windows.h> 

void test()
{
  int a[6][5] =
  {
    { 1, 0, 2, 0, 0 },
    { 1, 0, 1, 0, 3 },
    { 2, 0, 0, 1, 2 },
    { 3, 0, 1, 0, 0 },
    { 4, 0, 2, 0, 0 },
    { 0, 3, 4, 0, 0 },
  }; 

  SparseMatrix<int> sm((int*)a, 6, 5, 0);
  //SymmetricMatrix(int a[][N], size_t N)
  sm.Display(); 

} 

int main()
{
  test(); 

  system("pause");
  return 0;
} 

以上就是稀疏矩阵的压缩存储的实例详解,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-07-28

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里中的实现为例,首先来探讨一下稀疏矩阵是如何存储表示的. 1.sparse模块初探 python中scipy模块中,有一个模块叫sparse模块,就是专门为了解决稀疏矩阵而生.本文的大部分内容,其实就是基于sparse模块而来的. 第一步自然就是导入sparse模块 >>> from scipy import sparse 然后help一把,先来看个大概 >>> h

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

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

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

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

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

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

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语言实现图的搜索算法.分享给大家供大家参考,具体如下: 在游戏中,常常遇到路径规划问题,用到图的相关算法,我们以简单图来学习. 图通常有两种表示方式,矩阵和邻接表.矩阵表示简单,运算快,但当矩阵是稀疏矩阵的时候就存在空间浪费的问题,并且效率也会下降,而邻接表节约空间,并且由于边是连续访问,时间效率也比较高.在本文中,我们将以邻接表来表示图. #include<queue> #include<stack> using namespace std; struct SE{

C语言中static的作用及C语言中使用静态函数有何好处

想了解Java中static关键字的作用和用法详细介绍,请点击此处了解详情. 在C语言中,static的字面意思很容易把我们导入歧途,其实它的作用有三条,分别是: 一是隐藏功能,对于static修饰的函数和全局变量而言 二是保持持久性功能,对于static修饰的局部变量而言. 三是因为存放在静态区,全局和局部的static修饰的变量,都默认初始化为0 下面我逐一给大家介绍: (1)先来介绍它的第一条也是最重要的一条:隐藏. 当我们同时编译多个文件时,所有未加static前缀的全局变量和函数都具有

Java数据结构之稀疏矩阵定义与用法示例

本文实例讲述了Java数据结构之稀疏矩阵定义与用法.分享给大家供大家参考,具体如下: 稀疏矩阵非零元素的三元组类: package com.clarck.datastructure.matrix; /** * 稀疏矩阵的压缩存储 * * 稀疏矩阵非零元素的三元组类 * * @author clarck * */ public class Triple implements Comparable<Triple> { // 行号,列号, 元素值,默认访问权限 int row, colum, val

React-intl 实现多语言的示例代码

最近在项目中添加了语言国际化的功能. 语言国际化,也有人说成是语言本地化,其实就是为Web App添加多语言,我们的项目当前包含了中文版和英文版,按理来说『逐字替换』也不是多大事儿,但是,这么Low的做法,有钱途吗? 一开始的时候,我考虑的是传统的为整个项目添加config文件,根据不同的语言和地区,加载不同的config文件,就能够达到界面语言切换的目的.当然,也正是因为这个想法太过于幼稚,所以才被称为『一开始』的想法.语言的国际化不仅仅是将界面上的UI文字翻译成另一种语言,还包括了日期&时间

详解React-Native全球化多语言切换工具库react-native-i18n

开篇啰嗦–阶段感悟 最近2 -3个月基本都因为一些私事没怎么系统的工作和学习,途中看了几天Kotlin的东西写了些demo并且整了个小项目,但是整体状态不是很好,这些天看到些95后码农的强势细思极恐. 现在大多数醒来就已经是中午,起得早去一下健身房,起的晚就家里宅一天.公司有事或者有其他家事就去协调/沟通/处理下,整个人感觉都提前进入养老状态(当然这个锅有一半是沉迷王者荣耀不可自拔,不太好) 最近项目上基本没啥事情了,然后让手下的小伙伴们对之前做的一些内容进行二次封装,然后他们引用了一个第三方国

Go语言程序查看和诊断工具详解

想必Java 的开发者没有不知道或者没用过 jps 这个命令的,这个命令是用来在主机上查看有哪些 Java 程序在运行的. 我刚用 Go 语言程序的时候也很苦恼,我部署在公司服务器上的 Go 程序,其他的同事由于不清楚就经常找不到. 那么 Go 语言有没有像 jps 这样的工具呢?当然有,不仅有,而且还是 Google 自己出品的,官方认证(这种问题 Google 不可能自己想不到啊).名称也跟 jps 很像,叫 gops. 安装 gops 并不包含在官方安装包中,不属于标准工具.需要手动获取.

谷歌Sky语言怎么样?什么是Dart编程语言?

Q:谷歌Sky语言怎么样?Sky编程语言有哪些优势? A:Sky语言是谷歌近期推出的一款全新的自主网页编程语言Dart,谷歌推出Dart编程语言的目的是为了提升Android应用的流畅度.Sky语言的主要优势在于:可兼容iOS,为Android应用带来120fps的超级流畅体验. 作为当前市占率最高的智能手机操作系统,Android平台正在吸引着越来越多的开发者.不过,对用户而言,Android的体验还不够完善,卡顿的情况时有发生.再深入点理解,许多应用的帧率达不到普遍意义上流畅的标准60fps

Go语言中的延迟函数defer示例详解

前言 大家都知道go语言的defer功能很强大,对于资源管理非常方便,但是如果没用好,也会有陷阱哦.Go 语言中延迟函数 defer 充当着 try...catch 的重任,使用起来也非常简便,然而在实际应用中,很多 gopher 并没有真正搞明白 defer.return.返回值.panic 之间的执行顺序,从而掉进坑中,今天我们就来揭开它的神秘面纱!话不多说了,来一起看看详细的介绍吧. 先来运行下面两段代码: A. 匿名返回值的情况 package main import ( "fmt&qu

我放弃Python转Go语言的9大理由(附优秀书籍推荐)

前言 Go大概2009年面世以来,已经8年了,也算是8年抗战.在这8年中,已经有很多公司开始使用Go语言开发自己的服务,甚至完全转向Go开发,也诞生了很多基于Go的服务和应用,比如Dokcer.k8s等,很多的大公司也在用,比如google(作为开发Go语言的公司,当仁不让).Facebook.腾讯.百度.阿里.京东.小米以及360,当然除了以上提到的,还有很多公司也都开始尝试Golang,这其中是什么原因呢?让我们来一起分析分析. 原因 1:性能 Go 极其地快.其性能与 Java 或 C++