Immutable 结构共享

鉴于 mobx-state-tree 的发布,实现了 mutable 到 immutable 数据的自由转换,将 mobx 写法的数据流,无缝接入 redux 生态,或继续使用 mobx 生态。

这是将事务性,可追溯性与依赖追踪特性的结合,同时解决开发体验与数据流可维护性。万一这种思路火了呢?我们先来预热下其重要特征,结构共享。

1 引言

结构共享不仅仅是 “结构共享” 那么简单,背后包含了 Hash maps tries 与 vector tries 结构的支持,如果让我们设计一个结构共享功能,需要考虑哪些点呢?本期精读的文章给了答案。

2 内容概要

使用 Object.assign 作用于大对象时,速度会成为瓶颈,比如拥有 100,000 个属性的对象,这个操作耗费了 134ms。性能损失主要原因是 “结构共享” 操作需要遍历近 10 万个属性,而这些引用操作耗费了 100ms 以上的时间。

解决办法就是减少引用指向的操作数量,而且由于引用指向到任何对象的损耗都几乎一致(无论目标对象极限小或者无穷大,引用消耗时间都几乎没有区别),我们需要一种精心设计的树状结构将打平的引用建立深度,以减少引用操作次数,vector tries 就是一种解决思路:

上图的 key: t0143c274,通过 hash 后得到的值为 621051904(与 md5 不同,比如 hash(“a”) == 0,hash(“c”) == 2),转化为二进制后,值是 10010 10000 01001 00000 00000 00000,这个路径是唯一的,同时,为了减少树的深度,按照 5bit 切分,切分后的路径也是唯一的。因此寻址路径就如上图所示。

因此结构共享的核心思路是以空间换时间

3 精读

本精读由 rccoder ascoders cisen BlackGanglion jasonslyvia TingGe twobin camsong 讨论而出,以及我个人的吐血阅读论文原文总结而成。

Immutable 树结构的特性

camsong 的动态图形象介绍一下共享的操作流程:

share

但是,当树越宽(子节点越多)时,相应树的高度会下降,随之查询效率会提高,但更新效率则会下降(试想一下极限情况,就相当于线性结构)。为寻求更新与查询的平衡,我们便选择了 5bit 一分割。

因此最终每个节点拥有 2^5=32 个子节点,同时通过 Vector trie 和 Hash maps trie 压缩空间结构,使其深度最小,性能最优。

Vector trie

通过这篇文章查看详细介绍

其原理是,使用二叉树,将所有值按照顺序,从左到右存放于叶子节点,当需要更新数据时,只将其更新路径上的节点生成新的对象,没有改变的节点继续共用。

vector-tire

Hash maps trie

Immutablejs 对于 Map,使用了这种方式优化,并且通过树宽与树高的压缩,形成了文中例图中的效果(10010 10000 聚合成了一个节点,并且移除了同级的空节点)。

树宽压缩:

vhash-maps-tire-1

树高压缩:

hash-maps-tire-2

再结合 Vector trie,实现结构共享,保证其更新性能最优,同时查询路径相对较优。

Object.assign 是否可替代 Immutable?

结构共享指的是,根节点的引用改变,但对没修改的节点,引用依然指向旧节点。所以Object.assign 也能实现结构共享

见如下代码:

const objA = { a: 1, b: 2, c: 3 }
const objB = Object.assign({}, objA, { c: 4 })
objA === objB     // false
objA.a === objB.a // true
objA.b === objB.b // true

证明 Object.assign 完全可以胜任 Immutable 的场景。但正如文章所述,当对象属性庞大时, Object.assign 的效率较低,因此在特殊场景,不适合使用 Object.assign 生成 immutable 数据。但是大部分场景还是完全可以使用 Object.assign 的,因为性能不是瓶颈,唯一繁琐点在于深层次对象的赋值书写起来很麻烦。

Map 性能比 Object.assign 更好,是否可以替代 Immutable?

当一层节点达到 1000000 时,immutable.get 查询性能是 object.key 的 10 倍以上。

就性能而言可以替代 Immutable,但就结合 redux 使用而言,无法替代 Immutable。

redux 判断数据更新的条件是,对象引用是否变化,而且要满足,当修改对象子属性时,父级对象的引用也要一并修改。Map 跪在这个特性上,它无法使 set 后的 map 对象产生一份新的引用。

这样会导致,Connect 了 style 对象,其 backgroundColor 属性变化时,不会触发 reRender。因此虽然 Map 性能不错,但无法胜任 Object.assign 或 immutablejs 库对 redux 的支持。

3 总结

数据结构共享要达到真正可用,需要借助 Hash maps tries 和 vector tries 数据结构的帮助,在上文中已经详细阐述。既然清楚了结构共享怎么做,就更加想知道 mobx-state-tree 是如何做到 mutable 数据到 immutable 数据转换了,敬请期待下次的源码分析(不一定在下一期)。

如何你对原理不是很关心,那拿走这个结论也不错:在大部分情况可以使用 Object.assign 代替 Immutablejs,只要你不怕深度赋值的麻烦语法;其效果与 Immutablejs 一模一样,唯一,在数据量巨大的字段上,可以使用 Immutablejs 代替以提高性能。

阅读全文
下载说明:
1、本站所有资源均从互联网上收集整理而来,仅供学习交流之用,因此不包含技术服务请大家谅解!
2、本站不提供任何实质性的付费和支付资源,所有需要积分下载的资源均为网站运营赞助费用或者线下劳务费用!
3、本站所有资源仅用于学习及研究使用,您必须在下载后的24小时内删除所下载资源,切勿用于商业用途,否则由此引发的法律纠纷及连带责任本站和发布者概不承担!
4、本站站内提供的所有可下载资源,本站保证未做任何负面改动(不包含修复bug和完善功能等正面优化或二次开发),但本站不保证资源的准确性、安全性和完整性,用户下载后自行斟酌,我们以交流学习为目的,并不是所有的源码都100%无错或无bug!如有链接无法下载、失效或广告,请联系客服处理!
5、本站资源除标明原创外均来自网络整理,版权归原作者或本站特约原创作者所有,如侵犯到您的合法权益,请立即告知本站,本站将及时予与删除并致以最深的歉意!
6、如果您也有好的资源或教程,您可以投稿发布,成功分享后有站币奖励和额外收入!
7、如果您喜欢该资源,请支持官方正版资源,以得到更好的正版服务!
8、请您认真阅读上述内容,注册本站用户或下载本站资源即您同意上述内容!
原文链接:https://www.shuli.cc/?p=17508,转载请注明出处。
0

评论0

显示验证码
没有账号?注册  忘记密码?