Closed ascoders closed 7 years ago
文章中 Immutable 的实现是利用 object 的 key 构建了一棵 tire 树,然后在 update 之后针对没有修改的地方依旧指向老的 node,针对改变了的地方创建新的 node。
做个动画就是 camsong 之前画过的:
正是借助这种指向老节点的方式实现了 结构共享,在保持快速复制的同时保持内存占用低(有种软链接的感觉 😂)。
疑问? 如果是 tire 树的实现方式,在数据没怎么变化的情况下目测会增高内存占用?构建树本身应该需要一定的内存占用,记忆中这棵树还是比较大的。不过利用多数组 tire 树好像可以解决,目测相关库应该做了这方面的工作?
除此,如果实现一个简单的 Immutable,也可以不上 tire 树,比如: seamless-immutable
目前 Immutable 数据的更新都是借助相关库的 API 来更新,有比较强的侵入性。用了他之后我们之前熟悉的赋值,取值甚至判断相等都会发生变化。
如果在老代码中混合使用 Immutable 容易造成混淆,写出一堆乱七八糟的东西(可以想想混用 jQuery 和 浏览器原生支持的 DOM 操作混淆使用);在新代码中的话可以强制使用 Immutable。
最后期待 ES Next 支持原生的 Immutable。
我认为结构共享核心概念不是指针指向老节点,而是使用了 tire 树。 看如下代码:
const obj = { a: 1 }
const shallow = Object.assign({}, obj, { b: 2 })
console.log(shallow === obj) // false
console.log(shallow.a === obj.a) // true
可见 Object.assign 浅拷贝本身就是创建新对象,将指针指(js里是引用)向老节点的行为,只是当对象內数据量过大的时候,本身引用链接的过程就很慢。
而 tire 树的数据结构,保证其拷贝引用的次数降到了最低,这张图最为形象:
就是通过极端的方式,大大降低拷贝数量,一个拥有100万条属性的对象,浅拷贝需要赋值 99.9999万次,而在 tire 树中,根据其访问的深度,只有一个层级只需要拷贝 31 次,这个数字不随着对象属性的增加而增大。而随着层级的深入,会线性增加拷贝数量,但由于对象访问深度不会特别高,10 层已经几乎见不到了,因此最多拷贝300次,速度还是非常快的。
共享应该是指新旧节点共享子节点
this.entries = newEntries;
我研究过immutablejs的源码,抽象上还不是很理解,只懂点具体代码。里面好多递归,修改和两个非迭代关系的数据的比较都很耗性能。immutable无非就是读写,读比较简单略过。写的话每个节点都有自己的update函数,这个update会判断递归新建还是递归结束。实质上我觉得immutablejs好多都是抄scala的,iterable、seq、map等。估计就是scala不可变数据的js实现版,然后加上一堆好用的接口,然后就完成了。
本次精读的内容与刚结束的 JSConf EU 中的 Immutable data structures for functional JS 颇为相似。但均在 Tire 树的实现与优化上讲得比较简略,特做两点补充,欢迎指正~~
图中,t0143c274
经过 Immutable.js 的 hash 函数计算后,得到 621051904,转化为二进制为 10010 10000 01001 00000 00000 00000
文中的 不要将应用的业务逻辑与数据结构绑定 小节,提到需要搜索 10 万个 todo 中包含指定 assignee 的 todo,需要将这 10 万个元素遍历一遍,而解决方案是修改底层的数据结构,维护一个 taskId 与 assigneeId 之间的反向查找表。
事实上,反向查找表(Reverse Lookup Table)在安全领域是一个非常常见的概念,经常被用来做 MD5 的碰撞,又称彩虹表(Rainbow Table)。
所以解决方案大概就是:
{
't79444dae': [1, 2],
't7eaf70c3': [2],
't2fd2ffa0': [3],
...
(100,000 items)
}
默默感觉有点像 Redux 里的 normalizr 的概念?
关于结构共享的话题。我来闲聊下:
可变(Mutable)和不可变(Immutable)是数据结构的属性,而不是某种语言的。
各开发语言在实现上也各有不同。举些例子: Java.util.ArrayList 是结构上不可变的对象;Clojure 则原子在结构上不可变。当然也有 Immutable Object 模式这类优良实践的存在。
我了解的 JavaScript ,还是在依赖第三方库如 mori、Immutable.js 等实现结构上不可变的对象,可能 提供的 API 上风格有些差异。
最近在 Github 上发现个 js-structural-sharing 的一个示例,摘段代码给大家参考:
// returns true if the second object has a reference to the first object anywhere in its graph tree
function referencesAnywhereInItsGraph(obj1: any, obj2: any) {
if (isValue(obj1) || isValue(obj2)) return false;
if (obj1 === obj2) return true;
const obj2Props = properties(obj2, "enumerable && height>=1", x => {
return { prop: x.prop, value: x.value };
});
for (let i = 0; i < obj2Props.length; i++) {
const vb = obj2Props[i].value;
if (isValue(vb)) continue;
if (obj1 === vb) {
return true;
} else {
const subTreeReferences = referencesAnywhereInItsGraph(obj1, vb);
if (subTreeReferences) return true;
}
}
return false;
}
通常,结构共享与不可变数据结构相关联,但它也适用于结构上不可变的对象。完全可变的数据结构是不可能的,因为结构修改会破坏结构共享。
结构上不可变的对象的组成,即你可以将两个结构上不可变的对象粘合在一起,并创建一个新的结构上不可变的对象。这样可以通过将原始对象的两个引用保持在组合来利用结构共享,即新的组合对象可以非常轻量化。
另外,可以通过结构共享再次支持可变的子视图。您可以将视图创建为结构不可变数据结构的子集,其中,视图的更改还会更改底层数据,反之亦然。
immutable 内部使用了 trie 数据结构,参考 hash maps trie(HAMT)和 vector trie,来实现 persist data structure。
Vector trie 由于: (1)串具有较好的空间效率和顺序访问性能,但缺乏随机访问数据的能力; (2)树具有较好的操作数据能力,但空间效率和顺序访问性能较差; Vector trie 结合了串和树的特点,将所有的数据都保存在树的根节点,则树的最下一层叶子节点可以被看成是串,再将其分割成等长的分段,通过 Trie 树结构作为每个数据节点的索引。 Vector trie 在每次修改操作的时候, 复制从根到叶子节点的路径而不是直接修改它们,这样从两个根就可以访问到对数据不同时刻的两个快照。
hash maps trie(HAMT) 首先了解下 Hash Table,它是利用对象的 Hash 值对所储存的键进行散列从而实现快速的插入、删除和访问的数据结构。 HAMT 是将元素的 Hash 值按位分割成固定宽度的序列,在 Trie 树上以这些序列按顺序查找元素应该存放的位置,并且增加了节点内部的空间压缩和树高的压缩。
节点内部的空间压缩:
树高的压缩:
不过,Immutable.js 提供的API比较多,包括 List、Stack、Map、OrderedMap、Set、OrderedSet、Record等,库的体积比较大,个人觉得如果可以将 Immutable.js 拆分,提供按需打包会更好,如:'immutable/list'、'immutable/map' 等。
@twobin 回答很给力。关于 immutable/list
这种引用过会带来以下问题:
external: "immutable"
将会失效因此要拆我也建议拆成 immutable-list
这种包。
Immutable.js 提供的类大多是基于 Hash maps tries 和 vector tries 这两个数据结构来做的增强,这些都是 DAG 无回路有向图的具体实现算法。上面 @BlackGanglion @twobin 讲的很详细。
Immutable.js 文档里很明确的指出这样做的目的就是为了减少对象的复制,也就是尽可能多的把没有变化的地方依旧指向老 node。但 Object.assign
却不是这样。
我来对比下 Immutable.js 和它的最大竞争对手 Object.assign
之间的关系。
Object.assign
会把 10000 个对象全部复制一遍。因此 Object.assign 并不能实现不变数据指向旧的引用。Object.assign
会使用旧对象的引用,但改对象的引用还是需要一步操作啊。但 immutable 却把这个操作降到最小,结果有了 134ms 到 1.2ms 的提升。总之,在处理大量数据情况下,immutable.js 非常有价值。
文章地址:https://medium.com/@dtinth/immutable-js-persistent-data-structures-and-structural-sharing-6d163fbd73d2 鉴于 mobx-state-tree 的发布,完美融合了 redux 与 mobx,最大的特色是使用 mutable 数据,完成 immutable 的快照,这种机制是 structural sharing,让我们先夯实基础,聊聊结构共享吧。