Skip to main content

数组和特殊矩阵

数组​

定义

数组是由一些相同类型的数据元素组成的有限序列，数组可以视为线性表的推广。

对于多维数组，其存储结构可以分为 按行优先 和 按列优先，前者以行为单位进行存储，存储为一行之后再存储下一行，后者按照列为单位。

特殊矩阵​

压缩矩阵：为多个相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：对于一些有特殊性质矩阵的优化，如对称矩阵、上（下）三角矩阵、对角矩阵等。

对称矩阵​

对于一个 nn 阶对称矩阵，只需要存储主对角线及其以上（下）的区域即可，若存储上三角，则每行存储的元素与其行数的对应关系如下：

S(i)=n−i+1S(i)=n-i+1

若存储下三角，则对应关系为

Si=iS_{i}=i

则可以存储在长 n(n+1)2\frac{n(n+1)}{2} 的一维数组中。

对于矩阵的元素 ai,j,i,j>0a_{i,j},i,j>0，求其与该一维数组 （下标从 0 开始）的对应关系：

  1. 由下标可以得知其所在位置第 ii 行与第 jj 列；
  2. 若存储上三角，当 i≤ji\leq j ，元素在上三角区域，前面 i−1i-1 行的元素个数为 (n+n−i+2)(i−1)2=(2n−i+2)(i−1)2\frac{(n + n-i+2)(i-1)}{2}= \frac{(2n-i+2)(i-1)}{2}，再加上当前列所在行在上三角区域前面的元素个数 n−i+1−(n−j)=j−i+1n-i+1-(n-j)=j-i+1；若 i>ji>j 时，由于其是对称矩阵，满足 ai,j=aj,ia_{i,j}=a_{j,i}，只需要将 i,ji,j 互换即可
  3. 若存储下三角，当 i≥ji\geq j，元素在下三角区域，前 i−1i-1 行的元素个数为 i(i−1)2\frac{i(i-1)}{2}，其所在第 ii 行下三角区域的第 jj 个元素，i<ji<j 时同理，互换即可。

因此对应关系为

k={(2n−i+2)(i−1)2+j−i  i≤j(2n−j+2)(j−1)2+i−j  j≤i k=\begin{cases} \frac{(2n-i+2)(i-1)}{2}+j-i\ \ i\leq j\\ \frac{(2n-j+2)(j-1)}{2}+i-j\ \ j\leq i \end{cases}
note

这里都减去 11 是因为数组下标从 00 开始。

上面是按照行优先的方式进行计算的，请自行推到按列优先的情况

三角矩阵​

tip

下（上）三角矩阵指的是上（下）三角区域（除去主对角线）全为同一常量，因此其存储方式与对称矩阵类似，只需要多额外存储该常量到最后一个元素即可。

下标对应公式可由上面的式子推出，不再赘述。

三对角矩阵​

三对角矩阵

也称 带状矩阵，即主对角线及其上下一个副对角线的位置不为 00，其他元素都为 00.

可以按行进行存储，除了第一行和最后一行是两个元素，其他行都是三个元素，因此一维数组的长度为 4+3(n−2)=3n−24+3(n-2)=3n-2

求矩阵元素坐标与数组下标的对应关系：

  1. 虽然三对角矩阵每行元素个数并不相同，但是可以将其首尾进行扩展，额外添加一个元素；
  2. 对于 合法的 第 ii 行第 jj 列的元素 ai,ja_{i,j} 来说，前 i−1i-1 行有 3i−33i-3 个元素，由于有一个多添加的元素，减去一个 3i−43i-4，当前行前面共有 j−i+2j-i+2 个有效元素，则对应关系为
k=3i−4+j−i+2−1=2i+j−3(1) k=3i-4+j-i+2-1=2i+j-3\tag1
caution

合法的坐标取值范围是 1≤i,j≤n,∣i−j∣≤11\leq i,j\leq n,|i-j|\leq 1.

反过来，若得知一维数组的第 kk 个元素，其对应的矩阵坐标为：

  1. 同上述方法，额外添加一个得 k+1k+1
  2. 由于一行三个元素，则其行数为 k+13+1\frac{k+1}{3}+1;
  3. 列数用式 (1)(1) 反推 j=k−2i+3j=k-2i+3.

稀疏矩阵​

稀疏矩阵

非零元素远小于零元素的矩阵，一般认为非零元素占比小于 10%10\% 就可以视为稀疏矩阵， 此时采用常规方法存储会造成大量的浪费。

稀疏矩阵的常见存储格式如下：

  1. COO (Coordinate) 格式：以坐标形式存储稀疏矩阵的非零元素，每个非零元素包括其行号、列号和值；
  2. CSR (Compressed Sparse Row) 格式：通过将每一行的非零元素压缩存储来表示稀疏矩阵，其中需要三个数组：非零元素的值数组、每行第一个非零元素的列号数组和非零元素在值数组中的索引数组；
  3. CSC (Compressed Sparse Column) 格式：与 CSR 格式类似，但是通过按列存储非零元素来表示稀疏矩阵，需要三个数组：非零元素的值数组、每列第一个非零元素的行号数组和非零元素在值数组中的索引数组；
  4. DOK (Dictionary of Keys) 格式：使用字典数据结构存储稀疏矩阵的非零元素，其中字典的键是非零元素的坐标，值是对应的元素值
  5. BSR (Block Compressed Row) 格式：将稀疏矩阵划分为相等大小的块（block），然后针对每个块内的非零元素使用CSR格式进行压缩存储。
info

CSR 中，所有非零值存放在一个 valuevalue 数组中，并且使用一个相同长度的数组 indicesindices 存储其列号（一一对应），第三个矩阵被称为 row_offsetsrow\_offsets，其长度为矩阵行数，表示在原矩阵中每行第一个非零元素，在 valuevalue 数组中的位置。

CSC 类似，只是行列互换。

note

适合存储稀疏数组的数据结构有三元数组 和 十字链表。