字典嵌套字典数据结构的稀疏矩阵压缩存储方法

摘要

本发明涉及一种字典嵌套字典数据结构的稀疏矩阵压缩存储方法，属于高性能计算机存储领域。包括初始化生成字典嵌套字典类型的数据结构；输入稀疏矩阵；判断稀疏矩阵元素是否为零；将非零元素的行索引、列索引和值存储在字典嵌套字典的数据存储结构中。本发明利用字典数据存储结构的时间复杂度和空间复杂度较优的特性，采用一种字典嵌套字典的数据存储结构来存储稀疏矩阵，达到占用内存少、存储高效、处理成本低且耗时少的效果。

说明书

技术领域

本发明涉及高性能计算机存储领域，特别涉及一种字典嵌套字典数据结构的稀疏矩阵压缩存储方法。

背景技术

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于5％时，则称该矩阵为稀疏矩阵。在一些工程计算中，常用到百万级或千万级维度的稀疏矩阵，如果将这些稀疏矩阵元素全部存储是十分浪费计算机存储空间的，所以考虑将稀疏矩阵进行压缩存储。

在一些工程问题中，会用到有限元方法，在有限元方法的组装总体刚度矩阵的环节中，需要进行频繁的搜索、查找和插入功能，由于以往使用的数组或链表数据结构的这三个功能的时间复杂度都是O(n)(n为问题的规模)，即线性时间，则组装和存储的时间是随规模的增大而增大的，所以组装和存储大规模问题的总体刚度矩阵的过程是十分耗时的。有限元方法的总体刚度矩阵是稀疏矩阵，所以大规模问题的稀疏矩阵通常需要压缩存储。

目前有许多稀疏矩阵的压缩存储方法，如三元组顺序表、行逻辑链接的顺序表、行指针链表、十字链表、COO、CSR、CSC、LIL等方法。这些方法虽然都可以将稀疏矩阵进行压缩存储，但对大规模稀疏矩阵来说，仍然在存储过程中占用大量内存。

发明内容

本发明的目的在于提供一种字典嵌套字典数据结构的稀疏矩阵压缩存储方法，解决了现有技术存在的上述问题。本发明的字典嵌套字典数据结构的稀疏矩阵压缩存储方法不仅减少了存储稀疏矩阵所占用的内存，而且搜索、查找和插入三个功能的时间复杂度都是O(1)，用在有限元方法的总体刚度组装过程中时，是十分省时的，这对高性能计算机存储领域的发展是十分有利的。本发明存储高效、处理成本低且耗时少。减少计算机存储空间，扩大存储稀疏矩阵的规模。包括初始化生成字典嵌套字典类型的数据结构；输入稀疏矩阵；判断稀疏矩阵元素是否为零；将非零元素的行索引、列索引和非零值存储在字典嵌套字典的数据存储结构中。本发明利用字典数据存储结构的时间复杂度和空间复杂度较优的特性，采用一种字典嵌套字典的数据存储结构来存储稀疏矩阵，达到占用内存少的效果。

本发明的上述目的通过以下技术方案实现：

字典嵌套字典数据结构的稀疏矩阵压缩存储方法，字典是一种以键-值对形式存储数据的数据结构；设稀疏矩阵表示为A＝(a

步骤一、初始化生成字典嵌套字典类型的数据结构；

步骤二、读取稀疏矩阵A的第i行第j列元素的值a

步骤三、判断稀疏矩阵元素的值a

步骤四、按行或者按列存储稀疏矩阵A的非零的元素a

步骤五、判断元素的值a

步骤六、读取稀疏矩阵A的下一个元素的值a

所述的M,N为正整数。

所述的稀疏矩阵是规则的或者不规则的。

步骤四所述的按列存储稀疏矩阵A的非零的元素是：将每个非零的元素的值a

本发明的有益效果在于：

(1)本发明以字典嵌套字典这种数据结构只存储稀疏矩阵的非零元素的信息，达到占用计算机内存少的目的。设所有非零元所在的总行数为m，每一行非零元总列数为n

(2)本发明利用字典这种数据结构搜索、查找和插入功能的时间复杂度是O(1)的优点，即所需时间不随规模的增大而改变，可以高效组装和存储有限元中的大规模稀疏的总体刚度矩阵。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实例及其说明用于解释本发明，并不构成对本发明的不当限定。

图1为本发明的方法流程图；

图2为本发明的高效压缩存储稀疏矩阵的数据结构示意图；

图3为本发明的实施例1中低维稀疏矩阵；

图4为本发明的高效压缩存储稀疏矩阵的具体压缩存储结构示意图。

具体实施方式

下面结合附图进一步说明本发明的详细内容及其具体实施方式。

参见图1至图4所示，本发明的字典嵌套字典数据结构的稀疏矩阵压缩存储方法，字典是一些元素的集合，每个元素有一个称作键的域，不同元素的键各不相同。字典是一种以键-值对形式存储结构的数据结构。

设稀疏矩阵表示为A＝(a

按行或按列存储稀疏矩阵A，所述按行存储稀疏矩阵A是：将每个非零的元素的值a

所述的按列存储稀疏矩阵A是：将每个非零的元素的值a

所述的M,N为正整数。

所述的稀疏矩阵是任意的，可以是规则的，也可以是不规则的。

实施例1：

参见图1至图4所示，本实施例的字典嵌套字典数据结构的稀疏矩阵压缩存储方法，具体步骤如下：

设稀疏矩阵A＝(a

(1)初始化生成字典嵌套字典类型的数据结构；

(2)读取稀疏矩阵A的第i行第j列元素的值a

(3)判断元素的值a

(4)将行索引i存储在字典嵌套字典数据结构的外层字典的键中，列索引j存储在相应的外层字典行索引i所对应的内层字典的键中，非零的元素的值a

(5)判断是否为稀疏矩阵A的最后一个元素，如果不是，则跳至第(6)步；如果是，则结束。

(6)读取下一个元素的值a

最后将稀疏矩阵A压缩成如图4所示的字典嵌套字典数据结构中。由图可知，此稀疏矩阵的压缩比为

大规模的稀疏矩阵的压缩存储方法同上述流程一致，不做详细描述。

以上所述仅为本发明的优选实例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡对本发明所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。