编程文汇

稀疏矩阵

想用稀疏矩阵,用正常矩阵可能会浪费90%的矩阵空间,上次我就是直接使用的矩阵,终归要规划地图规模。只知道有稀疏矩阵的概念,不知道怎么存储,这里背背书。

很久没看了,复习一下:

主要存储格式

知乎上一位兄弟收集的很全面:

我看了全文,发现只有前两个有用:

  • COO , coordinate format.

COO格式是将矩阵中的非零元素以坐标的方式存储。例如下面的矩阵:

[公式] (1)

COO格式即将非零元素的行,列,值三个元素记录下来形成下面的表格。

[公式]

因此可以用两个长为nnz(非零元素的个数)整数数组分别表示行列指标,用一个实数数组表示矩阵元。

  • DOK ,Dictionary of keys

DOK的存储格式与COO格式相同,只是用字典变量存数稀疏矩阵的矩阵元。行列值作为字典的键,矩阵元作为字典内容。以上面为例。

[公式]

在python中,这一点非常容易实现。并且以上两种格式的矩阵元是可以乱序排列的。

毫无疑问,选择DOK

DOK用位操作和std::unordered_map非常容易实现,hash映射,增删改的算法复杂度都很低,都是常数。