共计 1621 个字符，预计需要花费 5 分钟才能阅读完成。
稠密矩阵的概念
一个 m×n 的矩阵是一个由 m 行 n 列元素排列成的矩形阵列。矩阵里的元素能够是数字、符号及其他的类型的元素。
一般来说，在矩阵中，若数值为 0 的元素数目远远多于非 0 元素的数目，并且非 0 元素散布没有法则时，则称该矩阵为稠密矩阵；与之相同，若非 0 元素数目占大多数时，则称该矩阵为浓密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的浓密度。，上面的矩阵就是一个典型的稠密矩阵。
咱们日常应用的电子表格也是一个典型的稠密矩阵场景，电子表格（SpreadJS, Excel，Google Sheet 等等），整体看起来像一个 table 表格。，
其中列名称顺次为 A, B, C … …，行名称顺次为 1, 2, 3 … …
举例一个比拟极其的场景，在 A1 和ZZ2000单元格别离赋值，这样咱们就须要一个 2000 行，26*26+26=702 列的矩阵来示意它，这个矩阵是一个显著的稠密矩阵。
稠密矩阵的存储形式及优化
间接存储为二维矩阵
间接应用二维矩阵会简略间接地存储整个电子表格，这样你不用每次都创立或删除一段内存。
但这是一种十分暴力的存储值的办法，这种形式下会耗费大量内容来存储毫无内容的单元格。
简略的来看一下它的复杂度：
- 占用空间：O(N2)
- 插入数据 ： 须要毁坏矩阵.
- 删除数据 ： 须要毁坏矩阵.
- 搜寻数据：O(N2)
- 拜访数据：O(1)
N是假如行和列具备雷同长度并造成正方形矩阵的行 / 列数。
通过键值对 (Map, Dictionary) 优化
在这种办法中，只有在单元格有值时，咱们才将单元格的值和地位存储在一起，应用 HashMap 或者 Dictionary 这些数据结构能够很容易的做到.。
下图咱们能够看到，键值对中别离存储了单元格地位和单元格值。
来看一下它的复杂度：
- 空间：O(N)
- 插入：O(1)
- 删除：O(1)
- 搜寻：O(N)
- 拜访：O(1)
N为所记录的条目数。
通过稠密矩阵存储形式优化
在稠密矩阵中，咱们能够应用三个不同的数组来存储行索引、列偏移、和其中的值，而不是间接在二维矩阵中存储值。以这种形式按列压缩稠密矩阵
存储的三个数组：
- 值 => 单元格中的值。
- 行索引 => 单元格的行索引。
- 列偏移 => 这里每个索引都代表列，并且该数组将行开始的索引值存储在 Row 数组中。
稠密矩阵具体的插入，、删除，、搜寻，、拜访的代码，大家能够本人来搜寻，这方面的材料网上有很多。，这里不一一列举。
和下面一样，来看看这种形式的复杂度：
- 空间：O(N)
- 插入：O(N)
- 删除：O(N)
- 搜寻：O(N)
- 拜访：O(1)
相较于传统的数组存储或是键值对存储，稠密矩阵存储构建了基于行索引为 Key 的数据字典，在涣散布局的表格数据中，稠密矩阵只会对非空数据进行存储，而不须要对空数据开拓额定的内存空间。应用这种非凡的存储策略，使得数据片段化变得容易，能够随时框取整个数据层中的一片数据，进行序列化或反序列化。如果咱们在我的项目开发中须要存储相似构造的数据，稠密矩阵这种存储形式，无论从工夫还是空间上都能大大的提成性能。
在葡萄城的 SpreadJS 和 GcExcel 表格组件中，也奇妙的应用了稠密矩阵这一个性，能够随时替换或复原整个存储构造中的任何一个级别的节点，以扭转援用的形式更高效的地解决表格数据回滚和复原问题，而这一点也为葡萄城表格组件反对多人在线协同打下了一个良好的根底。
因为底层采纳了稠密矩阵来优化存储，SpreadJS 在前端页面中，实现了 100W 级别数据秒级响应的能力：
纯前端百万级数据申请、加载、筛选和排序
点击此处能够在线体验：性能演示
同时，联合 SpreadJS 中应用的 Canvas 绘制模型，双缓存画布渲染等专利技术，让 SpreadJS 的前端性能相比于同类产品遥遥领先。
更多纯前端表格在线 demo 示例 :https://demo.grapecity.com.cn…
纯前端表格利用场景：https://www.grapecity.com.cn/…
挪动端示例（可扫码体验）：http://demo.grapecity.com.cn/…
