登录
注册
Investment
International news
International scientific
金融快讯
Financial anecdotes
International finance
科技快讯
Quantitative investment
Asset risk
科学论坛
科学论坛
发帖
Program
轨道交通工具
translate
新闻实时报表
天气预报
办公搜索
电影搜索
购物搜索
音乐搜索
图片搜索
工作搜索
学术搜索
美女照片
开发服务
Recruitment
Recruitment
Center
Account registration
Account login
System announcement
ContactUs
发布广告
News Message
矩阵(稀疏矩阵)压缩存储
by
wittx
2021-06-25
数据结构中,提供针对某些特殊矩阵的压缩存储结构。
这里所说的特殊矩阵,主要分为以下两类:
含有大量相同数据元素的矩阵,比如对称矩阵;
含有大量 0 元素的矩阵,比如稀疏矩阵、上(下)三角矩阵;
针对以上两类矩阵,数据结构的压缩存储思想是:矩阵中的相同数据元素(包括元素 0)只存储一个。
对称矩阵
图
1 对称矩阵示意图
图 1 的矩阵中,数据元素沿主对角线对应相等,这类矩阵称为
对称矩阵
。
矩阵中有两条对角线,其中图 1 中的对角线称为主对角线,另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。
结合数据结构压缩存储的思想,我们可以使用一维
数组
存储对称矩阵。由于矩阵中沿对角线两侧的数据相等,因此数组中只需存储对角线一侧(包含对角线)的数据即可。
对称矩阵的实现过程是,若存储下三角中的元素,只需将各元素所在的行标 i 和列标 j 代入下面的公式:
存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式:
最终求得的 k 值即为该元素存储到数组中的位置(矩阵中元素的行标和列标都从 1 开始)。
例如,在数组 skr[6] 中存储图 1 中的对称矩阵,则矩阵的压缩存储状态如图 3 所示(存储上三角和下三角的结果相同):
图 3 对称矩阵的压缩存储示意图
注意,以上两个公式既是用来存储矩阵中元素的,也用来从数组中提取矩阵相应位置的元素。例如,如果想从图 3 中的数组提取矩阵中位于 (3,1) 处的元素,由于该元素位于下三角,需用下三角公式获取元素在数组中的位置,即:
结合图 3,数组下标为 3 的位置存储的是元素 3,与图 1 对应。
上(下)三角矩阵
图 4 上(下)三角矩阵
如图 4 所示,主对角线下的数据元素全部相同的矩阵为
上三角矩阵
(图 4a)),主对角线上元素全部相同的矩阵为
下三角矩阵
(图 4b))。
对于这类特殊的矩阵,压缩存储的方式是:上(下)三角矩阵采用对称矩阵的方式存储上(下)三角的数据(元素 0 不用存储)。
例如,压缩存储图 4a) 中的上三角矩阵,矩阵最终的存储状态同图 3 相同。因此可以得出这样一个结论,上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。
稀疏矩阵
图 5 稀疏矩阵示意图
如图 5 所示,如果矩阵中分布有大量的元素 0,即非 0 元素非常少,这类矩阵称为
稀疏矩阵
。
压缩存储稀疏矩阵的方法是:只存储矩阵中的非 0 元素,与前面的存储方法不同,稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。
例如,存储图 5 中的稀疏矩阵,需存储以下信息:
(1,1,1):数据元素为 1,在矩阵中的位置为 (1,1);
(3,3,1):数据元素为 3,在矩阵中的位置为 (3,1);
(5,2,3):数据元素为 5,在矩阵中的位置为 (2,3);
除此之外,还要存储矩阵的行数 3 和列数 3;
Share Http URL: http://www.wittx.cn/get_news_message.do?new_id=772
请输入评论
请输入评论!
发布评论
更多评论......
©2021 上海优钧机械设备科技有限公司
Best Last Month
时间管理之道
Information industry by wittx
NeurIPS 2021 Spotlight | 准确、快速、内存经济,新框架MEST实现边缘设备友好的稀疏训练
Information industry by wittx
LLM 最新论文
Information industry by wittx
欧佩克八月增产 日产量增加约150万桶
Information industry by wittx
LLM思维模型TOT
Information industry by wittx
arxiv Computer Science
Information industry by wittx
Nature 大规模筛选发现21种现有抗新冠病毒药物
Medical science by wittx
量子通讯
Information industry by wittx
并购 收购 重组
Information industry by wittx
国际原油重挫 4%
Information industry by wittx