数据结构(3.9_1)——特殊矩阵的压缩存储

总览

一维数组的存储结构 

如果下标从1开始,则a[i]的存放地址=LOC +(i-1)*sizeof(ElemType); 

 二维数组的存储

二维数组也具有随机存储的特性

设起始地址为LOC 

在M行N列的二维数组b[M][N]中,若按行优先存储,

b[i][j]的存储地址的=LOC + (i*N+j) * sizeof(ElemType)

在M行N列的二维数组b[M][N]中,若按列优先存储,

b[i][j]的存储地址的=LOC + (j*N+i) * sizeof(ElemType)

行优先存储的优点:可以随机存储、

列优先存储

普通矩阵的存储

对普通矩阵存储我们可以采用二维数组存储

  1. 行优先存储(大多数编程语言,如 C/C++、Java、Python):

    position=i*n+j

  2. 列优先存储(某些语言和库,如 Fortran):

    position=j*m+i

普通矩阵的存储通常涉及到计算机内存中的数据结构。在大多数编程语言中,矩阵通常被实现为一维数组或者二维数组。

  1. 一维数组存储:在这种方法中,矩阵被 flatten 成一个一维数组。例如,一个 2x3 的矩阵:


    \begin{bmatrix} 1&2 &3 \\ 4&5 &6 \end{bmatrix}

  2. 可以被存储为一个一维数组 [1, 2, 3, 4, 5, 6]。在内存中,这个数组是连续存储的。要访问矩阵中的元素,需要通过特定的公式来计算其在数组中的位置。例如,要访问元素 (i, j),在列优先存储(Column-major order)中,其在一维数组中的位置是 i + j * rows;在行优先存储(Row-major order)中,其位置是 i * cols + j

  3. 二维数组存储:在这种方法中,矩阵被存储为一个二维数组。在大多数编程语言中,这通常是通过数组的数组或者动态分配的二维数组来实现的。例如,在 C 语言中,可以使用 int matrix[2][3] 来声明一个 2x3 的矩阵。在内存中,这个二维数组同样是连续存储的,但是以行或列的顺序。

每种存储方法都有其优缺点。一维数组存储更节省空间,因为不需要存储额外的行或列的指针信息,但是在访问特定元素时可能需要更多的计算。二维数组存储在访问元素时更直观,但是在某些编程语言中可能需要更多的内存来存储额外的指针信息。

对称矩阵的压缩存储

若n阶方阵中任意一个元素都\alpha i,j\alpha i,j=\alpha j,i,则该矩阵为对称矩阵

策略:只存储主队角线+下三角区

行优先原则将各元素存入一维数组中

数组大小应该设置为(1+n)*n/2 ,简而言之就是一个等差数列求和

,问题:对称矩阵压缩存储后该怎么样才能方便使用?

可以实现一个“映射”函数

矩阵下标—>一维数组下标

i>j(下三角)时

下标为0,从第0行开始元素个数有1个第二行元素个数2个....到最后一行有n个,所以它的元素总数为个,所以我们设置的一维数组大小应该就这么大,然后求aij在一维数组的坐标我们应该算出aij是第几个元素,按照行优先的原则,我们先得出aij前面有多少行,第一行为1,然后最后一行是i-1本身,为什么要-1呢?因为下标是从0开始的,所以转换成一维数组后需要减1如果下标从1开始则bu'xu'y,求出等差数列和为\frac{i\cdot (i-1))}{2},注意这里i-1才是项数,i是首项加末项由i-1+1得来,然后再算出aij前面有多少列元素,根据推导可得有j个元素,所以k=\frac{i\cdot(i-1))}{2}+j-1,这里-1原理同上

i<j(上三角)时

由于对称矩阵aij=aji ,所以k=\frac{j\cdot(j-1))}{2}ij-1

出题思路:

下标从0开始,先求aij前面有多少列元素,第一列是n元素,第二列n-1一值到最后一列n-(j-1-1),为什么要加1呢?因为,我们求的是i-1,i-1有n-(j-1-1)个元素,接下来再求行元素,根据图不难发现,求行元素只需将i-j便可求出除该元素之外本行有多少行元素,因为下标从0开始,所以最后再加上1得出坐标为k=\frac{i\cdot(i-j+3)}{2}+(i-j)+1

三角矩阵的压缩存储

下三角矩阵:

除了主对角线和下三角区,其余的元素都相同

 压缩存储策略:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

映射规律下三角区的规律和对称矩阵的相同,只是访问上三角区的时候我们需要把下标映射到一维数组的最后一个位置

上三角矩阵:

除了主对角线和上三角区,其余的元素都相同 

压缩存储策略:按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量c 

 首先我们确定aij前面有多少行,所以我们需要知道i-1行,第一行是n个,第二行n-1个,所以第n行有n-(i-1),所以第i-1行是n-(i-1-1)=n-i+2,等差数列求和:(\frac{(i-1)\cdot(2n-i+2))}{2})得知i前面有个(\frac{(i-1)\cdot(2n-i+2))}{2})元素,我们再来计算j前面有多少列元素,就是j-i,得知j前面有j-i个元素,于是我们得知aij是第(\frac{(i-1)\cdot(2n-i+2))}{2})+j-(i-1)-1个元素,最后-1是因为下标从0开始

三对角矩阵的压缩策略

三对角矩阵是一种特殊的带状矩阵,它在矩阵中只有主对角线、主对角线上方的一条对角线和主对角线下方的一条对角线上的元素是非零的,而其他位置的元素都是零。这种矩阵在数值分析中非常常见,尤其是在求解线性方程组时。

 三对角矩阵:当|i-j|>1时,有aij=0 (1<=i,j<=n)

压缩策略:按行优先(或列优先原则,只存储带状部分)

由三队角矩阵可见除第一行和最后一行元素是两个以外其它行元素都是3个所以元素总数是3n-2如果默认下标是0开始,那么最后一个数组的下标则是3n-3

将行号和列号映射为一维数组下标

key:按行优先的原则,aij是第几个元素 

求行:前i-1行共有3(i-1)-1个元素

求列:aij是i行第j-i+2个元素(看图推理得出)

求一维数组下标:行列元素相加得k=2i+j-2,若数组下标从0开始,则k=2i+j-3

已知k求aij

 

求B[k]转换成aij的坐标,首先由于k是数组下标是从0开始的,而题目要求k+1则是从1开始

前i-1行共3(i-1)-1个元素,前i行共有 3i-1

所以得出:3(i-1)-1<k+1\leq 3i-1

可以理解为i刚好大于等于(k+2)/3 : i\geq \frac{k+2}{3}向上取整即可满足"刚好"大于等于:i=\frac{k+2}{3}

稀疏矩阵的压缩存储

稀疏矩阵:非零元素远远少于矩阵元素的个数

压缩存储策略1:

顺序存储---三元组<行,列,值>

压缩存储策略2:

链式存储---十字链表法

总结:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/793816.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【JVM】对象的生命周期一 | 对象的创建与存储

Java | 对象的生命周期1-对象的创建与存储 文章目录 前言对象的创建过程内存空间的分配方式方式1 | 指针碰撞方式2 | 空闲列表 线程安全问题 | 避免空间冲突的方式方式1 | 同步处理&#xff08;加锁)方式2 | 本地线程分配缓存 对象的内存布局Part1 | 对象头Mark Word类型指针 P…

文献翻译与阅读《Integration Approaches for Heterogeneous Big Data: A Survey》

CYBERNETICS AND INFORMATION TECHNOLOGIES’24 论文原文下载地址&#xff1a;原文下载 目录 1 引言 2 大数据概述 3 大数据的异构性 4 讨论整合方法 4.1 大数据仓库&#xff08;BDW&#xff09; 4.2 大数据联盟&#xff08;BDF&#xff09; 5 DW 和 DF 方法的比较、分…

智充科技营收增速放缓:经营成本飙升,应收账款大幅增长

《港湾商业观察》黄懿 6月10日&#xff0c; XCHG Limited 智能充电有限公司(下称&#xff1a;智充科技)在美国证监会(SEC)更新招股书&#xff0c;拟在美国纳斯达克上市&#xff0c;其股票代码为“XCH”。北京智充科技有限公司为其国内运营主体&#xff08;下称“北京智充科技”…

IC后端设计中的shrink系数设置方法

我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 在一些成熟的工艺节点通过shrink的方式(光照过程中缩小特征尺寸比例)得到了半节点,比如40nm从45nm shrink得到,28nm从32nm shrink得到,由于半节点的性能更优异,成本又低,漏电等不利因素也可以…

C++学习

一、注释 /*多行 。。。 。。。 注释*/ //单行注释 #include <iostream> using namespace std; int main() {cout << "hellow" << endl;system("pause");return 0; }二、变量定义 #include <iostream> using namespace std; int…

YOLOv8改进 | 注意力机制| 利用并行子网络构建深度较浅但性能卓越的网络【全网独家】

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 专栏目录 &#xff1a;《YOLOv8改进有效…

[PM]原型与交互设计

原型分类 1.草图原型 手绘图稿, 规划的早期,整理思路会使用 2.低保真原型 简单交互, 无需配色, 黑白灰为主, 产品规划和评审阶段使用 标准化的低保真原型是高保真原型的基础 3.高保真原型 复杂交互, 一般用于公开演示, 产品先产出低保真原型, 设计师根据原型产出设计稿 低保…

【ARM】CCI缓存一致性整理

目录 1.CCI500提供的功能 2.CCI500在SOC系统中所处的位置​编辑 3.CCI500内部结构​编辑 4.功能描述 1.CCI500提供的功能 2.CCI500在SOC系统中所处的位置 3.CCI500内部结构 Transaction Tracker&#xff08;TT&#xff09;是用来解决一致性和ordering问题的&#xff0c;它…

【驱动篇】龙芯LS2K0300之spi设备驱动

实验介绍 GC9A01是一款小巧&#xff08;1.28寸&#xff09;、彩色&#xff08;分辨率为 240 * 240 RGB&#xff09;圆形TFT屏幕&#xff0c;它采用4线 SPI的控制方式&#xff0c;电源供电电压为3.3V&#xff0c;有7个控制引脚&#xff1b;本次实验将使用它来验证龙芯SOC的SPI通…

css实现图片渐变切换效果

一、效果 使用csskeyframes&#xff0c;实现5个图片渐变切换的效果。如下图&#xff1a; 二、代码 1.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"w…

头歌资源库(27)特别的数

一、 问题描述 编程输出一个特别的数&#xff0c;该数是一个由1~9组成的9位数&#xff0c;每个数字只能出现一次&#xff0c;且这个9位数由高位到低位前i位能被i整除。 二、算法思想 创建一个长度为9的数组&#xff0c;用于存放1~9这9个数字。使用回溯算法&#xff0c;从第…

(WRF-UCM)高精度城市化气象动力模拟技术

气候变化及应对是政府、科学界及商业界关注的焦点。气候是多个领域&#xff08;生态、水资源、风资源及碳中和等问题&#xff09;的主要驱动因素&#xff0c;合理认知气候变化有利于解释生态环境变化机理及过程&#xff0c;而了解现在、未来气候变化则是进行生态、环境及能源评…

IDEA中配置代理,解决Codearts Snap登陆不了的问题

问题描述&#xff1a;在mac电脑中的idea中安装了华为的codearts snap插件&#xff0c;一直登录不了&#xff0c;账号是没问题的&#xff0c;后来我怀疑是我的代理有问题&#xff0c;找到IDEA中的代理设置先是有这个问题“You have JVM property "https.proxyHost" se…

C++基础(一)

目录 1.不同版本的hello word&#xff01; 2.namespace和&#xff1a;&#xff1a;域作用限定符以及using 2.1 namespace 2.2&#xff1a;&#xff1a; 2.3using用于展开域 3.C输入和输出 4.缺省参数 5.重载 6.引用 6.1引用介绍 6.2 引用的特性 注意&#xff1a; 6.4 c…

C#绘制阻抗圆图初步

阻抗圆图&#xff0c;或者叫史密斯图&#xff0c;是无线电设计方面用的&#xff1b; 基本的阻抗圆图如下&#xff0c; 下面尝试用C#能不能画一下&#xff1b; 先在网上找一个画坐标的C#类&#xff0c;它的效果如下&#xff1b; 自己再增加一个函数&#xff0c;可以绘制中心在…

Redis的安装配置及IDEA中使用

目录 一、安装redis&#xff0c;配置redis.conf 1.安装gcc 2.将redis的压缩包放到指定位置解压 [如下面放在 /opt 目录下] 3.编译安装 4.配置redis.conf文件 5.开机自启 二、解决虚拟机本地可以连接redis但是主机不能连接redis 1.虚拟机网络适配器网络连接设置为桥接模式…

《昇思25天学习打卡营第16天|基于MindNLP+MusicGen生成自己的个性化音乐》

MindNLP 原理 MindNLP 是一个自然语言处理&#xff08;NLP&#xff09;框架&#xff0c;用于处理和分析文本数据。 文本预处理&#xff1a;包括去除噪声、分词、词性标注、命名实体识别等步骤&#xff0c;使文本数据格式化并准备好进行进一步分析。 特征提取&#xff1a;将文…

【嵌入式Linux】<知识点> GDB调试(更新中)

文章目录 前言 一、GDB调试预备工作 二、GDB的启动与退出 三、GDB中查看源代码 四、GDB断点操作 五、GDB调试指令 前言 在专栏【嵌入式Linux】应用开发篇_Linux打工仔的博客中&#xff0c;我们已经写了大量的源程序。但是在调试这些程序时我们都是通过printf大法和肉眼除…

异业联盟整合各大行业门店,共享资源

异业联盟系统是一种将不同行业的企业或商家整合在一起&#xff0c;通过资源共享、优势互补、合作推广等方式&#xff0c;实现共同发展和互利共赢的商业合作模式的数字化管理和运营系统。 其具有以下显著优势&#xff1a; 1.拓展客户群体&#xff1a;不同行业的企业联合起来&am…

Python骨架肌体运动学数学模型

&#x1f3af;要点 &#x1f3af;运动学矢量计算 | &#x1f3af;跳远的运动学计算 | &#x1f3af;关节肢体运动最小加加速度模型 | &#x1f3af;膝关节和踝关节角度二维运动学计算 | &#x1f3af;上下肢体关节连接运动链数学模型 | &#x1f3af;刚体连接点速度加速度计算…